Algebraic Certificates for Polynomial Nonnegativity and Convexity

48 concepts43 papers1 proposal

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:

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_algebraic_convexity_certification_9b4c6fe3,
  title = {algebraic convexity certification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algebraic-convexity-certification/rdr_9b4c6fe3f1e242aabda3751f8fa83a10},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_algebraic_convexity_certification_9b4c6fe3_v1,
  title = {algebraic convexity certification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/algebraic-convexity-certification/rdr_9b4c6fe3f1e242aabda3751f8fa83a10/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake