Questions tagged [convex-optimization]
Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
65 questions from the last 365 days
1
vote
0
answers
29
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
-2
votes
0
answers
24
views
Conditions for a cubic function to be quasiconcave or quasiconvex [closed]
I would like to understand under what conditions a cubic function $f(x)=ax^3+bx^2+cx+d$ can be considered quasiconcave or quasiconvex. Specifically, I am interested in finding conditions on the ...
- 13
1
vote
1
answer
82
views
Solution to a quadratically constrained quadratic program with unit ball constraint
I am working on a quadratically constrained quadratic program (QCQP) of the form:$$ \min_{x} \quad \frac{1}{2} x^T P x + q^T x + r$$
$$ \text{subject to} \qquad x^{T}x \leq 1 $$
where $P \in S^{++}_{...
- 13
0
votes
0
answers
37
views
Bounding the error of a truncated moment problem
Let $\{x_{i}\}_{i=1}^{\infty}$ be a non-increasing sequence of non-negative real numbers, and let $\{y_{j}\}_{j=1}^{B}$ be a non-increasing sequence of non-negative real numbers, where $B$ is a finite ...
- 433
0
votes
0
answers
39
views
Optimizing over convex polynomials
I have a minimization problem which reads $\min\limits_P J(P)$, where the minimum is over convex polynomials in $n$ variables, with degree at most $d$, and $J$ is a function taking polynomials as ...
- 101
2
votes
1
answer
92
views
Does approximately null gradient imply approximately global minimum for convex functions?
Let $f: \mathbb{R}^{n} \rightarrow \mathbb{R}_{+}$ be a non-negative and differentiable convex function which vanishes in a non-empty convex set $\Omega$ - possibly unbounded. Usually, when one ...
- 225
0
votes
0
answers
30
views
Question on the closed proper convex functions
I'm confused with the definition of the closed proper convex functions when reading the paper
https://people.orie.cornell.edu/aslewis/publications/00-dykstras.pdf
It appears that, when a function $f$ ...
- 1,389
1
vote
0
answers
48
views
What makes the generalized projection different than metric on a Banach space?
I have came across the notion of generalized projection in Banach spaces, introduced by Ya. Alber and has seen many iterative algorithms being solved by using this projection. It helps in finding the ...
- 85
0
votes
0
answers
35
views
Describing the boundary of the feasible direction cone to a convex open subset of $\mathbb{R}^n$ at a boundary point: connection via subdifferential?
Let $U\subset \mathbb{R}^n$ be a convex, open set with nonempty boundary. Let $x_0\in \partial{U}.$ We can describe $U$ locally near $x_0$ as a super level set of a suitable continuous concave ...
- 1,465
1
vote
0
answers
29
views
Change in active constraints when perturbing the objective of a QP
Suppose I have a quadratic program (with positive semidefinite cost matrix) with affine (polytopic) constraints. It is known that the solution to this is piecewise affine, with the ``pieces'' defined ...
- 11
4
votes
1
answer
172
views
Maximizing trace subject to two equality constraints
I am looking at the following optimization problem
$$\begin{align}
\underset{{\bf X}}{\text{maximize}} \qquad&\mathrm{tr}({\bf AX})\\
\text{subject to} \qquad& \mathrm{tr}({\bf X}) = 1,\\
&...
- 43
0
votes
1
answer
57
views
Self-concordant barrier for the epigraph of $f(x,y) = x^p y^{1-p}$?
The problem
Assume $p > 1$. Consider the function
$$f(x,y) = x^p y^{1-p}, \qquad x,y > 0.$$
Note that
$$
f'' = p(p-1)x^{p-2}y^{-1-p}
\begin{bmatrix}
y \\ & x
\end{bmatrix}
\begin{bmatrix}
1 &...
- 981
0
votes
2
answers
97
views
Optimization algorithms for Kronecker approximation of high-dimensional covariance matrices
I'm working with a high-dimensional covariance matrix and exploring Kronecker product approximations to make it computationally manageable.
Here's the setup:
I have a graph $G$ represented by a $D\...
- 1
0
votes
1
answer
236
views
Solving a 0-1 quadratic matrix inequality
I am working on a binary optimization problem. So far I have derived the following constraint functions.
\begin{align}
\begin{bmatrix} \left( P + \sum_{i=1}^n (\sum_{j=1}^n x_{i, j} \alpha_j) e_i e_i^...
- 11
1
vote
0
answers
46
views
Intuition for proximal point method using L2 regularization
To minimize a function $f$, the proximal point method is defined as
$$x_{k+1} := \operatorname*{argmin}_x f(x) + \frac{1}{2\eta}\|x - x_k\|^2.$$
What's the intuition for why we want to use L2 ...
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
1
vote
1
answer
60
views
Optimal transport for sum of two costs
Let $X$ be a finite set and $\sigma_0$, $\sigma_1$ two fixed measures on $X$ with $\sigma_0(X)=\sigma_1(X)$. A transportation plan is a measure $\mu$ on $X\times X$ whose projections on the first and ...
- 1,074
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
0
votes
0
answers
69
views
Degree of reflectional symmetry of (unbounded) convex polyhedra in Euclidean spaces
Let $U \subset \mathbb{R}^m$ be an open domain. I'm trying to come up with a measure of its degree of reflectional symmetry and I have a question. The post in two-part, where in PART I I introduce the ...
- 1,465
7
votes
0
answers
249
views
Proving this function is convex
Let $C$ be a symmetric positive definite matrix such that $0\leq c_{ij} \leq 1$, $c_{ii}=1$, and define $f$ as $$f(x)=\sum_{i}x_{i}\log(\sum_{j}c_{ij}x_{j})$$ for positive vectors $x$ (in fact let's ...
- 4,049
1
vote
0
answers
40
views
In search for optimal solution for a minimization problem
I am trying to solve the following optimization problem:
$\begin{align}\min_{\mathbf{c}_{k}} \sum_{k=1}^{K}\frac{q_k}{c_k} \\
\text{s.t. } c_k &\geq t_k \quad \forall k \tag1\label1 \\
\sum_{k=1}^{...
1
vote
0
answers
143
views
Integer points inside the high-dimensional ball (asymptotics)
Let $N(\alpha, n)$ denote the number of integer points inside the origin-centered ball of radius $\alpha \sqrt n$ in $n$ dimensions, where $\alpha \in (0,\infty)$ is some fixed constant. Precisely:
$$...
- 435
0
votes
0
answers
52
views
What are the injective embeddings of R^d into the cone of (semi-) positive definite matrices of dimension d?
How can we characterize the set of all injective functions from $\mathbb{R}^d$ to the set of all symmetric positive definite matrices of dimension d?
- 109
1
vote
0
answers
73
views
Convexity and subdifferential monotonicity
Do you know any reference where I can find some results in this sense:
Consider $W:K\to [0,\infty)$ is a functional defined on a convex cone $K\subset X$, where $X$ is a Banach space. Then the ...
- 1,759
1
vote
0
answers
41
views
Is there any software package to find the vertices of convex polytope where the inequality constraints are bounded by variable?
I know of this package lcon2vert that computes vertices from given inequality and equality constraints describing a bounded polyhedron. Here the bounds of constraints only accept numerical values, i.e....
1
vote
1
answer
63
views
Question on the relation between the Lagrangian Multiplier $\mathcal{L}=r+\lambda g(r,\theta_1,\dotsc,\theta_{N-1})$ and the Hessian of $r$
I want to minimize the radius $r=\sqrt{x^2_1+x^2_2+\dotsb+x^2_N}$, with the constraint $g(r,\theta_1,\dotsc,\theta_{N-1})=0$. Here $g(r,\theta_1,\dotsc,\theta_{N-1})$ is a function defined in the $N$-...
- 375
13
votes
0
answers
710
views
Minimizing total variation under constraint
For $p\in[0,1]$, we write $\mathrm{Ber}(p)$
to denote the Bernoulli measure on $\{0,1\}$;
that is, $\mathrm{Ber}(p)(0)=1-p$,
$\mathrm{Ber}(p)(1)=p$.
For $n\in\mathbb{N}$ and $p=(p_1,\ldots,p_n)\in[0,1]...
- 6,541
1
vote
0
answers
45
views
Inequality Involving Concave Monotonic Function
Assume that $ f: \mathbb{R} \to \mathbb{R}_+ $ is a concave, non-decreasing and positive function. Let $\mathbb{X}$ be a finite set consisting of $ 0\leq x_1 \leq x_2 \leq x_3 \leq \ldots \leq x_n$. ...
0
votes
0
answers
51
views
Minimizer of forward and reverse Kullback-Leibler divergence with sum constraints on marginals
Consider minimization of the Kullback Leibler divergence between two discrete distributions $p$ and $q$:
\begin{align*}
D_{KL} \left( p \parallel q \right) = \sum_i p_i \log \left( \frac{p_i}{q_i} \...
2
votes
0
answers
58
views
An s-convex function lying between two convex functions
Let $f: \mathbb R_{+} \to \mathbb R_{+}$ be an $s$-function in the second sense, i.e.,
$$ f(\lambda x +(1-\lambda)y) \leq \lambda^s f(x) +(1-\lambda)^s f(y)$$ for every $\lambda \in (0,1)$. Assume ...
- 55
0
votes
0
answers
54
views
How to deal with minimizing a flat objective function
Problematic (Debiased Sinkhorn barycenter, proposed by H.Janti et al.): Let $\alpha_1, \ldots, \alpha_K \in \Delta_n$ and $\mathbf{K}=e^{-\frac{\mathrm{C}}{\varepsilon}}$. Let $\pi$ denote a sequence ...
- 121
0
votes
1
answer
150
views
When are infimal convolutions contractions?
Let $X$ be a separable Fréchet space and $\varphi,\psi:X\to \mathbb{R}$ be a lower semi-continuous and convex function with $\psi$ bounded below and coercive. Consider the infimal convolution
$$
\...
- 364
0
votes
0
answers
56
views
How explicit the optimiser of this optimisation problem can be?
Provided the given parameters as follows :
$\mu\in\mathbb R, \sigma\in\mathbb R_+$ are constant, $\kappa, r, \alpha, \beta: \mathbb R_+\to\mathbb R_+ $ are measurable functions such that $\kappa(y)\...
- 1,334
7
votes
2
answers
178
views
Separating domains in $\mathbb{R}^{2n}$ by a real algebraic variety
Suppose $\Omega_1$ and $\Omega_2$ are two disjoint unbounded domains in $\mathbb{R}^{2n}$, $n \in \mathbb{N}$. Can there be conditions on $\Omega_1$ and $\Omega_2$ so that these two domains can be ...
- 171
0
votes
0
answers
115
views
Software for computing polytopes
As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
- 1
6
votes
1
answer
234
views
Stopping criteria for damped Newton iterations with backtracking line search
Are there better criteria than the Armijo criterion for damped Newton iteration with backtracking line search, when the objective is standard self-concordant? (See Boyd and Vandenberghe.)
Let $F(x)$ ...
- 981
1
vote
0
answers
79
views
Touring a sequence of convex polygons with minimal energy
There is a known problem of touring a sequence of $n$ polygons: given a starting point $s$, an ending point $t$ and a sequence of polygons $P_1,\dots,P_k$ with a total of $n$ vertices, find points $...
- 177
0
votes
0
answers
56
views
Convex optimization of the Lovász extension of a submodular function
I have a finite set of $n$ elements $A$, and a submodular function $f:2^A\rightarrow R$.
Let $g:[0,1]^n\rightarrow {R} $ be the Lovász extension of $f$.
I want to solve the following optimization ...
- 107
5
votes
1
answer
176
views
Efficient counting of integer solutions to linear system
In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
- 151
0
votes
0
answers
72
views
Minimizing the Spectral Norm of the Hadamard Product of a Quadratic Form Using CVX
I am trying to use CVX to minimize the spectral norm of the Hadamard product of two matrices, one of which is in quadratic form. Specifically, I am trying to minimize $\|{\bf A} \odot {\bf XX}^H\|_2$, ...
- 43
6
votes
0
answers
48
views
Strengthening the Kovner-Besicovich theorem: Does every unit-area convex set in the plane contain a centrally symmetric hexagon of area $2/3$?
The Kovner-Besicovich theorem states that every convex set $S$ in the plane contains a centrally symmetric subset $C$ of at least $2/3$ the area of $S$, and that this bound is sharp for triangular $S$....
- 3,068
0
votes
0
answers
38
views
Approximate local minima for sum of inverse trigonometric functions
Let $\{a_1, a_2, ..., a_N\} \in [0, 1[^N$, I would like to approximate the minimum of the function
$$f(x) = x \sum_{i=1}^N \left(\sin(x)^2 - \sin(a_i x)^2 \right)^{-2} $$
in the domain $x \in {]0, \...
- 1
2
votes
1
answer
170
views
Equivalence of minimizing trace and determinant over matrix quadratic form in multivariate regression
Consider the multivariate regression model
$$Y = XB + E$$
where $Y$ is $n \times p$ and corresponds to the dependent variables, $X$ is $n \times k$ and corresponds to the independent variables, $B$ is ...
0
votes
0
answers
40
views
Iterating partially-unconstrained optimization with projection
Let $f:H\to \mathbb{R}$ be a strictly convex Fréchet differentiable, coercive function on a separable Hilbert space $H$ and let $C_1,C_2\subseteq H$ be closed and convex.
I want to optimize
$$
\tag{(A)...
- 5,405
1
vote
0
answers
95
views
Distance between two convex sets
Setting
If $A$ an $B$ are two symmetric matrices, we denote by $A >B$ when the matrice $A-B$ is definite positive.
In $\left(\mathbb{R}^{*}_{+} \right)^4$, consider the convex set $$ \Lambda = \...
- 125
0
votes
1
answer
59
views
Do separable cubic constraint and separable quartic constraint SOCP presentable?
I am an engineer who is doing some network modeling and optimization. During my work, I was running into a case that is quite strange. The problem that I am trying to solve seems to be convex and it ...
3
votes
0
answers
281
views
Interchange limit and supremum of functionals over a bounded convex set
Let $(H, \langle\cdot,\cdot\rangle)$ be a separable real Hilbert space and $B\subset H$ be (nonempty) convex and bounded, and suppose that $(\alpha_k)\subset H$ is a sequence for which the limit $\...
- 463
0
votes
1
answer
74
views
Clarification about this optimisation problem
Good morning everybody. First of all, I apologise to ask here the same question I asked on MSE three days ago, but I am in fact re-asking since I obtained no relevant advice. Perhaps I will hear some ...
- 149
1
vote
0
answers
37
views
When does an optimal input sequence for a discrete-time system exist?
Suppose an LTI discrete-time system is given by the equations
$$
x_{k+1} = Ax_k + Bu_k,\\
y_{k} = Cx_k + Du_k
$$
with $x_k\in\mathbb{R}^{m}$, $y_k\in\mathbb{R}^{n}$ and $u_k\in\mathbb{R}^{p}$ and $\...
1
vote
0
answers
73
views
What is the closed form of a polyhedral cone's dual cone?
A polyhedral cone can be defined as
$$
\mathcal{K} = \{x~|~Ax\preceq 0\},
$$
where $A \in \mathbb{R}^{m \times n}$, $x\in \mathbb{R}^n$ and $\preceq$ denotes component-wise less than and equal to.
The ...
- 71