Sum-of-squares optimization, also called sum-of-squares programming, is optimization with a linear objective function and constraints
requiring specified polynomials to be sums of squares
of polynomials. A polynomial 
is a sum of squares if
 |
for polynomials 
.
Let 
contain all monomials of polynomial
degree at most 
. A polynomial 
of polynomial degree
at most 
is a sum of squares iff there is a positive
semidefinite matrix 
such that
 |
Equating coefficients gives linear constraints on the entries of the Gram matrix 
. Therefore, a sum-of-squares optimization problem can be converted
to a semidefinite programming problem.
In polynomial optimization, bounded-degree sum-of-squares certificates give a hierarchy of semidefinite programming relaxations. Increasing the polynomial degree can improve the bound, and Positivstellensatz results give convergence under suitable hypotheses.
