Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
Author(s)
Fawzi, Hamza; Saunderson, James; Parrilo, Pablo A.
DownloadFawzi-2015-Equivariant Semidefinite.pdf (768.7Kb)
PUBLISHER_POLICY
Publisher Policy
Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use.
Terms of use
Metadata
Show full item recordAbstract
A central question in optimization is to maximize (or minimize) a linear function over a given polytope P. To solve such a problem in practice one needs a concise description of the polytope P. In this paper we are interested in representations of P using the positive semidefinite cone: a positive semidefinite lift (PSD lift) of a polytope P is a representation of P as the projection of an affine slice of the positive semidefinite cone S[d over +]. Such a representation allows linear optimization problems over P to be written as semidefinite programs of size d. Such representations can be beneficial in practice when d is much smaller than the number of facets of the polytope P. In this paper we are concerned with so-called equivariant PSD lifts (also known as symmetric PSD lifts) which respect the symmetries of the polytope P. We present a representation-theoretic framework to study equivariant PSD lifts of a certain class of symmetric polytopes known as orbitopes. Our main result is a structure theorem where we show that any equivariant PSD lift of size d of an orbitope is of sum-of-squares type where the functions in the sum-of-squares decomposition come from an invariant subspace of dimension smaller than d[superscript 3]. We use this framework to study two well-known families of polytopes, namely the parity polytope and the cut polytope, and we prove exponential lower bounds for equivariant PSD lifts of these polytopes.
Date issued
2015-11Department
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science; Massachusetts Institute of Technology. Laboratory for Information and Decision SystemsJournal
SIAM Journal on Optimization
Publisher
Society for Industrial and Applied Mathematics
Citation
Fawzi, Hamza, James Saunderson, and Pablo A. Parrilo. “Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies.” SIAM Journal on Optimization 25, no. 4 (January 2015): 2212–2243. © 2015 Society for Industrial and Applied Mathematics
Version: Final published version
ISSN
1052-6234
1095-7189