Semidefinite programming lifts, sums of squares, and matrix factorizations

Abstract:

A central question in optimization is to maximize (or minimize) a linear function over a given polytope. To solve such a problem in practice one needs a concise description of the polytope. In this talk I will consider representations of a polytope as the projection of the feasible set of a semidefinite program. Such a representation is called a semidefinite programming lift and encompasses linear programming extended formulations. I will describe a connection between semidefinite programming lifts, sums of squares and a new notion of matrix rank called the positive semidefinite rank. Finally I will show how the idea of sparse sums of squares allows us to construct semidefinite programming lifts for certain classes of polytopes that are vanishingly smaller than linear programming lifts.

Based on joint work with Joao Gouveia, Pablo Parrilo, Richard Robinson, James Saunderson, Rekha Thomas.