A sum-of-squares optimization program is an optimization problem with a linear cost function and a particular type of constraint on the decision variables.
When fixing the maximum degree of the polynomials involved, sum-of-squares optimization is also known as the Lasserre hierarchy of relaxations in semidefinite programming.
Sum-of-squares optimization techniques have been applied across a variety of areas, including control theory (in particular, for searching for polynomial Lyapunov functions for dynamical systems described by polynomial vector fields), statistics, finance and machine learning.
, a sum-of-squares optimization problem is written as
SOS programs can be converted to semidefinite programs (SDPs) using the duality of the SOS polynomial program and a relaxation for constrained polynomial optimization using positive-semidefinite matrices, see the following section.
A natural, though generally non-convex program for this optimization problem is the following:
The additional, fixed constant index in our search space,
, is added for the convenience of writing the polynomials
This program is generally non-convex, because the constraints (1) are not convex.
One possible convex relaxation for this minimization problem uses semidefinite programming to replace the rank-one matrix of variables
is the set of real matrices whose rows and columns are identified with multisets of elements from
We then write the following semidefinite program in the variables
The third constraint ensures that the value of a monomial that appears several times within the matrix is equal throughout the matrix, and is added to make
respect the symmetries present in the quadratic form
, corresponds to a basic semidefinite program, or to sum-of-squares optimization over polynomials of degree at most
To augment the basic convex program at the
The SOS hierarchy derives its name from the fact that the value of the objective function at the
-th level is bounded with a sum-of-squares proof using polynomials of degree at most
can be used to bound the objective value, allowing one to prove guarantees on the tightness of the relaxation.
In conjunction with a theorem of Berg, this further implies that given sufficiently many rounds, the relaxation becomes arbitrarily tight on any fixed interval.
Berg's result[5][6] states that every non-negative real polynomial within a bounded interval can be approximated within accuracy
on that interval with a sum-of-squares of real polynomials of sufficiently high degree, and thus if
is the polynomial objective value as a function of the point
in the region of interest, then there must be a sum-of-squares proof of this fact.
to be the minimum of the objective function over the feasible region, we have the result.
-th level of the hierarchy can be written as a semidefinite program over
is a sum of squares (SOS) if there exist polynomials
Detailed descriptions of polynomial SOS are available.
is SOS if and only if there exists a symmetric and positive-semidefinite matrix
This provides a connection between SOS polynomials and positive-semidefinite matrices.