Questions tagged [convex-optimization]
The convex-optimization tag has no usage guidance.
82
questions
21
votes
1
answer
3k
views
Solving semidefinite programs in polynomial time
We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (...
- 1,571
14
votes
2
answers
1k
views
0-1 Linear Programming: computing the Optimal Formulation
Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in ...
- 6,615
10
votes
3
answers
677
views
When is the duality gap of semidefinite programming (SDP) zero?
I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold?
For example, when one goes back and forth ...
- 1,443
10
votes
1
answer
542
views
Convexity and efficient algorithms.
[Edit 21 July 2011: I edited the question to ask for more examples]
This question is asking for documented discussion of or more examples of a heuristic observation.
Some mathematical problems that ...
- 12.3k
9
votes
2
answers
496
views
What can be solved with semidefinite programming that can't be solved with linear programming?
I'm familiar with linear programs in that they can solve problems with linear objective functions and linear constraints. But what can semidefinite programming solve that linear programming can't? I ...
- 193
9
votes
1
answer
684
views
Information theory and convex optimization
I'm taking a graduate level course in information theory and I'm constantly struck by how much convex optimization there is in this subject. However, the proofs seem to shy away from using the full ...
- 263
8
votes
2
answers
4k
views
A Question on Convex Conjugate Duality for KL Divergence
The convex conjugate of a function, say, $f:X\mapsto \mathbb{R}$ is a function $f^*:X^*\mapsto \mathbb{R}$ defined as
$$f^*(x^*):=\sup_{x\in X} ~\langle x, x^*\rangle-f(x),$$ where $X^*$ is the ...
- 415
8
votes
1
answer
553
views
Is the feasible region of this SDP polyhedral?
We have a semidefinite program (SDP) whose feasible region contains only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral?
We believe this to ...
- 251
8
votes
2
answers
212
views
Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$
Consider a rational polytope $P$ that is defined by means of a separation oracle. That is, $P$ can be described implicitly as $P = \{x \in R^k: Ax \leq b, A \in Z^{m \times k}, b \in Z^m \}$, but ...
- 1,175
8
votes
1
answer
864
views
Is convex optimisation in P?
Consider a convex optimisation problem in the form
$$\begin{align}
f_0(x_1, \ldots, x_n) &\to \min \\
f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m
\end{align}$$
where $f_0, f_1, \...
- 189
7
votes
0
answers
115
views
Has compressed sensing been generalized to convex optimization problems?
Has the theory of "compressed sensing" been generalized to any classes of convex optimization problems? I need to analyze a problem of the type
$$\min ||x||_0, ~~~~ \mbox{ subject to } ~~~g(x) \leq 0$$...
- 71
7
votes
0
answers
157
views
SVM - running time for detecting if data is linearly separable?
If my understanding is correct, one way to check if a set of $m$ data points is linearly separable is to use support vector machines to find a maximum margin hyperlane for separating the data; the ...
- 71
7
votes
0
answers
2k
views
Time complexity of standard semidefinite programming solvers
I am interested in exact scaling of the ellipsoid method and interior point methods for solving SDPs.
(I am not interested in algorithms like multiplicative weights updates method.)
- 121
7
votes
0
answers
129
views
What's the state of the art for matrix nuclear/trace norm optimization
I am interested in simple matrix optimizations with nuclear/trace norm:
$\min_X \left(f(X) + \|X\|_*\right)$
where $\|X\|_*$ stands for the trace norm of the matrix $X$, and $f$ is a convex smooth ...
- 71
6
votes
1
answer
858
views
Analytic solutions in semidefinite programming (SDP)
From my experience in the application of semidefinite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example,...
6
votes
1
answer
278
views
Complexity of max problem
Consider the problem
$\max_x \;||x||_2\\ x\in P\subseteq \mathbb{R}_{\geq 0}^n$
where $||\cdot||$ is Euclidean 2-norm and $P$ is a polytope in positive orthant of $\mathbb{R}^n$. Is this problem ...
- 253
6
votes
1
answer
164
views
Bounds on the size of the solution of a quadratic program
I am interested in a quadratic program of the form
$$ \min x^T Q x $$
$$s.t.$$
$$ Ax \leq b $$
where $x$ is a vector with $n$ entries, the size of the maximal entry in $Q, A$, and $b$ is $\varphi$, $...
- 1,175
6
votes
1
answer
1k
views
The Average-case Complexity of Simplex Algorithm
I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint. I know that Smale did ...
- 451
6
votes
3
answers
806
views
Neural Networks: what's the point of learning features that don't linearly separate?
Unless I'm mistaken, deep neural networks are good for learning functions that are nonlinear in the input.
In such cases, the input set is linearly inseparable, so the optimisation problem that ...
6
votes
1
answer
155
views
Brute force search algorithm for semidefinite programming (representation of spectrahedron)
I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for ...
- 451
6
votes
0
answers
99
views
Looking for an easy/pedantic exposition of Renegar's famous result on polynomial optimization
In September $1989$, Renegar had this famous sequence of 3 papers titled, "On the Computational Complexity and Geometry of the First-order Theory of the Reals, Part I/II/III". I was wondering if ...
- 1,443
5
votes
1
answer
485
views
Gradient descent-like optimization on a convex landscape with noisy sampling
We have a strictly convex function $f(x,y)$ with a global minimum at $p_{min}$.
The goal is to approximate the minimum.
E.g.
$$f: [0,\pi]^2 \to \mathbb{R}$$
$$f(\theta,\phi) = t_1 \sin \theta + t_2 ...
- 75
4
votes
2
answers
190
views
On facets of 01-polytope
$0,1$-polytopse are fundamental objects in combinatorial geometry and comvex optimization. I am interested in the size of binary representation of hyperplanes to use in the framework of computational ...
- 549
4
votes
1
answer
179
views
Restriction of a convex function to {0, 1}^n
Suppose I have a real-valued convex function $f$ on the unit hypercube $[0,1]^n$, and let $\bar{f}$ be its restriction to the integer points $\{0,1\}^n$. Does $\bar{f}$ satisfy any properties, or can ...
- 43
4
votes
1
answer
66
views
Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length
If $a_{ij}$ is an $m \times n$ matrix of real numbers, and $b_j$ are $n$ more real numbers, then
$$\max_i \sum_j (a_{ij} x_j + b_j) \qquad (\ast)$$
is a convex piecewise linear function of $(x_1, \...
- 361
4
votes
1
answer
200
views
Active learning for inferring a convex optimization formulation
I was wondering if anybody knows of any relevant references on the general topic of active learning for gradually inferring/updating a convex opt. formulation.
As a specific example, I am thinking of ...
4
votes
0
answers
100
views
Bounding a Solution of an SDP
It's common for convex optimization procedures to require a bounded region containing an optimal solution, either as input, like the initial ellipsoid of the ellipsoid method, or for run time bounds, ...
- 41
3
votes
2
answers
3k
views
Minimizing the maximum dot product among k unit vectors in an n-dimensional space
Suppose, we are given a set of $k$ unit vectors $v_1,\ldots,v_k$ in $\mathbb{R}^n$. Consider all possible dot products among distinct vectors $v_i \cdot v_j$, where $i \ne j$. Let,
$$\alpha = \max_{1 ...
- 1,571
3
votes
1
answer
183
views
On complexity of linear programming with quadratic equality/inequality constraints?
Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ ...
- 12.5k
3
votes
1
answer
796
views
Objective function for stochastic optimization
Stochastic Optimization problems in general deals with random variables in the 'loss function'.
Incase of a Deterministic optimization problem with basic objective $\parallel Ax-b \parallel_2^2$, we ...
- 33
3
votes
1
answer
873
views
Maximizing a convex function with linear constraints
I have the following optimization problem:
$$
\arg\max_{\{\phi_p\}_{p=1}^M}\sum_{i=1}^N \max_{p=1,\ldots,M}\{\phi_p a_{ip}\}
\mbox{ such that }\sum_{p}\phi_p\leq 1\mbox{ and }0\leq \phi_p\leq 1,\...
- 33
3
votes
1
answer
229
views
An optimization problem
I am considering the following optimization problem. Let $P$ be a set of $n$ points in $\mathbb{R}^d$
maximize $\sum_{p\in P}\vert\langle \Vert p\Vert p, \hat{x}\rangle\vert$ subject to $\Vert\hat{x}\...
- 267
3
votes
1
answer
108
views
Parametrized complexity of sparse optimization
Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so ...
- 10.1k
3
votes
0
answers
59
views
Extremal Ellipsoids
I'm considering the following problem.
Given a collection of $m$ ellipsoids in $R^n$, compute the maximum volume ellipsoid inscribed in their intersection.
In Boyd & Vandenberghe, Convex ...
- 181
3
votes
0
answers
101
views
SVM perturbation bounds
Let $B$ be the unit ball of $\mathbb{R}^d$. Suppose that $x_1,\ldots,x_n$ are vectors in $B$ with labels $y_i\in\{-1,1\}$. We say that $w\in B$ separates this labeled set with margin $\gamma$ if $y_i(...
- 10.1k
3
votes
0
answers
101
views
Hessian of non differentiable convex function
The motivation of the question is the following:
Let $P$ be a set of $n$ points in $\mathbb{R}^d$. Consider the following objective(convex and differentiable) function $f:\mathbb{R}^d\rightarrow [0,\...
- 267
3
votes
0
answers
75
views
Gradient descent step size for strongly convex functions
Suppose we are optimizing a strongly convex function $f(x)$ via gradient descent $x_{t+1} = x_t - \eta_t \nabla f(x_t)$. By strongly convex I mean that $f(x+h) \ge f(x) + \langle \nabla f(x), h \...
- 131
3
votes
0
answers
81
views
First-order methods for solving SDP with geometric convergence or better
Is there any first-order method that can solve general SDP in a geometric (linear) rate? or super-geometric (super-linear) rate?
- 792
3
votes
0
answers
98
views
Software that generates and solves a Lasserre hierarchy
Suppose L is a linear program that is a relaxation of some 0/1 integer linear program ILP. There is a systematic way to construct SDP relaxations of ILP that are tighter than L by using a Lasserre ...
- 1,935
3
votes
0
answers
187
views
Computing the convex hull of several polyhedra
Let $K_1,..., K_m$ be a set of $m$ polyhedra, with $K_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities.
How easy is it to compute an ...
- 1,214
3
votes
0
answers
82
views
What is the state-of-the-art asymptotics for convex optimization?
I've got a convex program of the form:
Choose $v \in \mathbb{R}^n$ to minimize $vAv^T$ subject to $O(n)$ linear contraints (including $v \ge 0$). $A$ is a square binary matrix.
What algorithm gives ...
- 2,313
3
votes
0
answers
2k
views
Linear programming optimization problems using parallel algorithms
I'm looking for methods and algorithms for solving linear programming algorithms, characterized by up to 20 variables but up to thousands of constraints in a parallel way. There are several approaches ...
- 376
3
votes
0
answers
270
views
Maximizing a convex function where the objective function is separable but the search space is not
The problem statement is
Given convex functions $f_i$ over $X$, find $$\arg\max_{x\in X} \sum_i f_i(x)$$
Does this kind of problem structure allow one to use specific strategies to solve the ...
- 261
2
votes
1
answer
193
views
Is the Chi-square divergence a Bregman divergence?
Is the Chi-squared divergence $\sum_{i} \frac{(x(i)-y(i))^2}{x(i)}$ a Bregman divergence? I.e., can it be written as
$\phi(x) - \phi(y) - \langle\phi'(y),x-y\rangle$?
If so, what is the potential ...
- 33
2
votes
1
answer
229
views
When can a convex function induce submodularity?
Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which ...
- 644
2
votes
1
answer
927
views
On the stopping criterion of coordinate descent method
I am trying to implement the coordinate descent method to solve the dual of linear SVM problem, but blocked at the stopping criterion.
Consider the optimization problem
\begin{equation}
\min f(\...
- 241
2
votes
1
answer
281
views
Linear programming, a non standard handling of absolute value
This is really a basic (undergrad) question in LP but still i would like to
clarify it for myself to be sure. I have a minimization problem from the sort $\min \sum_i |x_i|$ s.t $Ax \le b$.
I've seen ...
- 323
2
votes
0
answers
30
views
Finding shortest calculation of the sum of a subset of a group, given sums for other previously summed subsets
Say $S=\{g\in G\}$ is a set of elements in an abelian group $G$ whose group operation $(+)$ is expensive to compute. Given a subset $T\subset S$, we want to compute the sum of $T$'s elements, $\...
- 121
2
votes
0
answers
65
views
Has Khachiyan/Porkolob's convex integer optimization been implemented?
Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
- 12.5k
2
votes
0
answers
160
views
Non-Linear Programming with \min operator in the constraint
Can the following non-linear program be solved in polynomial time? $c_{ij}$'s are constants and known. Each $c_{ij}$ is either -1 or 1.
\begin{align}
\text{maximize } &\sum_{i,j=1}^{m,n} c_{ij}...
