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
5
votes
1
answer
2k
views
Algorithm to minimally connect line segments in Euclidean plane
Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...
- 3,979
2
votes
1
answer
276
views
An optimization problem in complex space
Consider the following optimization problem
$$
\min \| \textbf{Ax-B}\|
$$
$$
s.t.|x_i|=1,i=1,...,n
$$
where $\textbf{x}\in \mathbb{C}^{n}$ is the optimization varaible, $x_i$ is the $i$-th ...
- 14k
3
votes
1
answer
239
views
A difficult combinatorial optimization problem
Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$.
(Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. $\mid\...
CommunityBot
- 1
0
votes
1
answer
87
views
Finding maximum of a function with unfixed number of variables
Can anybody solve this:
For a constant positive integer $n\geq6$
find $k$ and positive integers $a_{1},a_{2},...,a_{k}$
that maximize the expression
$$\sum_{i=1}^{k}\left[-4a_{i}^{3}+\left(3n-...
- 37.7k
9
votes
2
answers
967
views
Removing constraints in convex optimization
Say I have a convex optimization problem of the form $$\min_x f(x) ~~ s.t.\\ g_1(x)\leq0,\\\vdots \\g_n(x)\leq 0$$ with all functions convex. Suppose that $x^*$ is a unique optimizer to my problem and ...
- 12.7k
2
votes
0
answers
431
views
What is the purpose of the definition of "metric regularity"/"regularity modulus"?
A set mapping $F:X \rightrightarrows Y$ is said to be metrically regular for $\overline{x}\in X$ and $\overline{y} \in Y$ if there exists a $\kappa\in(0,\infty)$ for which
$$
d(x,F^{-1}(y))\leq \...
- 81
4
votes
0
answers
184
views
This function looks quasiconvex, can't understand why
Suppose that $\mathbf{C}$ is a given matrix with non-negative entries in $\mathbb{R}^{m\times n}$ and $d$ is a given scalar, and let $g(\mathbf{y})$ be defined by $$g(\mathbf{y}):=\max_{\mathbf{x}\in\...
- 41
1
vote
0
answers
81
views
Is there a unique tilted measure with specified marginals?
Suppose $\mathcal{A},\mathcal{B}$ are finite sets and $\mu_{A,B}(a,b)$ is a probability measure on the product set $\mathcal{A}\times \mathcal{B}$ so that $\mu_{A,B}(a,b)>0$ for each $a\in \mathcal{...
- 1,269
1
vote
2
answers
150
views
investigating positivity/negativity of a function [closed]
I'm investigating if and how the positivity or negativity of a multivariable function can be proved. Consider $y_{1},y_{2},y_{3}\in\mathbb{R}$ and the following function
$$f\left(y_{1},y_{2},y_{3}\...
- 79.9k
2
votes
2
answers
352
views
The set of matrices with same spectral radius
I am working on an optimization problem over the set of positive matrices (that is, matrices where all entries are positive numbers) that have the same spectral radius. My main problem is how to ...
- 20.2k
2
votes
1
answer
643
views
Linear dependency of real numbers with integer coefficients adding up to zero [closed]
Let $x = (x_1, \dots, x_n)$ be a vector of real number. I was asking myself if there was an efficient way of telling whether there exists a non-zero vector of integers $z \in \mathbb Z$ such that both
...
- 30.1k
3
votes
0
answers
386
views
On increasing the penalty term in convex optimization with regularization
Given the two strictly convex (unique solution) optimization problems as:
$$Problem\:1:\min_{X} f(X)+\|X\|_{F}^2 \hspace{2cm}Problem \:2:\min_{X}f(X)+n\|X\|_2^2$$
where $X\in\mathbf{S}_{++}^{n}$ (...
- 53
1
vote
0
answers
126
views
Convex Optimization related problem
Suppose two non-negative convex functions $f$ and $g$ be given.
We want to solve the following optimization
$$\max_{g\leq\epsilon}f.$$
Now suppose that both $f$ and $g$ can be upper-bounded by a ...
- 1,109
2
votes
0
answers
83
views
Reference request: Edmond's Algorithm for integer hull
I'm looking for a good reference for the algorithm (supposedly by Edmonds) to compute the integer hull of a polytope, not by cutting plane methods but by starting with a set of integer points and then ...
- 243
1
vote
0
answers
295
views
dual problem of SDP [closed]
suppose we have the following optimization problem:
\begin{array}{l}
\mathop {\min }\limits_{{\bf{X}},{\bf{x}}} \,\,Tr\left( {{\bf{XA}}} \right) + 2{{\bf{a}}^H}{\bf{x}} + b\\
s.t:\,\,\,\,\left[ {\...
- 275
2
votes
1
answer
135
views
Is first term of my cost function convex?
I have an optimization problem in the form of
[\begin{array}{l}
\mathop {{\rm{Minimize}}}\limits_{\bf{X}} \,\,\,2\left| \delta \right|\sqrt {{\rm{Tr}}\left( {{\bf{A}}{{\bf{X}}^2}} \right)} {\rm{ - ...
- 980
1
vote
0
answers
100
views
Changing a nonlinear equality constraint into some conic inequality plus rank constraint
If we have a constraint optimization problem in which one of our constraint is $\prod\limits_{k = 1}^N {\left( {x - {a_k}} \right) = 0} $ . How could this nonlinear equality condition be changed into ...
- 33
0
votes
0
answers
80
views
Finding gradient of an optimization
I am trying to find the gradient of the following optimization problem and then add to objective, but I got some trouble in computing. Could you please help me?
Assume that we have an optimization ...
- 161
1
vote
0
answers
110
views
Characterization of the optimal solution in relative entropy minimization
The following optimization problem is related to relative entropy and to the limit of the iterative proportional fitting procedure.
For $1 \leq i,j \leq n$ and fixed $w_{ij} \geq 0$, and fixed $a_i, ...
- 340
5
votes
1
answer
447
views
Reference request: Continuity of unique maximizer of linear functional on convex set
Does anyone know reference for a theorem of the following sort:
Proposition: Let $K \subset\mathbb {R}^n$ be a compact convex set, and assume that
$$f(w):=\operatorname{argmax}_{x\in K}w(x) $$ is ...
- 837
2
votes
1
answer
147
views
mixed semi definite and second order programming complexity order
Consider the following mixed semi definite and second order programming:
$\begin{array}{l}
\mathop {{\rm{min}}}\limits_{\bf{X}} \,{\rm{Tr}}\left( {{\bf{XA}}} \right)\\
{\rm{s}}{\rm{.t:}}\, & {\rm{...
- 980
2
votes
1
answer
2k
views
Projection onto $\ell^{2,1}$ ball
Does anyone have an idea how to project onto the $\ell^{2,1}$ ball efficiently, i.e. how to solve
$$ u = \arg \min_u \|u-f \|^2 \text{such that } \left(\sum_i \big(\sum_j |u_{i,j}|\big)^2 \right)^{...
- 1,587
5
votes
1
answer
4k
views
Convergence rate of stochastic gradient decent with projections
Given a strong (not only strict) convex function $f: \mathbb{R}^n\to\mathbb{R}$. On such problems, stochastic gradient decent (SGD) has a convergence rate of $O(1/T)$, where $T$ is the number of ...
4
votes
2
answers
207
views
Is the prox-residual monotone?
$\newcommand{\scp}[2]{\langle #1,#2\rangle}\newcommand{\id}{\mathrm{Id}}$
Let $f$ and $g$ be two proper, convex and lower semi-continuous functions (on a Hilbert space $X$ or $X=\mathbb{R}^n$) and let ...
- 28.6k
3
votes
0
answers
207
views
proving quasi convexity of multivariable function
Given
an arbitrary $(N \times N)$ square matrix ${\bf X}$
a positive definite $(M\times M)$ matrix ${\bf T}$
a $(Q\times MN), Q< MN$ matrix ${\bf Z}$ consisting of only 1s and 0s where there is
...
4
votes
0
answers
293
views
When is the sum of a weak-$*$ closed convex cone and a subspace also weak-$*$ closed?
Let $X$ be a Banach space. Suppose $C \subset X^*$ is a convex cone and $V \subset X^*$ is a subspace, and suppose both $C$ and $V$ are closed in the weak-$*$ topology. Are there any general ...
- 195
3
votes
0
answers
749
views
Optimality condition for non-differentiable constrained convex optimization problem
(EDIT: see proof at the end) Consider the problem
$$
\min f(x) \; \text{s.t.} \; x\in D
$$
where $f(x)$ is convex but not differentiable, and $D$ is convex.
For differentiable $f$, we know that $x$ ...
- 300
5
votes
1
answer
704
views
What it is the volume of the unit ball section of the cone of positive definite matrices?
Let $PD_{n}$ be the cone of positive definite $n \times n$ real matrices and let $B$ be the unit sphere in $n \times n$ dimensions. What is the volume of $PD_{n} \cap B$?
EDIT: Let's assume that $B$ ...
- 108k
1
vote
0
answers
1k
views
Diagonal entries of a Cholesky factorization
Let $I$ denote an identity matrix, $E$ denote the all-one matrix of dimension $k\times k$ and $c$ some positive real number. Define $X=B(I-cE)B^T$ where $B$ is given by
$B:=\begin{pmatrix}
1 &\...
- 3,958
0
votes
0
answers
113
views
Sufficient optimality condition for a non-smooth quasiconvex problem
The result of relaxing to an integer program is the following optimization problem:
$$\min_{\textbf{x}} \sum_{i=1}^n \alpha_i h(x_i)\quad subject \; to \quad A\textbf{x} = \textbf{0}$$
where $\textbf{...
- 127
2
votes
1
answer
115
views
Convex interaction energy
Does anybody know examples of absolutely continuous probability measures $\mu_0,\mu_1$ on $\mathbb{R}^n$ with finite 2nd moments such that
$$
\frac{d^2}{dt^2}\left(\int_{\mathbb{R}^n\times \mathbb{R}^...
- 4,466
2
votes
1
answer
1k
views
Subgradient of Minimum Eigenvalue
Consider three $N \times N$ Hermitian matrices $A_0$, $A_1$, $A_2$. Consider the function
\begin{align}
f(t_1,t_2)=\lambda_{\text{min}}(A_0+t_1A_1+t_2A_2)
\end{align}
where $\lambda_{\text{min}}$ ...
- 6,210
2
votes
1
answer
459
views
Minimize a strictly convex quadratic function subject to linearly equality and nonnegativity constraints in finite time?
I am wondering if we can minimize a strictly convex quadratic function in finite time, subject to linearly equality and nonnegativity constraints.
Thanks!
- 980
1
vote
1
answer
1k
views
Lagrange multiplier and semidefinite programming
suppose we have a primal semidefinite programming. for finding its dual we use Lagrange multiplier $w_i$ for each semidefinite constraint. If the Lagrange multiplier be zero for one constraint what we ...
- 21.5k
2
votes
5
answers
3k
views
Distance between two sets
Let $A, B$ be two convex and closed subsets of $\mathbb{R}^n$. We would like to the minimum distance between these two sets. i.e., we want to find a solution for the following problem.
$$ \min \{||x-y|...
CommunityBot
- 1
3
votes
2
answers
759
views
How to minimize the Bregman divergence on a convex hull spanned from a set of vectors?
everyone.
It has been well known that the following minimization problem of a Bregman divergence with linear inequality
can be solved by successively projecting the current point to each constraint $\...
- 980
1
vote
0
answers
40
views
Searching for the maximum of a (strictly convex) two-dimensional distribution via maximization over a series of arbitrarily specified 1D intervals
Let $f$ be a strictly convex two-dimensional distribution with a maximum $M$ at some unknown position $(x_m,y_m)$. Starting from the origin, $(x_0,y_0) = (0,0)$, we need to find $(x_m,y_m)$, however ...
- 6,210
1
vote
1
answer
928
views
Block Covariance Matrix - Positive Definite? (Quadratic Optimization) [closed]
I have a covariance matrix C. I have then formulated an quadratic optimization problem that involves the following matrix in the quadratic form:
[ C C ]
[ C C ]
However, the quadratic solver ...
- 10.7k
1
vote
1
answer
277
views
Maximum Dispersion of a Connected Geometric Graph
Let $\left\{\mathbf{p}_1,\dots, \mathbf{p}_k\right\}$ be a set of points in $n$-dimensional Euclidean space, and let the second moment of these points be defined as:
$
U=\sum \limits_{i=1}^{k} ||\...
- 115
1
vote
0
answers
413
views
Extreme points of a set related to semidefinite cone
Let $X \in \mathbb{R}^{n \times n}$ be symmetric matrix. Consider the following set
$$
\mathcal{C} = \{ X: X \succeq 0, \quad 0 \le X_{ij} \le 1, \forall i,j\}
$$
What are the extreme points of this ...
- 1,731
-1
votes
1
answer
175
views
Regularized Gradient with respect to a matrix (with a specific structure)
Suppose we have a typical logdet function $\mathcal{L}$
$$
\mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - \mathbf{q}^T(\mathbf{A}^{-1} + \mathbf{S})^{-1} \mathbf{q},
$$
where $\...
CommunityBot
- 1
-1
votes
1
answer
954
views
Uniqueness of the solution to a quadratic problem [closed]
Consider a positive definite matrix $\boldsymbol H$, the known vectors ${\boldsymbol b}$ and ${\boldsymbol a}_i$. Now the minimization problem is casted with respect to the vector ${\boldsymbol x} $ ...
- 980
0
votes
1
answer
203
views
Eigenvalues of a given parametrized matrix.
Let $\mathbf{A}$ and $\mathbf{B}$ be two complex rank-one $N\times N$ positive semi-definite matrices. Let the matrix $\mathbf{C}$ be defined as
\begin{align}
\mathbf{C}=\left(\mathbf{I}*\frac{1}{\...
1
vote
0
answers
180
views
How to solve such an optimization problem efficiently？
Given a symmetric positive semi-definite matrix $\mathbf Y$ and a convex set $\mathcal M$ which is a subset of all symmetric positive semi-definite matrices (consider a simple case of $\mathcal M$： a ...
- 11
2
votes
2
answers
2k
views
Hessian of function of covariance matrices
Suppose we have a typical logdet function $\mathcal{L}$ with respect to a covariance matrix $\mathbf{A}$,
$$
\mathcal{L}(\mathbf{A}) = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - \mathbf{q}^T(\...
CommunityBot
- 1
2
votes
2
answers
306
views
Projection onto rotated box
Does anyone know if there is an efficient way to find the projection of an arbitrary point $z$ onto a rotated box, i.e. onto the set $\Omega=\{x \mid a \leq Ux \leq b\}$ where $U$ is a unitary matrix?
...
- 12.7k
3
votes
1
answer
774
views
maximizing convex quadratic form over the intersection of unit sphere and positive orthant
For a positive semi-definite matrix $C$, I want to find the solution to the following problem:
$\arg\max_{h\geq 0} h^T C h\quad$ s.t. $\quad h^T h\leq 1$
Any pointers are welcome.
CommunityBot
- 1
4
votes
1
answer
288
views
Equivalent method for maximum likelihood estimation of covariance parameters
My goal is to estimate the parameters of a covariance matrix $\Omega$, by maximizing the following log-likelihood function:
$$\log L(\vec\tau, \rho, \sigma \mid W, X) = -m\ln(\left | \Omega \right |) ...
1
vote
0
answers
526
views
minimizing the sum of euclidean norms
minimizing the sum of euclidean norms with box constraints
I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following ...
- 13
2
votes
0
answers
154
views
Maximizing an integral over a convex region
Let $C$ denote a compact, convex region in the plane containing the origin with unit area, and let $f$ be a probability distribution on $C$. Let $f^\ast$ denote the distribution that maximizes the ...
- 6,210