Sebastian Pokutta's Blog

Mathematics and related topics

On the polyhedral inapproximability of the SDP cone

with 2 comments

I was at HPOPT in Delft last week which was absolutely great and I would like to thank Mirijam Dür and Frank Vallentin for the organization and providing us with such an inspirational atmosphere. I talked On the complexity of polytopes and extended formulations which was based on two recent papers (see [1] and [2] below) which are joint work with Gábor Braun, Samuel Fiorini, Serge Massar, David Steurer, Hans Raj Tiwary and Ronald de Wolf. One of the question that came up repeatedly was the statement for the inapproximability of the SDP cone via Linear Programming and its consequences. This is what this brief post will be about; I simplify and purposefully imprecise a few things for the sake of exposition.

For a closed convex body K containing 0 there is a natural notion of appoximating K within a factor of (1+ \epsilon) with \epsilon > 0. We can simplify define (1+\epsilon) K = \{ (1+\epsilon) x \mid x \in K\}. This notion is compatible with the notion of approximating the maximum value of a (say, nonnegative) linear objective from the outside over K within a factor of 1+\epsilon. For this observe that

\frac{\max_{x \in (1+\epsilon) K} cx}{\max_{x \in K} cx} = \frac{\max_{x \in K} (1+\epsilon) cx}{\max_{x \in K} cx} \leq (1+\epsilon)

What one can show now is that there exists a pair polyhedra P \subseteq Q where P = COR(n) = conv\{bb^T \mid b \in \{0,1\}^n\} is the correlation polytope (also called boolean quadric polytope) and Q is given by the valid inequalities <2 diag(a) - aa^T,x> \leq 1 for all a \in \{0,1\}^n. This pair of polyhedra has the property that for any other polyhedron T so that P \subseteq T \subseteq (1+\epsilon) Q it follows that one needs a super-polynomial number of inequalities in any extended formulation of T and \epsilon can be here as large as O(n^\beta) with \beta < 1/2. This follows from a modification of Razborov’s well-known rectangle corruption lemma.

On the other hand, there exists a spectrahedron S \in \mathbb R^{n \times n} sandwiched between P and Q, i.e., P \subseteq S \subseteq Q where S is the projection of an affine space intersected with the cone of n+1 \times n+1 psd matrices. In particular P \subseteq S \subseteq (1+\epsilon)S \subseteq (1+\epsilon)Q. Now, if K is a polyhedron so that S \subseteq K \subseteq (1+\epsilon) S it follows that K needs a super polynomial number of inequalities in any extended formulation for any \epsilon = O(n^\beta) with \beta < 1/2. In consequence, there exists a spectrahedron S with small SDP extension complexity that cannot be well approximated by any polyhedron. If now the SDP cone could be approximated well (in sense similar to the one for the SOCP cone, see [3]), so could this particular spectrahedron. This is inapproximability is in contrast to the case of SOCP cone which can be approximated arbitrarily well with a polynomial number of inequalities (see [3] for a precise statement). (Note that we can add the nonnegativity constraints to obtain the same statements for polytopes in order to resolve unboundedness issues.)

Concerning the consequences of this statement. First of all it suggests that the expressive power of SDPs can exponentially stronger than the power of linear programs, in the sense that while you need an exponential number of inequalities, a polynomial size SDP formulation can exist. Moreover, it might suggest that for some optimization problems, the optimal approximation ratio might not be attainable via linear programming but with semidefinite programming. What should be also mentioned is that in practice many SDPs can be typically solved rather well with first-order methods (there were several amazing talks at HPOPT discussing recent developments).

References:

  1. Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds
    Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf
    Proceedings of STOC (2012)
  2. Approximation Limits of Linear Programs (Beyond Hierarchies)
    Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer
    To appear in Proceedings of FOCS (2012)
  3. On polyhedral approximations of the second-order cone
    Aharon Ben-Tal, Arkadi Nemirovski
    Mathematics of Operations Research, vol. 26 no. 2, 193-205 (2001)

Written by Sebastian

June 22, 2012 at 7:58 am

Posted in Mathematics and Optimization

Tagged with , , , , , ,

«

2 Responses

Subscribe to comments with RSS.

  1. […] issue. Then we need to see how far the logic of this paper (and a FOCS 2012 followup noted on the blog of my Tech colleague Pokutta) extends to alternative formulations. But first we also need to note […]

    How Not To Prove Integer Factoring Is In P « Gödel’s Lost Letter and P=NP

    September 26, 2012 at 3:15 pm

    Reply

  2. You need to read this paper (perhaps the best paper on the Complexity of the SDP):

    The author is M.V. Ramana, and the paper appeared in Math Programming (1997), Vol 77, p. 129-162.

    Title: An exact duality theory for semidefinite programming and its complexity implications

    You can check with Pablo Parrilo at MIT, who has worked with the author (M.V. Ramana).

    Sam

    October 11, 2012 at 1:16 pm

    Reply

Leave a comment