10
votes
Accepted
When is the duality gap of semidefinite programming (SDP) zero?
There is a more complicated theory of duality for SDPs that is exact: there is no 'extra condition' like Slater's condition. This is due to Ramana. (For another take on this involving SOS, see [KS12]...
- 1,801
9
votes
When is the duality gap of semidefinite programming (SDP) zero?
For the SDP in standard form
$$
\min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\},
$$
Slater's condition reduces to the existence of a positive ...
- 18.1k
6
votes
Accepted
On complexity of linear programming with quadratic equality/inequality constraints?
A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints. In particular, they prove:
Let $G$ be ...
- 5,772
6
votes
Accepted
Strongly polynomial time algorithm for shortest convex combination
It is known via a paper of De Loera, Haddock and Rademacher that a strongly polynomial time algorithm for finding a minimum norm point in a simplex implies a strongly polynomial time algorithm for ...
- 6,979
6
votes
Accepted
Restriction of a convex function to {0, 1}^n
Any real valued function $g$ defined on $\{0,1\}^n$ can be extended to a convex function over $[0,1]^n$ (it is called the convex closure). See Dughmi's nice survey. The implication for your question ...
- 6,979
4
votes
Accepted
Is the Chi-square divergence a Bregman divergence?
$\chi^2$-divergence is not a Bregman divergence.
I'll show it for sample size $n=1$. We would have
$$
(x-y)^2/x=f(x)-f(y)-f'(y)(x-y)$$
If $y=0$ and $x>0$ this says
$$x=f(x)-f(0)-xf'(0),$$
$$1=\...
- 4,475
4
votes
Accepted
Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length
Introduce variables $y_{hi}$ together with constraints
$y_{hi}=\sum_j (a_{hij} x_j + b_{hj})$ for all $h$ and $i$.
Introduce variables $z_h$ together with constraints
$z_h\ge y_{hi}$ for all $h$ and ...
- 5,772
4
votes
Accepted
When can a convex function induce submodularity?
The notion of sub-modularity you use is non-standard. Usually you consider set functions with domain $\lbrace 0, 1\rbrace^n$. But to answer your questions, the Lovász extension establishes the ...
- 56
4
votes
A Question on Convex Conjugate Duality for KL Divergence
An alternative proof:
Given that $\psi(p)=D_{KL}\left(p\,||q\,\right)$ is closed and convex we know that $\psi^{**}(p)=\psi(p)$.
One proposes $\psi^{*}(\lambda)=\log\left(\sum_{x}q(x)e^{\lambda_{x}}...
- 41
3
votes
Accepted
What is wrong with this procedure to convert quadratic programming to convex quadratic programming?
The constraint $x_i x_j = y_{ij}$ isn't convex. Indeed, even the simpler constraint $ab = 8$ isn't convex. Let $C = \{(a,b) : ab = 8\}$. Then $(4,2),(2,4) \in C$ but $(3,3) \notin C$.
- 14.3k
3
votes
Accepted
Properties of convex polytope of 0-1 matrices
Sasho already gave you a yes/no answer, but here's an actual convex combination for you: If $B_\ell$ is the $k \times k$ matrix which is $1$ when $|S_i \cap S_j| \ge \ell$ and zero otherwise, then $M =...
- 1,429
2
votes
Poly-time Algorithm for Non-Linear Optimization
In general, even approximating a global optimum of a quadratic program, the simplest case of a nonlinear program, is NP-Hard (http://web.cs.ucdavis.edu/~rogaway/papers/qp.pdf), not to mention finding ...
- 161
2
votes
An optimization problem
The problem as described is not convex, due to the nonconvexity of the constraint set. However, if you were to permit a relaxation, we could write your problem as
$\begin{array}{ll}
\max & \sum_{p\...
- 136
2
votes
Accepted
Can the ellipsoid method be used with a randomized separation oracle?
Yes, given your conditions the probability of a correct result is at least $(1-\epsilon)^T$.
This seems to follow from standard calculations, so maybe I am missing something. Here are the ...
- 9,595
2
votes
The Average-case Complexity of Simplex Algorithm
The first thing that comes to mind is "Smoothed Analysis" of Spielman and Teng: arxiv.org/pdf/cs/0111050.pdf. Their main result is Theorem 5.0.1, which bounds the expected (over "typical instances") ...
- 10.3k
1
vote
Solving non-linear programming with large number of variables
This is a quadratic program (QP). If the matrix $C$ where $(C)_{i,j} = c_{i,j}$ is positive semi definite, then the problem is convex. It seems that your problem should have non-empty interior, so if ...
- 226
1
vote
Accepted
Linear Programming Sensitivity to Matrix
Okay I think I have figured this out! I am going to assume we have primal and dual problems:
\begin{array}?
(P) &&\max& c^Tx &&& (D) &&\min& b^Ty \\
&&\text{...
- 226
1
vote
Linear Programming Sensitivity to Matrix
Let $u$ and $v$ be vectors of slack variables for the primal and dual, respectively. Thus $A x^* + u = b$ and $A^T y^* - v = c$. Then we can see that
\begin{equation}
\nu = c^T x^* = (Ay^*-v)^Tx^* = {...
- 226
1
vote
Accepted
Parametrized complexity of sparse optimization
This may be related to what you have in mind: arxiv.org/abs/0804.4666
- 4,011
1
vote
Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$
Consider the function $f(x, y) = 1 - e^{-(x + y)}$. Now $f(0, 0) = 0$, $f$ is increasing and concave, since $g(t) = -e^{-t}$ is concave.
But $f(1, 0) + f(0, 1) = 2(1 - e^{-1}) > 1 - e^{-2} = f(1, ...
- 551
1
vote
Brute force search algorithm for semidefinite programming (representation of spectrahedron)
The question is not very well defined. E.g., if the SDP has an optimal solution, then "searching" that one optimal solution is (trivially) enough to find a good approximate (in fact optimal) solution....
- 9,595
1
vote
When is the duality gap of semidefinite programming (SDP) zero?
There is a nice (I think....) characterization of when strong duality holds, or fails for {\em all} objective functions.
We say that the semidefinite {\em system}
$(P_{SD}) \,\, \sum_{i=1}^m x_i ...
- 11
1
vote
Optimal value of a semidefinite program
Here are a few more details for Suresh and Yoshio's answer. Following e.g. https://en.wikipedia.org/wiki/Semidefinite_programming, an SDP is of the form
$$\begin{array}{rl}
{\displaystyle\min_{X \in \...
- 9,595
Only top scored, non community-wiki answers of a minimum length are eligible