### Abstract

A central question in optimization is to maxim ize (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}_{+}. 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 ^{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.

Original language | English |
---|---|

Pages (from-to) | 2212-2243 |

Number of pages | 32 |

Journal | SIAM Journal on Optimization |

Volume | 25 |

Issue number | 4 |

DOIs | |

Publication status | Published - 2015 |

Externally published | Yes |

### Keywords

- Equivalent lifts
- Extended formulations
- Semidefinite programming
- Sum-of-squares

## Cite this

*SIAM Journal on Optimization*,

*25*(4), 2212-2243. https://doi.org/10.1137/140966265