On Polyhedral Approximations of the Positive Semidefinite Cone

It is well known that state-of-the-art linear programming solvers are more efficient than their semidefinite programming counterparts and can scale to much larger problem sizes. This leads us to consider the question, how well can we approximate semidefinite programs with linear programs? In this paper, we prove lower bounds on the size of linear programs that approximate the positive semidefinite cone. Let D be the set of n x n positive semidefinite matrices of trace equal to one. We prove two results on the hardness of approximating Dwith polytopes. We show that if 0 < epsilon < 1 and A is an arbitrary matrix of trace equal to one, any polytope P such that (1 - epsilon) (D - A) subset of P subset of D - A must have linear programming extension complexity at least exp(c root n), where c > 0 is a constant that depends on e. Second, we show that any polytope P such that D subset of P and such that the Gaussian width of P is at most twice the Gaussian width of D must have extension complexity at least exp(cn(1 / 3)). Our bounds are both superpolynomial in n and demonstrate that there is no generic way of approximating semidefinite programs with compact linear programs. The main ingredient of our proofs is hypercontractivity of the noise operator on the hypercube.

Automated summary

This paper establishes lower bounds on the complexity of approximating semidefinite programs with linear programs, showing that any polytope approximating the positive semidefinite cone must have at least superpolynomial extension complexity. Ultimately, there is no generic way to efficiently approximate semidefinite programs with compact linear programs.