Proving that a multivariate polynomial never drops below zero is a fundamental challenge in optimization, control theory, and statistics. While checking the sign of a function at a few points is easy, proving global nonnegativity is generally NP-hard because a function might dip into negative values in a tiny, overlooked region of its domain. The research direction of algebraic certification shifts this problem from a point-by-point search to a search for a symbolic "identity of positivity."
The Intuition of Sums of Squares
The most intuitive certificate of nonnegativity is a Sum of Squares (SOS) decomposition. If a polynomial $f(x)$ can be rewritten as $\sum p_i(x)^2$ for some other polynomials $p_i$, it is mathematically impossible for $f(x)$ to be negative for any real $x$.
As Jean B. Lasserre and Mihai Putinar describe in Positivity and Optimization for Semi-Algebraic Functions, this algebraic approach can be extended to broader classes of semi-algebraic functions, including those with radicals. The power of this method lies in its translation to computation: finding the coefficients of the polynomials $p_i$ can be framed as a Semidefinite Program (SDP), a type of convex optimization that can be solved efficiently. Jean B. Lasserre further demonstrates in The Moment-SOS hierarchy that this creates a sequence of increasingly accurate approximations, known as the Lasserre hierarchy, which bridges the gap between real algebraic geometry and numerical optimization.
Certifying Constraints and Domains
In most practical scenarios, we only care if a polynomial is nonnegative over a specific region, such as a box or a sphere, defined by other polynomial inequalities $g_j(x) \geq 0$. These regions are called basic semi-algebraic sets.
To certify positivity here, researchers rely on Positivstellensatz theorems. These theorems, such as Putinar’s, state that if a polynomial is strictly positive on a compact set, it can be represented as $f(x) = \sigma_0(x) + \sum \sigma_j(x)g_j(x)$, where each $\sigma$ is itself a sum of squares. Korda et al. utilize this in Convergence rates of moment-sum-of-squares hierarchies for optimal control problems to enforce differential inequalities in control systems. Similarly, Laurent et al. provide effective degree bounds for these certificates on the hypercube in An effective version of Schmüdgen's Positivstellensatz for the hypercube, quantifying how complex the certificate must be to guarantee a proof.
The Gap Between Geometry and Algebra
A central theme in this field is that geometric properties (like convexity) and algebraic certificates (like SOS) do not always overlap perfectly. A polynomial is SOS-convex if its Hessian matrix can be factored into a sum of polynomial squares. While SOS-convexity is computationally tractable via SDP, it is a stricter condition than standard convexity.
Amir Ali Ahmadi et al. famously settled a long-standing question in A convex polynomial that is not sos-convex by providing an explicit counterexample: a polynomial that is geometrically convex but lacks an SOS-convex certificate. They later provided a complete characterization of this gap, showing that the cases where convexity equals SOS-convexity are exactly the cases where nonnegativity equals SOS, following classical results by Hilbert.
Alternative Certificates for Efficiency and Precision
While SOS is the standard, it can be computationally expensive for high-degree or sparse polynomials. This has led to alternative certification frameworks:
- SONC (Sums of Nonnegative Circuit Polynomials): Adam Kurpisz proposes SONC in Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials as a tool for sparse optimization. Unlike SOS, which uses SDP, Wang et al. show in A second order cone characterization for sums of nonnegative circuits that SONC can be solved using Second-Order Cone Programming (SOCP), which is often faster.
- Hyperbolic Optimization: James Saunderson introduces hyperbolic certificates, which leverage the real-rootedness of hyperbolic polynomials to certify nonnegativity for cases where SOS fails.
- Exact Rational Certificates: Numerical solvers often produce approximate certificates. Magron et al. developed techniques in On Exact Polya and Putinar's Representations and Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients to convert these into exact rational proofs, ensuring that the certificate is not just a numerical artifact but a rigorous mathematical truth.
Applications in Data and Dynamics
These algebraic tools are increasingly used to solve high-dimensional problems in statistics and physics. Diakonikolas et al. proved in SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications that the moment-boundedness of subgaussian distributions is SOS-certifiable, enabling new robust estimation algorithms. In the realm of information theory, Guo et al. and Junliang Liu have used SOS to verify complex inequalities regarding differential entropy and Fisher information, turning abstract conjectures into solvable optimization problems.
Key Foundational Work
Minimum Ellipsoid Bounds for Solutions of Polynomial Systems via Sum of Squares (2005) — contributed 2 concept elements to this direction.
Initialization of Physical Parameter Estimates (2003) — contributed 1 concept elements to this direction.
A moment approach to analyze zeros of triangular polynomial sets (2005) — contributed 1 concept elements to this direction.