From coefficients to samples: a new approach to SOS optimization

We introduce a new methodology for the numerical solution of semidefinite relaxations arising from the sum of squares (SOS) decomposition of multivariate polynomials. The method is based on a novel SOS representation, where polynomials are represented by a finite set of values at discrete sampling points. The techniques have very appealing theoretical and numerical properties; the associated semidefinite programs are better conditioned, and have a rank one property that enables a fast computation of the search directions in interior point methods. The results are illustrated with examples, and a preliminary implementation is compared with previous techniques.