Questions tagged [convex-optimization]
Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
839 questions
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
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^{++}_{...
- 63.9k
-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
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
1
answer
104
views
Optimality condition for strongly convex function under sparsity constraint
Let $f: \mathbb{R}^p \to \mathbb{R}$ be a $2s$-sparse strongly smooth, $2s$-sparse strongly convex and twice differentiable function. In other words, there exists positive constants $\alpha, L >0$ ...
CommunityBot
- 1
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
0
votes
2
answers
531
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
CommunityBot
- 1
2
votes
1
answer
183
views
Exponential optimization problem
\begin{eqnarray}
\arg\max_{k}\sum_{i=1}^{p}\sum_{j=1}^{p}\exp\left(-{\frac{\left(X(i,j)-{U_k}(i,j)\right)^2}{2}}\right),\:\: k=0,\dots,p
\end{eqnarray}
where $X$ and $U_k$ are the $p\times p$ matrices,...
CommunityBot
- 1
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 ...
- 128k
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,399
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
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^...
CommunityBot
- 1
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,467
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
2
votes
1
answer
307
views
Positivity of quadratic form minus linear form on the simplex
Let $a_{ij}$ be the elements of a $n$-dimensional covariance matrix. Can we prove the following?
$$ 1-\sum_{k=1}^n a_{ik} \lambda_k + \sum_{j=1}^n \sum_{k=1}^n \lambda_j a_{jk} \lambda_k > 0, \...
CommunityBot
- 1
4
votes
1
answer
174
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,\\
&...
- 109k
1
vote
1
answer
309
views
Numerical estimation of partial derivatives of convolved functions when closed forms do not exist
Summary: Some peak functions are convolutions which may not have a closed form solution. A classical example can that of a Voigt which is a convolution of a Lorentzian and a Gaussian, followed by ...
CommunityBot
- 1
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\...
- 20.2k
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 &...
- 63.9k
2
votes
2
answers
323
views
Reference request on computational schemes for $\inf_{x\in\Omega^n}\sup_{y\in\mathbb R^n}F(x,y)$
Let $\Omega\subset \mathbb R^d$ be compact, $\rho$ be a density function on $\Omega$ and $p_1,\ldots, p_n\in (0,1)$ be weights satisfying $\int_{\Omega}\rho(z)dz=1=\sum_{k=1}^n p_k$. We consider the ...
CommunityBot
- 1
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 ...
- 12.9k
1
vote
1
answer
173
views
Taut string algorithm and TV-minimization equivalence
Given real numbers $y_i's$, consider the following convex optimization problem:
$$
\min_{x_i's} \sum_{i=1}^N(y_i-x_i)^2 + \lambda\sum_{i=1}^{N-1}|x_{i+1}-x_{i}|.
$$
The paper A Direct Algorithm for 1D ...
CommunityBot
- 1
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 ...
- 63.9k
2
votes
1
answer
240
views
Basis pursuit algorithms for exponentially large matrices?
Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is
$$\begin{array}{ll} \underset{x \in \Bbb R^n}{\text{minimize}} & \lVert x \rVert_0\\ \text{...
CommunityBot
- 1
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 ...
- 128k
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$ ...
- 128k
3
votes
1
answer
966
views
Continuity of minimizers to distance function from point to convex set
Suppose I am minimizing the Euclidean distance in $\mathbb{R}^{n}$ between a point $y$ and compact convex set $U$ (where $y\notin U$):
$\min_{x\in U}\|x-y\|$.
I believe the minimizer $x_{U}^{*}$ is ...
CommunityBot
- 1
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,467
2
votes
1
answer
506
views
Effect of duplicated row on singular values and vectors
Let $\mathbf{A}$ be a $n\times n$ matrix with Singular Value Decomposition (SVD) $\mathbf{A}=\mathbf{U}\mathbf{S}\mathbf{V}$ and $\mathbf{a}_1$ be the first row of $\mathbf{A}$. What can we say about ...
CommunityBot
- 1
1
vote
1
answer
266
views
Relative interior of a normal cone at a face of a convex polytope?
Suppose $A$ is a nonempty convex polytope in $\mathbb{R}^n$. Suppose $F$ is a face of $A$.
Consider the normal cone of $A$ at $F$:
$C_A(F)=\{v\in\mathbb{R}^n:v\cdot x\geq v\cdot y\ \forall\ x\in ...
CommunityBot
- 1
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
3
votes
1
answer
368
views
Lot sizing problem: how to add these cuts efficiently
Consider the set of constraints of the uncapacitated lot sizing problem:
$$
\{(x,s,y)\in \mathbb{R}^n_+ \times \mathbb{R}^n_+ \times \mathbb{B}^n \;|\;s_{t-1}+x_t = d_t+s_t,\; x_t \le My_t,\; t=1,\...
CommunityBot
- 1
4
votes
2
answers
905
views
About optimization with Renyi divergence
Can someone link me to some pedagogic example of computing the Renyi divergence between two discrete/continuous distributions? Like examples where someone has been able to obtain a neat closed form or ...
- 67
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:
$$...
- 12.9k
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
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,367
1
vote
1
answer
191
views
Comparison of solutions of Hamilton-Jacobi equations with different initial conditions
Consider a Hamilton-Jacobi equation:
$$u_{t} + f(u_{x}) = 0 \quad (x,t) \in \mathbb{R}\times [0,+\infty)$$
with two possible initial conditions $u(x,0) = g_{i}(x)$ for $x \in \mathbb{R}$ and $i=1,2$. ...
CommunityBot
- 1
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$-...
- 2,670
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$. ...
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
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
1
answer
102
views
Norm bound in simultaneous stability to semidefinite program
In the context of robust control, I remember hearing that the two following problems are equivalent.
Find $P \succ 0$, such that $A P + P A^{\top} \prec 0$ for all $A \in \mathscr{A}$ where $$\...
CommunityBot
- 1
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
1
vote
1
answer
187
views
Bound the distance between two vectors on the probability simplex
Let $a,b$ be two vectors with strictly positive elements and $\delta = 1 - \frac{\langle a,b \rangle}{\|a\|\|b\|}$. Bound the following optimization problem as a function of $\delta$
$$\sup_{x>0} \...
CommunityBot
- 1
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
$$
\...
- 1,714
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
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