English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A central question in optimization is to maximize (or minimize) a linearfunction over a given polytope P. To solve such a problem in practice one needsa concise description of the polytope P. In this paper we are interested inrepresentations of P using the positive semidefinite cone: a positivesemidefinite lift (psd lift) of a polytope P is a representation of P as theprojection of an affine slice of the positive semidefinite cone$\mathbf{S}^d_+$. Such a representation allows linear optimization problemsover P to be written as semidefinite programs of size d. Such representationscan be beneficial in practice when d is much smaller than the number of facetsof the polytope P. In this paper we are concerned with so-called equivariantpsd lifts (also known as symmetric psd lifts) which respect the symmetries ofthe polytope P. We present a representation-theoretic framework to studyequivariant psd lifts of a certain class of symmetric polytopes known asorbitopes. Our main result is a structure theorem where we show that anyequivariant psd lift of size d of an orbitope is of sum-of-squares type wherethe functions in the sum-of-squares decomposition come from an invariantsubspace of dimension smaller than d^3. We use this framework to study twowell-known families of polytopes, namely the parity polytope and the cutpolytope, and we prove exponential lower bounds for equivariant psd lifts ofthese polytopes.

Equivariant semidefinite lifts and sum-of-squares hierarchies