On Polyhedral Approximations of the Positive Semidefinite Cone

Hamza Fawzi ()
Additional contact information
Hamza Fawzi: Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge CB3 0WA, United Kingdom

Mathematics of Operations Research, 2021, vol. 46, issue 4, 1479-1489

Abstract: 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 × n positive semidefinite matrices of trace equal to one. We prove two results on the hardness of approximating D with polytopes. We show that if 0 < ε < 1and A is an arbitrary matrix of trace equal to one, any polytope P such that (1-ε) ( D - A ) ⊂ P ⊂ D - A must have linear programming extension complexity at least exp ( c n ) , where c > 0 is a constant that depends on ε. Second, we show that any polytope P such that D ⊂ 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 ( c n 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.

Keywords: 90C05, 90C22, 52B55, Primary: convex programming/linear programming; secondary: polyhedra, semidefinite programming, linear programming, extended formulations (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1077 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:4:p:1479-1489

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().