Sum-of-squares optimization

Sum-of-squares optimization, commonly abbreviated SOS optimization, is a framework for approximating polynomial optimization problems through semidefinite programming. Its central construction replaces polynomial nonnegativity with the more restrictive condition that a polynomial admit a representation as a sum of squared polynomials. The resulting certificate can be expressed through a positive semidefinite Gram matrix, converting an otherwise difficult algebraic condition into a convex feasibility problem.

The framework connects nineteenth-century questions about positive polynomials with modern convex optimization. Its mathematical basis includes Hilbert’s classification of forms for which nonnegativity and sum-of-squares representability coincide, Artin’s solution of Hilbert's seventeenth problem, and later Positivstellensatz results concerning positivity on semialgebraic sets. Its computational form emerged from the development of interior-point methods and semidefinite relaxations during the late twentieth century.

Algebraic formulation

Let (p(x)\in\mathbb{R}[x_1,\ldots,x_n]) be a real multivariate polynomial. The polynomial is a sum of squares if there exist polynomials (q_1,\ldots,q_r) satisfying

[ p(x)=\sum_{i=1}^{r}q_i(x)^2. ]

Every sum-of-squares polynomial is globally nonnegative because each squared term is nonnegative on (\mathbb{R}^n). The converse does not hold in general. A globally nonnegative polynomial can fail to possess any polynomial sum-of-squares decomposition.

For homogeneous polynomials, Hilbert established that nonnegativity is equivalent to sum-of-squares representability only in specific cases. The equivalence holds for univariate forms, quadratic forms, and ternary quartic forms. Outside these cases, nonnegative forms exist that are not sums of squares. The Motzkin polynomial,

[ M(x,y)=x^4y^2+x^2y^4+1-3x^2y^2, ]

is a standard nonhomogeneous example. Its nonnegativity follows from the arithmetic–geometric mean inequality, while its monomial structure precludes a polynomial sum-of-squares decomposition.

This distinction determines the character of SOS optimization. A sum-of-squares certificate establishes nonnegativity, but the absence of such a certificate at a fixed degree does not establish that the polynomial takes negative values. SOS conditions therefore produce tractable inner approximations to cones of nonnegative polynomials.

Gram-matrix representation

Suppose that (p) has degree at most (2d), and let (z_d(x)) denote the vector containing every monomial in (x) of degree at most (d). Then (p) is a sum of squares exactly when a symmetric positive semidefinite matrix (Q) exists such that

[ p(x)=z_d(x)^{\mathsf T}Qz_d(x). ]

The matrix (Q) is called a Gram matrix for (p). Positive semidefiniteness permits a factorization (Q=R^{\mathsf T}R), from which

[ p(x)=\lVert Rz_d(x)\rVert_2^2 ]

and an explicit sum-of-squares decomposition follow.

Expanding (z_d(x)^{\mathsf T}Qz_d(x)) and matching its coefficients with those of (p) produces linear equations in the entries of (Q). The conditions on (Q) are consequently an affine system together with a positive semidefinite constraint. This is the standard form of a semidefinite feasibility problem.

The Gram matrix is generally nonunique because distinct matrix entries can contribute to the same polynomial coefficient. This nonuniqueness affects numerical conditioning and the interpretation of decompositions, but it does not alter the existence of an SOS certificate. A lower-rank Gram matrix corresponds to a decomposition using fewer squared polynomials, although rank minimization itself is not a convex operation.

Polynomial optimization relaxations

A basic unconstrained polynomial optimization problem has the form

[ p^\star=\inf_{x\in\mathbb{R}^n}p(x). ]

A scalar (\gamma) is a global lower bound whenever (p(x)-\gamma) is nonnegative for every (x). Replacing nonnegativity by sum-of-squares representability gives the relaxation

[ \begin{aligned} \text{maximize}\quad & \gamma,\ \text{subject to}\quad & p-\gamma\ \text{is SOS}. \end{aligned} ]

Because the SOS constraint has a Gram-matrix representation, this relaxation is a semidefinite program. Its optimal value cannot exceed (p^\star), and equality occurs when the optimal nonnegativity certificate is expressible within the chosen SOS cone.

Constrained problems are commonly written as

[ \inf_x{p(x):g_i(x)\geq 0,\ i=1,\ldots,m}. ]

A lower bound can be certified through an identity of the form

[ p(x)-\gamma

\sigma_0(x)+\sum_{i=1}^{m}\sigma_i(x)g_i(x), ]

where each (\sigma_i) is a sum-of-squares polynomial. On the feasible set, every term on the right-hand side is nonnegative. Degree bounds on the multipliers produce finite-dimensional semidefinite relaxations.

More general certificates include products of the constraint polynomials, as in [Schmüdgen's Positivstellensatz](/wiki/Schm%C3%BCdgen%27s_Pos ivitstellensatz), or membership in a quadratic module, as in [Putinar's Positivstellensatz](/wiki/Putinar%27s_Pos itivstellensatz). These theorems relate strict positivity on a basic closed semialgebraic set to algebraic representations involving sums of squares. Compactness or an equivalent Archimedean condition supplies the principal convergence assumption in the most widely used hierarchy.

