# Tag Info

18

A typical problem is MaxCut: output a cut in a graph that (approximately) maximizes the number of edges cut. Goemans and Williamson showed an SDP approximates the value of MaxCut to within a factor at least 0.878. Recently, Chan, Lee, Raghavendra, and Steurer showed that for a natural linear encoding of the MaxCut problem, all polynomial size LPs achieve ...

15

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 \succeq 0, X_{11} = \ldots = X_{nn} = 1\}$, i.e. the set of Gram matrices of $n$ unit vectors. This is, for example, the feasible region for the Goemans-...

12

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 based" hardness. That is, the UG-hardness result have the following flavor - "if the unique games conjecture is true then for problem $P$ no algorithm can get a ...

12

I'm not familiar with details of the ellipsoid method specifically for semi-definite programs, but even for linear programs, analysis of the ellipsoid method is pretty subtle. First, one needs to bound the number of iterations of the ideal ellipsoid algorithm. Let $E_i$ be the ellispoid used in the $i$th iteration of the ellipsoid algorithm, and let $c_i$ ...

12

For many combinatorial optimization problems (for instance Max-Cut), semidefinite programming yields much stronger relaxations than the LP relaxation of IP formulations. This allows the design of approximation algorithms, and of exact algorithms which are more efficient than their linear counterparts due to the better quality of the bounds. Examples can be ...

10

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].) To be honest, I've never tried to understand these papers and would be happy if someone dumbed them down for me. One notable consequence of this work is ...

9

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 definite $X\succ 0$ that satisfies the affine constraints $\mathrm{tr}(A_i^T X) = b_i$. I would guess this is satisfied for any SDP you can find in the ...

9

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 Nullstellensatz as stated in the question is indeed its special case. Other comments asked for lecture notes with a proof of the Positivstellensatz, and as I do not ...

5

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 leading eigenvector of a symmetric matrix". So spectral algorithms that use the latter as a starting point can be interpreted as SDP rounding algorithm. To see that ...

5

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. The problem in the post is Is there a permutation matrix in the span of a given set of matrices? This is essentially the same as Is there a permutation ...

3

Regarding the problem of computing the diameter of a polytope presented as the intersection of halfspaces, the problem is NP-hard in general, and also NP-hard to approximate within any constant factor, see Brieden's paper and references therein. I think for centrally symmetric polytopes, an SDP gives an $O(\sqrt{\log m})$ approximation where $m$ is the ...

3

See the following paper. There may have been other developments since then. Maximum Quadratic Assignment Problem, Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko, ICALP 2010 http://www.cs.princeton.edu/~kmakaryc/pdf/maxqap.pdf

3

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 polynomial (or sum of squares of polynomials) always has nonnegative pseudo-expectation. Also, if we have a system of polynomial equations $\{p_i = 0\}$ of degree at ...

3

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

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 be no SDP relaxations for exact Max-CUT of size $2^{n^c}$ for some $c < 1$. I think this means there can be no SOS proof of degree $n^c$, and hence there ...

1

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 A_i \preceq B$ is badly behaved if here is an objective function $c$ for which the SDP $\sup c^T x \,\, s.t. \,\, \sum_{i=1}^m x_i A_i \preceq B$ has a finite ...

1

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. Similarly, any algorithm that solves the SDP in finite time will find a "good approximate solution" while considering only finitely many points of the SDP. ...

1

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 \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \quad\text{subject to}\\ & \langle A^{(k)}, X \rangle_{\mathbb{S}^n} \leq b_k, \quad (\forall k \...

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