26

Luca, since a year has passed, you probably have researched your own answer. I'm answering some of your questions here just for the record. I review some Lagrangian-relaxation algorithms for the problems you mention, and sketch the connection to learning (in particular, following expert advice). I don't comment here on SDP algorithms. Note that the ...


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 ...


16

The ellipsoid method and interior point methods can be extended to solve SDPs as well. You can refer to any standard-texts on SDPs for details. Here's one: Semidefinite Programming. Vandenberge and Stephen Boyd, 1996.


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-...


15

There are many examples in quantum information and computation where quantities of interest are expressible as optimal values of semidefinite programs. Here are a few beyond those mentioned in the question: The optimal probability to correctly distinguish states chosen from a known ensemble is expressible as an SDP. (See arXiv:quant-ph/0205178 .) The ...


13

SDPs usually provide relaxations, so for a minimization problem you'll get a lower bound. The Lovasz theta function does provide such a lower bound on chromatic number (see wiki). Upper bounds can be provided by rounding schemes (constructive or otherwise). In general, if you have an upper bound $U$ on the integrality gap of the SDP, you can scale the ...


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 ...


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


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 ...


10

Fixed Point Logic $+$ Counting (FPC) is believed to capture most of the $P$ solvable problems. Anderson, Dawar and Holm 2015 [1]showed that optimization of linear programs is expressible in FPC. Dawar and Wang 2016 [2]showed that The FPC implementation of the ellipsoid method extends to semidefinite programs (subject to some technical conditions).


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 ...


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 ...


7

Check Chapter 6 in the book "The Design of Approximation Algorithms" by Williamson and Shmoys. The book is available on-line here: http://www.designofapproxalgs.com/


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 ...


5

The new SDP that you obtain by replacing minimize by maximize is not necessarily closely related to the first one. Right now the value is infinity, and if you replaced 0 by $Q_a$ on the right side of the constraint, the value is always going to be 0 or infinity (if it's not 0, you can just multiply any solution with positive value by an arbitrary constant, ...


5

I don't know if all convex problems are in P, but I can answer a related question: nonconvex optimization is NP-hard. See "Quadratic programming with one negative eigenvalue is NP-hard".


4

There is a nice book by Gartner and Matousek on SDPs and their applications to approximation algorithms. It covers a lot with the added benefit of giving a good introduction to the theory of semi-definite programming. See http://books.google.com/books/about/Approximation_Algorithms_and_Semidefinit.html?id=5QeLPOvIpNUC


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 ...


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

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

To the best of my knowledge, there is no such study; furthermore, without some nontrivial advances in the technology of sum-of-squares (SOS) problems, it is not currently clear what the immediate benefit of such a study would be. (I'll focus on the SOS connection since that, as far as I know, is the best way to solve these general quartic problems.) This ...


2

There's this survey: http://ttic.uchicago.edu/~madhurt/Papers/sdpchapter.pdf which has a focus on the hierarchies of convex programming. It has Max-Cut, Sparsest-Cut, coloring, hypergraph independent set, knapsack.


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

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

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