On the polyhedral inapproximability of the SDP cone

Sebastian Pokutta's Blog 2018-03-12

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:

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)
Approximation Limits of Linear Programs (Beyond Hierarchies) Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer To appear in Proceedings of FOCS (2012)
On polyhedral approximations of the second-order cone Aharon Ben-Tal, Arkadi Nemirovski Mathematics of Operations Research, vol. 26 no. 2, 193-205 (2001)