Sum of Squares and Polynomial Convexity

The Motzkin polynomial M(x,y)=x2y4+x4y2-3x2y2+1 is historically the first example of a globally nonnegative polynomial that does not admit a representation as a sum of squares.

Given a multivariate polynomial how can we decide if it is globally nonnegative? This basic question appears ubiquitously in various areas of optimization and control, and unfortunately it is known to be difficult to answer from a computational complexity viewpoint. What if instead we ask the question: can the polynomial be written as a sum of squares (SOS) of other polynomials? It turns out that because of several appealing connections between real algebra and convex optimization, one can answer the latter question efficiently. It is clear that if a polynomial is a sum of squares, then it is globally nonnegative. But when do nonnegative polynomials admit a representation as a sum of squares? The study of this question, which belongs to the emerging field of convex algebraic geometry, has a prolonged and interesting history that dates back to prominent mathematicians such as David Hilbert.

At LIDS, MIT, Amir Ali Ahmadi and Professor Pablo Parrilo are looking at the interplay of the sum of squares machinery with the question of deciding convexity of polynomials. Similar to the SOS relaxation for polynomial nonnegativity, an algebraic notion known as SOS-convexity can be proposed as a tractable sufficient condition for polynomial convexity. Many natural questions arise: are there polynomials that are convex but not SOS-convex? If so, in what dimensions and degrees? What are the algebraic analogues of classical analytic theorems in convex analysis?

At a theoretical level, the overall goal of this project is to better understand the connections between the geometric and algebraic aspects of positivity and convexity. Practical applications of this work include efficient algorithms for minimizing polynomial functions, parameterizing convex polynomials that best fit given data, or searching for polynomial Lyapunov functions with convex sub-level sets.