Skip to main content
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
9 votes
Accepted

Positivstellensatz and sum of squares method

As already noted in the comments, the question is based on a misunderstanding; the actual Positivstellensatz is a stronger statement than Artin’s theorem on nonnegative polynomials, and the real ...
Emil Jeřábek's user avatar
6 votes
Accepted

How is SDP an extension of spectral algorithms?

This is not a precise statement so it's hard to give a precise answer, but I think what is meant is that SDPs are powerful enough to express both linear programs, and problems like "compute the ...
Sasho Nikolov's user avatar
5 votes

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

Theorem. The problem in the post is NP-hard, by reduction from Subset-Sum. Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op. Here is the intuition. ...
Neal Young's user avatar
  • 10.8k
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

SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?

We don't have integrality gaps even for Max-CUT, even for degree 4. See Barak and Steurer's notes, at the end. You might be interested in Lee Raghavendra Steurer '14. They seem to be saying there can ...
Whosyourjay's user avatar
3 votes
Accepted

Approximation algorithm for balanced bipartite independent set?

There is a nice reduction by Chalermsook et al. (WG 2020) that can give the kind of approximation you want. I'll describe it below in terms of finding balanced complete bipartite subgraph (biclique) ...
Pasin Manurangsi's user avatar
3 votes
Accepted

Max-k-cut with negative edge weights

There is no approximation algorithm for the problem of maximizing $\sum_{(i,j)\text{ is cut}} w_{ij}$, since it's even NP-hard to determine whether the optimal value is positive. However, there is a ...
Yury's user avatar
  • 3,909
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

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