Sum-of-Squares Programming

This section contains a brief introduction to Sum-of-Squares Programming. For more details, see [BPT12, Las09, Lau09].

Quadratic forms and Semidefinite programming

The positive semidefiniteness of a $n \times n$ real symmetric matrix $Q$ is equivalent to the nonnegativity of the quadratic form $p(x) = x^\top Q x$ for all vector $x \in \mathbb{R}^n$. For instance, the polynomial

\[x_1^2 + 2x_1x_2 + 5x_2^2 + 4x_2x_3 + x_3^2 = x^\top \begin{pmatrix}1 & 1 & 0\\1 & 5 & 2\\ 0 & 2 & 1\end{pmatrix} x\]

is nonnegative since the matrix of the right-hand side is positive semidefinite. Moreover, a certificate of nonnegativity can be extracted from the Cholesky decomposition of the matrix:

\[(x_1 + x_2)^2 + (2x_2 + x_3)^2 = x^\top \begin{pmatrix}1 & 1 & 0\\0 & 2 & 1\end{pmatrix}^\top \begin{pmatrix}1 & 1 & 0\\0 & 2 & 1\end{pmatrix} x\]

Polynomial nonnegativity and Semidefinite programming

This can be generalized to a polynomial of arbitrary degree. A polynomial $p(x)$ is nonnegative if it can be rewritten as $p(x) = X^\top Q X$ where $Q$ is a real symmetric positive semidefinite matrix and $X$ is a vector of monomials.

For instance

\[x_1^2 + 2x_1^2x_2 + 5x_1^2x_2^2 + 4x_1x_2^2 + x_2^2 = X^\top \begin{pmatrix}1 & 1 & 0\\1 & 5 & 2\\ 0 & 2 & 1\end{pmatrix} X\]

where $X = (x_1, x_1x_2, x_2)$ Similarly to the previous section, the Cholesky factorization of the matrix can be used to extract a sum of squares certificate of nonnegativity for the polynomial:

\[(x_1 + x_1x_2)^2 + (2x_1x_2 + x_2)^2 = X^\top \begin{pmatrix}1 & 1 & 0\\0 & 2 & 1\end{pmatrix}^\top \begin{pmatrix}1 & 1 & 0\\0 & 2 & 1\end{pmatrix} X\]

When is nonnegativity equivalent to sum of squares ?

Determining whether a polynomial is nonnegative is NP-hard. The condition of the previous section was only sufficient, that is, there exists nonnegative polynomials that are not sums of squares. Hilbert showed in 1888 that there are exactly 3 cases for which there is equivalence between the nonnegativity of the polynomials of $n$ variables and degree $2d$ and the existence of a sum of squares decomposition.

$n = 1$ : Univariate polynomials
$2d = 2$ : Quadratic polynomials
$n = 2$, $2d = 4$ : Bivariate quartics

The first explicit example of polynomial that was not a sum of squares was given by Motzkin in 1967:

\[x_1^4x_2^2 + x_1^2x_2^4 + 1 - 3x_1^2x_2^2 \geq 0 \quad \forall x\]

While it is not a sum of squares, it can still be certified to be nonnegative using sum-of-squares programming by identifying it with a rational sum-of-squares decomposition. These facts can be verified numerically using this package as detailed in the motzkin notebook.

References

[BPT12] Blekherman, G.; Parrilo, P. A. & Thomas, R. R. Semidefinite Optimization and Convex Algebraic Geometry. Society for Industrial and Applied Mathematics, 2012.

[Las09] Lasserre, J. B. Moments, positive polynomials and their applications World Scientific, 2009.

[Lau09] Laurent, M. Sums of squares, moment matrices and optimization over polynomials Emerging applications of algebraic geometry, Springer, 2009, 157-270.