Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
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 s...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2016
|
| Online Access: | http://hdl.handle.net/1721.1/101895 https://orcid.org/0000-0001-6026-4102 https://orcid.org/0000-0003-1132-8477 |
| Summary: | 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. |
|---|