Semidefinite descriptions of regular polygons (and beyond), James Saunderson

Tuesday, November 10, 2015, 4:00 pm
GUG 204

James Saunderson, University of Washington .
Semidefinite descriptions of regular polygons (and beyond)

Abstract: This talk is focused on describing certain polytopes as the feasible regions of semidefinite programs (SDPs). The polytopes of interest arise from abelian groups in a natural way and include regular polygons in the plane, parity polytopes, certain cyclic polytopes, and cut polytopes. These polytopes provide excellent examples through which we can examine general questions about the relative expressive power of semidefinite programming vs linear programming, the role of symmetry in semidefinite descriptions, and differences in the size of descriptions based on the Lasserre hierarchy and those based on general SDPs.

In this talk I will describe a combinatorial way to construct such semidefinite descriptions for this family of polytopes. When applied to the nth cut polytope we obtain a proof that the Lasserre hierarchy is exact after \lceil n/2\rceil rounds (establishing a conjecture of Laurent). When applied to trigonometric cyclic polytopes we obtain semidefinite descriptions that are significantly smaller than any possible linear programming descriptions of these polytopes.

Based on joint work with Hamza Fawzi and Pablo Parrilo