Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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]...
Ryan O'Donnell's user avatar
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 ...
Sasho Nikolov's user avatar
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 ...
Gamow's user avatar
  • 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 ...
Chandra Chekuri's user avatar
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 ...
Chandra Chekuri's user avatar
4 votes

Deciding whether a convex region is empty

Warning: As one of the comments points out, the sum of squares is not necessarily convex, so the hardness reduction suggested below does not work. The problem still lies in $\exists\mathbb{R} \...
user67422's user avatar
  • 144
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 ...
Gamow's user avatar
  • 5,772
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=\...
Bjørn Kjos-Hanssen's user avatar
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}}...
nosferatttu's user avatar
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$.
Yuval Filmus's user avatar
  • 14.5k
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 =...
Andrew Morgan's user avatar
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") ...
Aryeh's user avatar
  • 10.6k
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\...
walkerbacker's user avatar
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 ...
Neal Young's user avatar
  • 10.8k
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 ...
NaturalLogZ's user avatar
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{...
NaturalLogZ's user avatar
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^* = {...
NaturalLogZ's user avatar
1 vote
Accepted

Parametrized complexity of sparse optimization

This may be related to what you have in mind: arxiv.org/abs/0804.4666
Mahdi Cheraghchi's user avatar
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, ...
Antti Röyskö's user avatar
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 ...
district9's user avatar
  • 111
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....
Neal Young's user avatar
  • 10.8k
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 \...
Neal Young's user avatar
  • 10.8k

Only top scored, non community-wiki answers of a minimum length are eligible