Is SOS just checking many sample points?

No. An exact polynomial identity can establish nonnegativity across an entire domain rather than only at sampled locations.

Does increasing certificate degree always solve the problem immediately?

No. Higher degrees can strengthen certain hierarchies under assumptions, but cost grows and finite-degree success is not guaranteed in every setting.

Can a sum-of-squares polynomial be nonconvex?

Yes. Nonnegativity of a polynomial and convexity of its graph are different properties.

AI Glossary / Mathematics and optimization / Advanced

Sum-of-squares optimization

Definition

Sum-of-squares optimization, or SOS optimization, uses representations of polynomials as sums of squared polynomials to obtain tractable certificates of nonnegativity. Because every real square is nonnegative, an identity p(x) = Σ qi(x)² proves that p is nonnegative for every real x. Many SOS searches can be formulated as semidefinite programs, supporting polynomial optimization and verification tasks.

What it means

The central idea is to replace a difficult statement about infinitely many input values with a finite algebraic certificate. For example, proving p(x) − γ is a sum of squares establishes γ as a global lower bound on p. Maximizing γ searches for the strongest bound available under that certificate form. This differs from ordinary least-squares fitting, where squared residuals are minimized over data. SOS optimization concerns polynomial identities and nonnegativity, although both subjects involve squares.

How it works

Choose a vector z(x) of monomials up to a suitable degree and seek a positive-semidefinite matrix Q such that p(x) = z(x)ᵀQz(x). Matching coefficients produces linear equations in Q and any polynomial coefficients that enter affinely as decision variables. The positive-semidefinite constraint makes the search a semidefinite program. Factorizing Q yields a sum-of-squares representation. For a restricted domain, polynomial multipliers can incorporate the domain inequalities into a certificate. Degree limits control the size and strength of the search. If unknown quantities multiply each other in the formulation, the resulting problem need not retain this simple convex structure.

Three practical examples

A polynomial-optimization study can seek a certified lower bound to compare with the value of a candidate minimizer.
A control-analysis project can search for polynomial Lyapunov functions or related certificates under clearly stated dynamics and domain assumptions.
A robotics-research workflow can investigate polynomial inequalities that certify properties over a region, while separately checking modeling approximations and numerical certificate accuracy.

Think of it this way

Think of proving that an account balance cannot be negative by rewriting it as a sum of amounts that are each visibly nonnegative. The representation provides an explanation that applies across all allowed cases. The analogy captures certification, but polynomial SOS has a specific algebraic form, and not every nonnegative multivariate polynomial admits that form without additional constructions or assumptions.

Worked example

Consider p(x) = x⁴ − 2x² + 2. Rewrite it as p(x) = (x² − 1)² + 1. Therefore p(x) ≥ 1 for every real x, and equality occurs at x = 1 and x = −1. An SOS program maximizing γ subject to p(x) − γ being SOS can achieve γ = 1. It cannot achieve a larger value, because evaluating at x = 1 would make p(1) − γ negative. A Gram representation uses z(x) = [1, x, x²] and Q = [[1, 0, −1], [0, 0, 0], [−1, 0, 1]], giving zᵀQz = (x² − 1)². This Q equals vvᵀ for v = [1, 0, −1], so it is positive semidefinite. If the domain is restricted to |x| ≤ 1/2, a stronger bound holds: p(x) − 25/16 = (x² − 1/4)² + (3/2)(1/4 − x²). Both terms are nonnegative on that domain, and equality occurs at its endpoints. The second certificate uses the domain inequality; it is not a claim that p − 25/16 is globally nonnegative.

Illustrative case study

In a fictional project, Hazel Controls studies a polynomial approximation to a system's local dynamics. Analysts search for an SOS certificate over a declared operating region, then check coefficient residuals and compare the approximated dynamics with the underlying model. They keep the region and approximation error visible in their report. The case illustrates certificate scope and verification, not a claim that an invented controller has been proven safe for deployment.

Common misconceptions and mistakes

Every SOS polynomial is nonnegative, but the converse fails for general multivariate polynomials. Failure to find an SOS certificate at a chosen degree does not prove that the original polynomial becomes negative. A numerical solver's success flag alone is not an exact symbolic proof: tolerances, near-zero eigenvalues and coefficient residuals require examination. Conversely, a lower-bound certificate does not by itself identify a point attaining the bound. Adding a matching feasible point supplies that extra evidence. The term convex applies to an appropriately formulated SOS program, not automatically to the original polynomial objective in x.

Business use

Use SOS methods when a polynomial model and a certificate-based answer suit the task. Specify whether the claim is global or restricted to a semialgebraic domain, and state the allowed certificate degree. Estimate matrix size before solving: the number of monomials can grow rapidly with variables and degree. Inspect feasibility residuals and positive-semidefinite tolerances, and use exact or rigorously bounded verification when a formal certificate is required. Preserve the polynomial, domain, certificate and numerical settings so another analyst can reproduce the reasoning.

Check your understanding

Why does p(x) − 1 = (x² − 1)² prove the global minimum is exactly 1 rather than merely at least 1?

Answer: The identity gives the lower bound, and the explicit points x = ±1 attain it. Both pieces are needed for the exact optimum claim.

Related terms

Gram matrix
polynomial optimization
semidefinite programming
nonnegative polynomial
Lyapunov function
optimization certificate

Learn next

expand both worked certificates and verify each coefficient. Check the domain-specific identity at x = 0, x = 1/2 and x = 1. Then compare a numerical Gram matrix with its exact intended coefficients before interpreting solver output as a proof.

Gram matrix

Sources

Sources: Drake project, Sum-of-Squares Optimization tutorial, https://drake.mit.edu/tutorials/sum_of_squares_optimization.html ; Pablo Parrilo, SOSTOOLS project overview, https://www.mit.edu/~parrilo/sostools/ . The quartic, rank-one Gram matrix, interval certificate and fictional controls study are original educational examples.

Previous: Sum of squared differences Next: Sums of squares