Questions tagged [convex-optimization]
Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes
793
questions
38
votes
2
answers
2k
views
How to make a sandwich from just one piece of bread?
I don't know how to go about such questions. It's not exactly my area, so maybe it is stupid, but curiosity is winning.
So I have a piece of bread $P$ of a really non-regular shape (let's make it ...
30
votes
5
answers
13k
views
Can all convex optimization problems be solved in polynomial time using interior-point algorithms?
Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
25
votes
2
answers
2k
views
An Interesting Optimization Problem
You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
20
votes
4
answers
4k
views
Is the pseudoinverse the same as least squares with regularization?
Given a linear system $Ax=b$, the pseudoinverse of $A$ is found as the matrix $A^+$ such that $x=A^+ b$ where $x$ solves the least squares problem $\min \| Ax - b \|^2 $ and $x \perp \mathcal{N}(A)$. ...
18
votes
8
answers
3k
views
When do people actually use the maximum entropy distribution?
One of the standard problems in convex optimization is the calculation of the maximum entropy distribution that satisfies some set of criteria. For example, if $\mathbf{x} \in \mathbb R^n$ is an ...
18
votes
3
answers
2k
views
Current state of the Komlos conjecture on vector balancing
Komlos Conjecture: the exists an absolute constant $K>0$ such that for all $d$ and any collection of vectors $v_1,\ldots, v_n\in \mathbb{R}^d$ with $\left\lVert v_i\right\rVert _2=1$ we can find ...
14
votes
1
answer
4k
views
Is KL divergence $D(P||Q)$ strongly convex over $P$ in infinite dimension
By KL divergence I mean $D(P||Q) = \int dP \log(\frac{dP}{dQ})$. I am looking for the conditions under which this strong convexity is true and possible references. I could not find an answer for ...
13
votes
2
answers
715
views
Is there a class of optimization problems more general than semidefinite programming?
I was TA-ing my convex optimization class and explaining that linear programs are a special case of second-order cone programs, which are themselves special cases of semidefinite programs. Is there ...
13
votes
4
answers
2k
views
Is group theory useful in any way to optimization?
For what I have seen, optimization uses a lot of linear algebra and convex analysis, but I have not seen any group theory being used, so I was curious about it.
Is group theory useful in any way to ...
13
votes
3
answers
814
views
Famous theorems that are special cases of linear programming (or convex) duality
The max flow-min cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any ...
13
votes
1
answer
1k
views
Minimize sum of $\ell_2$ norm and linear combination, on simplex
Let $\Delta_n := \{x \in \mathbb{R}^n | x \ge 0, \sum_{1 \le i \le n}x_i = 1\}$ be the $n$-simplex. For $a, b \in \mathbb R^n$, with $\Delta_n \not \ni a$, consider the problem of computing the ...
13
votes
1
answer
2k
views
An intuition for three different types of subgradients (proximal, regular, limiting)
I'm having a bit of difficulty getting my head around the different types of subgradients we're currently covering in a nonsmooth optimisation class I'm taking.
These subgradients are (assume $x \in$ ...
11
votes
2
answers
521
views
Convex hull of the Stiefel manifold with non-negativity constraints
Consider the Stiefel manifold
$$\mathrm{St}(n,k) :=\{X \in \mathbb{R}^{n\times k} : X^TX = I_k\},$$
where $I_k$ is the $k$-dimensional identity matrix. It is well known that
$$\mathrm{conv} \left( ...
11
votes
2
answers
376
views
Sum of squared nearest-neighbor distances between points in a square
Let $\square_2=\{(x,y): 0\leq x, y\leq1\}$ be the unit square in $\mathbb{R}^2$. Take $n>1$ points $P_1, \dots, P_n\in\square_2$.
Denote the distances $d_j=\min\{\Vert P_k-P_j\Vert: k\neq j\}$, ...
10
votes
4
answers
897
views
The distribution of the shortest path through $n$ points
In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small?
More ...
9
votes
1
answer
2k
views
Is There an Induction-Free Proof of the 'Be The Leader' Lemma?
This lemma is used in the context of online convex optimisation. It is sometimes called the 'Be the Leader Lemma'.
Lemma:
Suppose $f_1,f_2,\ldots,f_N$ are real valued functions with the same ...
9
votes
1
answer
301
views
Closedness of linear image of positive L1 functions
Let $\mathcal X$ be the Banach space of $L^1$ functions on some probability space, $\mathcal Y$ be some other Banach space, $T:\mathcal X\to \mathcal Y$ be some surjective continuous linear map, $\...
9
votes
1
answer
713
views
property of convex functions
I am able to give a proof to the following inequality for convex functions. Most likely this is well known, but I am unable to find a reference. I would appreciate if someone more knowledgeable in the ...
9
votes
2
answers
1k
views
Orthogonal representations of graphs
A faithful orthonormal representation of a graph $G=(V,E)$ on $n$ vertices $\{1,2,\dotsc,n\}$ is an assignment of unit vectors $v_1,v_2,...,v_n \in \mathbb{R}^d$ to the vertices of $G$ such that $\...
9
votes
2
answers
916
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 ...
9
votes
0
answers
898
views
Existence of barycenter
Let $(X,d)$ be a metric space. A barycenter of a Borel probability measure $\mu$ on $X$ is a minimizer of the function
\begin{equation}
\begin{split}
f \colon X & \to \mathbb{R}\\
x &\mapsto \...
8
votes
3
answers
514
views
Lower bound for spectral radius on $\operatorname{GL}(n,\mathbb{Z})$
Consider the group of matrices $G =\operatorname{GL}(n,\mathbb{Z})$ with integer entries and determinant $\pm 1$. For each matrix $D \in G$, the product of the eigenvalues of $D$ is equal to $\det D =\...
8
votes
4
answers
500
views
Abstract treatment of multivariate calculus relevant for optimization
After studying the basics of (convex) optimization, I've become convinced there's sometimes a conceptual benefit in thinking of quantities like gradients etc. in a coordinate-free way, and keeping ...
8
votes
2
answers
684
views
Bounding the spectral gap of a simple symmetric matrix
I have a seemingly innocent linear algebra problem that I cannot solve, and which I hope that you would kindly offer some insight into. Here is the description: Let $\mathbf{a} = (a_1, a_2, \dots, a_d)...
8
votes
2
answers
700
views
On the convexity of element-wise norm 1 of the inverse
Question first asked on math.stackexchange here: https://math.stackexchange.com/questions/317209/on-the-convexity-of-element-wise-norm-1-of-the-inverse
On the convexity of element-wise norm 1 of the ...
8
votes
3
answers
2k
views
Optimization problem with determinant as objective
Let $A$ be a given symmetric positive definite $N\times N$ matrix. I need to find a symmetric positive semi-definite matrix $S$ which is the solution to the following optimization problem
\begin{align}...
8
votes
1
answer
1k
views
Finding Toeplitz matrix nearest to a given matrix
For an arbitrary $N\times N$ Hermitian matrix $A$, I want to derive a Toeplitz matrix from $A$ such that the eigenvectors of both matrices have minimal change.
Specifically I want find the Toeplitz ...
8
votes
1
answer
1k
views
Uniqueness of a Solution for a Convex Optimization Problem
I have the following convex optimization problem:
$$\begin{array}{ll} \text{maximize}_{{f,g}} & \displaystyle\int_{\Omega} g^u{f}^{1-u}\mathrm{d}\mu\\ \text{subject to} & \displaystyle\int_{\...
8
votes
0
answers
192
views
Concavity of product and ratio of sums
Apologies if this question is not appropriate for MathOverflow. I have asked at Math.StackExchange without success.
Consider the function $f:\mathbb{R}^n\rightarrow \mathbb{R}$ defined as
$$
f(x)=\...
8
votes
0
answers
247
views
Quantum coupon collection: positivity of an alternating sum of matrices
It is well-known that in the classic coupon collecting problem (CCP), the expected waiting time is
\begin{equation*}
T_n(x_1,\ldots,x_n) = \sum_{k=1}^n (-1)^{k+1}\sum_{1\le i_1 < \cdots < i_k \...
7
votes
2
answers
441
views
Proving the set $\left\lbrace \frac{(x + y)^2}{\sqrt{y}} \leq x - y + 5, y > 0 \right\rbrace$ is convex
I have recently picked up a course on Convex Analysis in my spare time, but feel I'm not quite up to speed with the 'tricks' for proving a set is convex.
I have managed to prove this by moving all ...
7
votes
1
answer
377
views
Nondifferentiable convex function whose subdifferential admits a continuous selection
Is there a convex function $F$ that is not differentiable, but whose subdifferential admits a continuous selection, i.e. a continuous $g$ with $g(x) \in \partial F(x)$ for all $x$ in the domain?
In ...
7
votes
2
answers
432
views
Gaussian Surface Area of Positive Semidefinite Cone
Let $\mathbb{R}^n$ be the Euclidean space and $A \subseteq \mathbb{R}^n$ be a sufficiently regular set, e.g., one that has smooth boundary or is convex. We define the $\epsilon$-neighbor of $A$ in the ...
7
votes
1
answer
350
views
Is the solution of this optimization problem always positive semidefinite?
We are given a set of unit vectors $U \subset \mathbb{C}^n$ which spans the space $\mathbb{C}^n$. Given another unit vector $x$, consider then the following optimization problem:
$$ \sup_H \left\{ x^*...
7
votes
2
answers
251
views
What methods do we have to understand the spectrum of matrices with restricted entries?
Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"),
What is the largest possible spectral radius of a $...
7
votes
1
answer
396
views
Does the plane clustered to minimize sum distances^2 to clusters centers ( inertia / "K-means") produce hexagonal clusters / hexagonal lattice?
"K-means" is the most simple and famous clustering algorithm, which has numerous applications.
For a given as an input number of clusters it segments set of points in R^n to that given number of ...
7
votes
1
answer
196
views
How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?
This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...
7
votes
0
answers
400
views
Are there any characterizations of $C^2$ convex functions?
There are several characterizations of convex functions with the Lipschitz continuous gradient. If we already know that the function is of class $C^1$, then we have the following equivalent conditions:...
7
votes
0
answers
1k
views
Closed-form solution of a linear programming question
Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & \...
7
votes
0
answers
215
views
Characterizing matrices with rank constraint
Given matrix $M\in\Bbb\{0,1\}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M]=\{Q\in\Bbb\{0,1\}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad M-Q\in\Bbb\{0,1\}^{n\times ...
7
votes
0
answers
208
views
Numerical linear algebra: how to compute $B^TC^{−1}B$ efficiently
Hi,
my question is similar to this one. I have to compute $B^TC^{−1}B$, where $C$ is a strictly positive definite $n\times n$ matrix and $B$ is $n\times m$.
The matrix $C$ is huge ($n$ up to a ...
6
votes
2
answers
516
views
Why are $\Gamma_0$ functions called this
It is very common to indicate with $\Gamma_0(A)$ the set of lower semicontinuous convex functions from $A$ to $(-\infty,+\infty]$ with nonempty domain. An example of usage of this notation can be ...
6
votes
2
answers
458
views
Optimal polynomial approximation of rational function $\frac{1}{1-x}$
I've been working on the following polynomial approximation problem. I want to find the optimal Chebyshev approximation of the rational function $\frac{1}{1-x}$ on the real interval $x\in[-\rho, \rho]$...
6
votes
2
answers
2k
views
Computational complexity of unconstrained convex optimisation
What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...
6
votes
2
answers
307
views
Convex optimization with full subdifferential information
Can anyone direct me to any algorithms or theorems that describe the difficulty of solving a non-smooth convex optimization problem for the special case where the full subdifferential is available? ...
6
votes
1
answer
2k
views
SDP formulation of noisy low-rank matrix completion
Exact low rank matrix completion using nuclear norm minimization can be formulated as a semidefinite program (SDP). Following the notation in the paper, a convex problem for noisy matrix completion ...
6
votes
2
answers
2k
views
Wasserstein distance and the Kantorovich-Rubinstein duality
The only few references I could find on this topic are either amateur blog posts (http://n.ethz.ch/~gbasso/download/A%20Hitchhikers%20guide%20to%20Wasserstein/A%20Hitchhikers%20guide%20to%...
6
votes
1
answer
165
views
Subsets of a ball/sphere with the largest sum of distances
$\newcommand\R{\mathbb R}\newcommand\S{\mathbb S}$Let $B_d$ and $S_{d-1}$ denote, respectively, the closed unit ball and the unit sphere in $\R^d$. Let us say that a finite subset $F$ of $B_d$ is ...
6
votes
1
answer
659
views
If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?
I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...
6
votes
5
answers
712
views
Convex optimization over vector space of varying dimension
In all instances of convex optimization I know of, the dimension of the vector space is defined beforehand. Is there any work on convex optimization over a vector space of varying dimension?
For ...