Exploiting symmetries in semidefinite programming

Pablo A. Parrilo, ETH Zurich

In several applications of semidefinite programming (SDP), the underlying optimization problem is invariant under the action of a symmetry group. A natural question, therefore, is the possibility of exploiting this information for faster and more reliable algorithms. To this effect, we study the associative algebra associated with a given SDP. We show how to explicitly decompose it as a direct sum of "smaller" algebras, greatly simplifying its numerical solution. The methods extend our earlier work with Karin Gatermann on symmetry reduction for sum of squares problems, and enable improved techniques for problems with large groups. The results will be illustrated through applications of sum of squares techniques in control theory and quantum mechanics.