Questions tagged [convex-optimization]
The convex-optimization tag has no usage guidance.
91
questions
22
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,591
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,782
10
votes
2
answers
587
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 ...
- 203
10
votes
3
answers
742
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
559
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.6k
10
votes
1
answer
1k
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, \...
- 209
9
votes
1
answer
735
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 ...
- 425
8
votes
1
answer
583
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
218
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,195
7
votes
3
answers
826
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 ...
7
votes
0
answers
116
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
158
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
3k
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
917
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
282
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
168
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,195
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
1
answer
163
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
101
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
490
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
193
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
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,591
4
votes
1
answer
188
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
67
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
129
views
Convex optimization: is it possible to find solutions that are exactly feasible and approximately optimal in polynomial time?
In Nemirovxki's lecture notes on interior point methods, I found the following.
He defines an approximate solution as satisfying the following, for any given $\epsilon>0$:
that is: the ...
- 2,078
4
votes
0
answers
132
views
Which variant of the ellipsoid method was used for the Santa Claus problem?
As one of the steps in the article The Santa Claus problem (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the dual):
\begin{align*}
&\...
- 91
4
votes
0
answers
106
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
4
votes
0
answers
102
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,945
4
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 ...
- 386
3
votes
1
answer
109
views
Strongly polynomial time algorithm for shortest convex combination
Problem: Let $S$ be a finite set of vectors. Let $C$ be their convex hull. Compute $\operatorname{argmin}_{x \in C} \|x\|$.
Reference 1 gives an algorithm for this problem that is finite-time (Section ...
- 652
3
votes
1
answer
207
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.8k
3
votes
1
answer
798
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
941
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
210
views
Can the ellipsoid method be used with a randomized separation oracle?
Suppose we are trying to solve the following optimization problem:
$$
\text{maximize } ~~ c\cdot y
\\
\text{subject to } ~~ y\in S
$$
where the region $S$ is described by an exponential number of ...
- 91
3
votes
1
answer
234
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}\...
- 265
3
votes
1
answer
115
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.4k
3
votes
0
answers
111
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.4k
3
votes
0
answers
162
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,\...
- 265
3
votes
0
answers
135
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 \...
- 141
3
votes
0
answers
88
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?
- 832
3
votes
0
answers
188
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,224
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,393
3
votes
0
answers
272
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
3
votes
1
answer
95
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 ...
- 199
2
votes
1
answer
237
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
258
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
2
answers
114
views
Linear Programming Sensitivity to Matrix
Consider a linear program in the following standard form:
\begin{align*}
&\max c^T x &\\
&\mbox{subject to:}\\
&A x \preceq b\\
&x \succeq 0
\end{align*}
Its dual is
\begin{align*}...
- 575