# Tag Info

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 \... 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 ... 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]... 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 ... 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 ... 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 ... 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. ... 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 ... 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$. 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 ... 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 ... 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.... 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 ...
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 \...