15 votes
Accepted

Is the feasible region of this SDP polyhedral?

No, even if there is a finite number of feasible rank-1 matrices, the feasible region of an SDP does not have to be polyhedral. A spectrahedron you see all the time in applications is $S_n = \{X: X \...
user avatar
12 votes

Unique Games versus SDP procedures

As far as I know (and can interpret your question) no such result is known. There are two reasons: 1) Generally unique games hardness results (as well as NP hardness result) do not yield "instance ...
user avatar
  • 3,721
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]...
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 ...
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 ...
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 ...
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. ...
user avatar
  • 8,213
3 votes
Accepted

What is a "level-r pseudo expectation functional"?

The degree $r$ pseudo-expectation operator operates on polynomials of at most degree $r$. Since the pseudo-expectation operator is positive semidefinite, we're guaranteed that the square of a ...
user avatar
  • 2,295
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$.
user avatar
  • 14.1k
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 ...
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 ...
user avatar
  • 3,844
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....
user avatar
  • 8,213
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 ...
user avatar
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 \...
user avatar
  • 8,213

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