Moment duality

The dual interpretation of SOS optimization is expressed through truncated moment problems. A linear functional (L_y) is specified by a sequence (y=(y_\alpha)) indexed by monomials, with

[ L_y!\left(\sum_\alpha p_\alpha x^\alpha\right)

\sum_\alpha p_\alpha y_\alpha. ]

If (y_\alpha) consists of moments of a positive measure, then the associated moment matrix is positive semidefinite. Localizing matrices encode the requirement that the measure be supported where the constraint polynomials are nonnegative.

The primal SOS certificate and the dual moment relaxation describe the same semidefinite structure from algebraic and measure-theoretic perspectives. Under suitable regularity conditions, their optimal values coincide. When a moment matrix satisfies an appropriate flat-extension rank condition, a finitely supported representing measure can be recovered, and its support identifies global minimizers of the original polynomial problem.

Jean-Bernard Lasserre formulated a hierarchy in which the degree limits on moment and SOS certificates increase successively. Under the Archimedean condition, the relaxation values converge monotonically to the global optimum. Finite convergence occurs for particular algebraic configurations, but it is not guaranteed for every polynomial optimization problem.

Computational development

The modern computational framework arose when polynomial identities were connected explicitly to semidefinite programming. Yurii Nesterov described semidefinite representations of cones of univariate and structured nonnegative polynomials, while Pablo Parrilo developed systematic SOS relaxations for polynomial systems and control problems. Masakazu Kojima and his collaborators established related semidefinite formulations for global polynomial optimization through quadratic representations and moment-type constructions.

The early 2000s also produced software that translated symbolic polynomial constraints into semidefinite programs. The initial development of SOSTOOLS involved Stephen Prajna, Antonis Papachristodoulou, Pablo Parrilo, and You Watanabe. Their work connected coefficient matching, Gram-matrix construction, and semidefinite solver interfaces within a common modeling system. Comparable packages subsequently adopted related representations, including YALMIP and GloptiPoly.

The size of a dense Gram matrix is governed by the number of monomials of bounded degree. For (n) variables and degree limit (d), the monomial vector has length

[ \binom{n+d}{d}. ]

The corresponding matrix dimension therefore grows combinatorially with the number of variables and the relaxation degree. This growth is a primary computational limitation rather than a defect in the underlying positivity certificate.

Structural reductions alter the resulting semidefinite program without changing its intended algebraic meaning. Correlative sparsity can separate variable groups whose interactions follow a sparse graph, while symmetry reduction decomposes Gram matrices according to invariant subspaces. Alternative bases can improve numerical scaling because monomials of substantially different magnitudes often produce poorly conditioned coefficient equations.

Exactness and limitations

SOS exactness depends on the polynomial class, the feasible set, and the permitted certificate degree. Convex quadratic optimization is represented exactly because nonnegative quadratic forms possess positive semidefinite matrix representations. Certain structured higher-degree problems also admit exact low-order relaxations, particularly when their algebraic constraints force an appropriate rank condition in the moment dual.

General polynomial nonnegativity remains computationally distinct from SOS membership. Deciding whether a polynomial is nonnegative is NP-hard for broad classes of multivariate polynomials, while a fixed-size SOS test is a convex semidefinite feasibility problem. The tractability of the relaxation is obtained by testing membership in a smaller cone.

Numerical solutions introduce a further distinction between approximate and exact certificates. Floating-point semidefinite solvers return matrices that satisfy coefficient equations and positive semidefiniteness only within numerical tolerances. Rational reconstruction and symbolic verification can convert suitable approximate solutions into exact algebraic identities, although such conversion depends on the location of the solution relative to the boundary of the positive semidefinite cone.

SOS methods also differ from linear programming relaxations based on nonnegative coefficients or polyhedral positivity certificates. Semidefinite formulations retain quadratic coupling among monomials and generally provide different bounds. Restrictions based on diagonally dominant Gram matrices replace semidefinite constraints with linear or second-order cone constraints, producing smaller cones of certifiable polynomials and correspondingly different computational problems.

Applications

In control theory, SOS constraints represent polynomial inequalities associated with Lyapunov functions. A polynomial candidate (V(x)) can be constrained so that (V) is positive and its derivative along a polynomial vector field is negative on a specified region. The resulting certificate establishes stability properties through a semidefinite program, subject to the conservatism of the chosen polynomial degree and SOS representation.

In dynamical systems, polynomial barrier certificates encode invariant regions and exclusion conditions. Related formulations bound reachable sets or long-time averages by replacing pointwise inequalities with SOS certificates. Moment duality gives these bounds an interpretation in terms of occupation measures over trajectories.

In discrete optimization, Boolean relations such as (x_i^2-x_i=0) convert finite problems into polynomial systems. SOS hierarchies then yield sequences of semidefinite relaxations whose strength increases with degree. These constructions are closely related to the Lasserre hierarchy and to proof systems based on polynomial identities.