A central question in optimization is to maximize (or minimize) a linear function over a given polytope P. Often, 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. Such a representation allows linear optimization problems over P to be written as semidefinite programs.

In this talk 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 regular orbitopes. Our main result is a structure theorem where we show that any equivariant psd lift of a regular orbitope is of "sum-of-squares" type (suitably interpreted).

We use this framework to study several families of orbitopes, such as the parity polytope, the cut polytope, and regular polygons. For these, we obtain both exponential lower bounds (parity, cut) and new explicit efficient constructions (polygons).

Based on joint work with Hamza Fawzi and James Saunderson.

Bio: Pablo A. Parrilo is a Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. He is currently Associate Director of the Laboratory for Information and Decision Systems (LIDS), and is also affiliated with the Operations Research Center (ORC). Past appointments include Assistant Professor at the Automatic Control Laboratory of the Swiss Federal Institute of Technology (ETH Zurich), Visiting Associate Professor at the California Institute of Technology, as well as short-term research visits at the University of California at Santa Barbara (Physics), Lund Institute of Technology (Automatic Control), and University of California at Berkeley (Mathematics). He received an Electronics Engineering undergraduate degree from the University of Buenos Aires, and a PhD in Control and Dynamical Systems from the California Institute of Technology.

His research interests include optimization methods for engineering applications, control and identification of uncertain complex systems, robustness analysis and synthesis, and the development and application of computational tools based on convex optimization and algorithmic algebra to practically relevant engineering problems.

Prof. Parrilo has received several distinctions, including a Finmeccanica Career Development Chair, the Donald P. Eckman Award of the American Automatic Control Council, the SIAM Activity Group on Control and Systems Theory (SIAG/CST) Prize, the IEEE Antonio Ruberti Young Researcher Prize, and the Farkas Prize of the INFORMS Optimization Society.