Exploiting structure in sum of squares programs

Abstract

We present an overview of the different techniques available for exploiting structure in the formulation of semidefinite programs based on the sum of squares decomposition of multivariate polynomials. We identify different kinds of algebraic properties of polynomial systems that can be successfully exploited for numerical efficiency. Our results apply to three main cases: sparse polynomials, the ideal structure present in systems with explicit equality constraints, and structural symmetries, as well as combinations thereof. The techniques notably improve the size and numerical conditioning of the resulting SDPs, and are illustrated using several control-oriented applications.