Sebastian Pokutta's Blog

Mathematics and related topics

Posts Tagged ‘optimization

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 BraunSamuel Fiorini, Serge MassarDavid SteurerHans 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

Informs Annual Meeting 2011

leave a comment »

I plan to update this post in the course of the following days and I would have also loved to send out a few more tweets, especially now that I have this fancy twitter ribbon, but I have hard time connecting to the internet at the convention center.

Day 1: So the first day of the Informs Annual Meeting is almost over… What were my personal highlights from today? I listened to quite a lot of talks and most of them were really good so that I feel that it would not be fair to mention only a few selected ones. One personal highlight that I would like to mention though is the Student Paper Prize that Dan Dadush from Georgia Tech got for his work together with Santanu Dey and Juan Pablo Vielma on the Chvátal-Gomory closure for compact convex sets. This result is really amazing as it provides deep insights into the way of how cutting-plane procedures work when applied to non-linear relaxations. Congratulations Dan! Below is a picture of the three taken at the session.

20111113-160856.jpg

Day 2: The second day of the Informs meeting was great. In particular I loved the integer optimization session (for apparent reasons) and had some extremely intense and deep discussions with some of my colleagues – for me this is the most important reason to go to a conference: dialog. One such discussion was with David Goldberg from GATech about the fundamental concepts in optimization/math/reasoning that completely redefine your thinking once fully understood/appreciated (this includes concepts such as “equality”, “proof by contradiction”, “induction”, or “diagonalization”). I will have a separate blog post together with David on that. If you think there is a concept that completely changed your thinking, please email us or drop us a line in the comment section. I am off to my talk now – more later…

Day 3: I actually did not see too much of the third day as I had to leave early.

All in all, Informs 2011 was a great event, in particular to meet all the people that are usually spread all over the US. I was actually quite happy to see that there were also quite a lot of Europeans at the conference

Written by Sebastian

November 13, 2011 at 9:09 pm