Overview of SOS polynomials

Grigoriy Blekherman, Georgia Institute of Technology.

Nonnegativity of polynomials and its relations with sums of squares are classical topics in real algebraic geometry. This area has a rich and distinguished mathematical history beginning with Hilbert's fundamental work, his 17th problem, and its solution by Artin. Work in this area involves a blend of ideas and techniques from algebraic geometry, convex geometry and optimization. Recently SOS algorithms and relaxations have found numerous applications in engineering and theoretical computer science. There is also an emergent understanding that the study of nonnegative and SOS polynomials on a variety is inextricably linked to classical topics in algebraic geometry and commutative algebra, such as minimal free resolutions.

This exciting blend of ideas can be demonstrated with a single prominent example: the cone of positive semidefinite (PSD) matrices. On the one hand this cone can be viewed as the set of all homogeneous quadratic polynomials (forms) nonnegative on all of R^n, while on the other hand it is also a convex cone in the vector space of real symmetric matrices. It is also known that quadratic forms nonnegative on R^n are always SOS. An affine linear slice of the PSD cone is called a spectrahedron. The object of semidefinite programming is optimization of a linear function over a spectrahedron, and it is the engine that makes SOS algorithms work. SOS algorithms naturally lead to spectrahedra via convex duality, and understanding algebraic and convexity properties of these spectrahedra is the key to understanding the quality of these algorithms.