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. These constraints are of the form that when the decision variables are used as coefficients in certain polynomials, those polynomials should have the polynomial SOS property. 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.
Optimization problem.
Given a vector formula_1 and polynomials formula_2 for formula_3, formula_4, a sum-of-squares optimization problem is written as
formula_5
Here "SOS" represents the class of sum-of-squares (SOS) polynomials.
The quantities formula_6 are the decision variables. 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.
Dual problem: constrained polynomial optimization.
Suppose we have an formula_7-variate polynomial formula_8 , and suppose that we would like to minimize this polynomial over a subset formula_9. Suppose furthermore that the constraints on the subset formula_10 can be encoded using formula_11 polynomial equalities of degree at most formula_12, each of the form formula_13 where formula_14 is a polynomial of degree at most formula_12. A natural, though generally non-convex program for this optimization problem is the following:
formula_16
subject to:
 ;templatestyles src="Numbered block/styles.css" / ;
formula_17
where formula_18 is the formula_19-dimensional vector with one entry for every monomial in formula_20 of degree at most formula_21, so that for each multiset formula_22 formula_23, formula_24 is a matrix of coefficients of the polynomial formula_25 that we want to minimize, and formula_26 is a matrix of coefficients of the polynomial formula_27 encoding the formula_28-th constraint on the subset formula_29. The additional, fixed constant index in our search space, formula_30, is added for the convenience of writing the polynomials formula_25 and formula_32 in a matrix representation.
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 formula_33 with a positive-semidefinite matrix formula_34: we index each monomial of size at most formula_12 by a multiset formula_36 of at most formula_12 indices, formula_38. For each such monomial, we create a variable formula_39 in the program, and we arrange the variables formula_39 to form the matrix formula_41, where formula_42 is the set of real matrices whose rows and columns are identified with multisets of elements from formula_7 of size at most formula_21. We then write the following semidefinite program in the variables formula_39:
formula_46
subject to:
formula_47
formula_48
formula_49
formula_50
where again formula_24 is the matrix of coefficients of the polynomial formula_25 that we want to minimize, and formula_26 is the matrix of coefficients of the polynomial formula_27 encoding the formula_28-th constraint on the subset formula_29.
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 formula_34 respect the symmetries present in the quadratic form formula_58.
Duality.
One can take the dual of the above semidefinite program and obtain the following program:
formula_59
subject to:
formula_60
We have a variable formula_61 corresponding to the constraint formula_62 (where formula_63 is the matrix with all entries zero save for the entry indexed by formula_64), a real variable formula_65 for each polynomial constraint formula_66 and for each group of multisets formula_67, we have a dual variable formula_68 for the symmetry constraint formula_69. The positive-semidefiniteness constraint ensures that formula_70 is a sum-of-squares of polynomials over formula_29: by a characterization of positive-semidefinite matrices, for any positive-semidefinite matrix formula_72, we can write formula_73 for vectors formula_74. Thus for any formula_75,
formula_76
where we have identified the vectors formula_77 with the coefficients of a polynomial of degree at most formula_21. This gives a sum-of-squares proof that the value formula_79 over formula_80.
The above can also be extended to regions formula_81 defined by polynomial inequalities.
Sum-of-squares hierarchy.
The sum-of-squares hierarchy (SOS hierarchy), also known as the Lasserre hierarchy, is a hierarchy of convex relaxations of increasing power and increasing computational cost. For each natural number formula_82 the corresponding convex relaxation is known as the "formula_83th level" or "formula_84-th round of the SOS hierarchy." The formula_85st round, when formula_86, corresponds to a basic semidefinite program, or to sum-of-squares optimization over polynomials of degree at most formula_87. To augment the basic convex program at the formula_85st level of the hierarchy to formula_83-th level, additional variables and constraints are added to the program to have the program consider polynomials of degree at most formula_90.
The SOS hierarchy derives its name from the fact that the value of the objective function at the formula_83-th level is bounded with a sum-of-squares proof using polynomials of degree at most formula_92 via the dual (see "Duality" above). Consequently, any sum-of-squares proof that uses polynomials of degree at most formula_92 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 states that every non-negative real polynomial within a bounded interval can be approximated within accuracy formula_94 on that interval with a sum-of-squares of real polynomials of sufficiently high degree, and thus if formula_95 is the polynomial objective value as a function of the point formula_96, if the inequality formula_97 holds for all formula_96 in the region of interest, then there must be a sum-of-squares proof of this fact. Choosing formula_99 to be the minimum of the objective function over the feasible region, we have the result.
Computational cost.
When optimizing over a function in formula_100 variables, the formula_83-th level of the hierarchy can be written as a semidefinite program over formula_102 variables, and can be solved in time formula_102 using the ellipsoid method.
Sum-of-squares background.
A polynomial formula_104 is a "sum of squares" ("SOS") if there exist polynomials formula_105 such that formula_106. For example,
formula_107
is a sum of squares since
formula_108
where 
formula_109
Note that if formula_104 is a sum of squares then formula_111 for all formula_112. Detailed descriptions of polynomial SOS are available.
Quadratic forms can be expressed as formula_113 where formula_114 is a symmetric matrix. Similarly, polynomials of degree ≤ 2"d" can be expressed as 
formula_115
where the vector formula_116 contains all monomials of degree formula_117. This is known as the Gram matrix form. An important fact is that formula_104 is SOS if and only if there exists a symmetric and positive-semidefinite matrix formula_114 such that formula_120.
This provides a connection between SOS polynomials and positive-semidefinite matrices.