Sparse Certificates for Polynomial Nonnegativity

22 concepts9 papers

Proving that a polynomial is always non-negative is a foundational challenge across optimization, control theory, and robotics. If we can certify that a cost function is always greater than or equal to zero, we can find global minima, guarantee system stability, and solve complex geometric problems.

The mathematical gold standard for proving nonnegativity is the Sum of Squares (SOS) certificate: if a polynomial can be written as $f(x) = \sum g_i(x)^2$, it is obviously non-negative. To find these $g_i(x)$, we typically use the Lasserre hierarchy, which translates the problem into Semidefinite Programming (SDP).

However, standard SOS methods hit a "computational wall" when dealing with high-degree polynomials. In the standard toolkit, the complexity of the SDP depends entirely on the degree of the polynomial and the number of variables, not on how many terms it actually has. If you have a polynomial with only three terms but a degree of 100 (such as $1 - 2x^{50} + x^{100}$), standard SOS treats it with the same heavy machinery as a dense polynomial containing hundreds of terms. It completely ignores sparsity.

To overcome this bottleneck, a major research direction focuses on creating sparse nonnegativity certificates. The goal is simple: the complexity of proving a polynomial is non-negative should scale with its number of non-zero terms (monomials), not its total degree.

The Failure of Sparsity in Standard Sum-of-Squares

Why does traditional SOS fail to preserve sparsity? When we look for an SOS decomposition, we construct a large matrix of coefficients (the Gram matrix) indexed by all possible monomials up to half the polynomial's degree. Even if the input polynomial is sparse, the squares of the underlying polynomials $g_i(x)$ can introduce a massive number of cross-terms that must cancel out perfectly.

As Claus Scheiderer points out, this means standard hierarchies require semidefinite constraints whose sizes grow exponentially with degree, ignoring the inherent sparsity that could allow for lower-complexity proofs. If a polynomial has very few terms but a high degree, finding a standard SOS certificate becomes computationally intractable.

To fix this within the SOS framework, researchers have developed ways to restrict the certificate's support. For instance, Hamza Fawzi et al. demonstrated that by utilizing polynomials supported on a limited set of frequencies, one can construct sparse SOS certificates that respect geometric symmetries, resulting in drastically smaller SDP representations. Similarly, Jie Wang et al. introduced the TSSOS framework, which directly exploits "term sparsity" to construct a sparse variant of Putinar's Positivstellensatz, breaking down the massive Gram matrix into smaller, block-diagonal pieces.

The Power of the Monomial Count: Bounded-Degree Certificates

The core intuition of sparse certificates is that the complexity of a proof should be governed by the number of monomials. Claus Scheiderer proved a remarkable theoretical justification for this: for certain sparse polynomials, nonnegativity can be certified using SOS polynomials whose degrees are bounded by the number of monomials rather than the total degree.

To construct these explicit, low-degree representations, Claus Scheiderer leverages Schur polynomials. Because Schur polynomials possess inherently non-negative coefficients on the positive orthant, they serve as a bridge between algebraic combinatorics and optimization, allowing researchers to factorize determinants into explicit, sparse SOS representations.

This aligns with an earlier breakthrough by Jean B. Lasserre, who shifted the mathematical perspective from standard topologies to a weighted $\ell_1$-norm. Under this norm, the closest algebraic approximation to a non-negative polynomial is extremely sparse—often requiring only a constant and a few high-degree terms. This provides a simple, explicit certificate of positivity for complex polynomials without requiring a dense, exhaustive search.

Unbounded Domains and Rational Multipliers

When optimizing over non-compact (unbounded) sets, maintaining sparsity becomes even more difficult. A polynomial might be positive everywhere, but a sparse polynomial SOS decomposition simply might not exist without causing an exponential blowup in the degree of the terms.

To solve this, researchers turn to rational sum-of-squares certificates. Instead of proving $f(x) = \sum g_i(x)^2$, we prove:

$$f(x) = \frac{\sum g_i(x)^2}{D(x)}$$

where $D(x)$ is a strictly positive polynomial called a uniform denominator.

Ngoc Hoang Anh et al. developed a sparse version of Reznick's Positivstellensatz using this exact mechanism. By incorporating uniform denominators, the authors showed that positivity certificates can mirror the original sparsity pattern of the input function. This allows a large-scale global positivity proof to be decomposed into smaller, local certificates that only involve specific subsets of variables, preventing the exponential growth of computational complexity in unbounded regions.

Moving Beyond Squares: The SONC Alternative

While optimizing the SOS framework helps, some researchers argue that the sum-of-squares property is fundamentally mismatched with sparsity. As Jie Wang et al. argue, the SOS certificate inherently fails to preserve sparsity in many settings, creating a need for alternative certificates.

The most prominent alternative is the Sum of Nonnegative Circuit Polynomials (SONC). Instead of relying on the fact that squares are non-negative ($x^2 \ge 0$), SONC relies on the Arithmetic-Geometric Mean (AM-GM) inequality.

A "circuit polynomial" is a sparse polynomial whose support forms a simplex in the exponent space (vertices with positive coefficients) plus at most one interior point (which can have a negative coefficient). We can easily check if a circuit polynomial is non-negative by comparing the magnitude of the interior negative term to the geometric mean of the outer positive terms.

SOS Approach:  f(x) = g₁(x)² + g₂(x)² + ...

+ gₙ(x)²  --> Requires Semidefinite Programming (SDP)
SONC Approach: f(x) = Circuit₁ + Circuit₂ + ...      --> Requires Second-Order Cone Programming (SOCP)

Because SONC focuses entirely on the combinatorial structure of the terms that are actually present, it inherently preserves sparsity. Adam Kurpisz et al. and Adam Kurpisz demonstrated that for optimization over the boolean hypercube, SONC matches SOS in key theoretical benchmarks. By using Carathéodory’s Theorem, the authors proved that these circuit-based certificates can be made "short"—meaning the number of required terms scales polynomially with the number of variables, offering a massive computational advantage in high-dimensional settings.

The Computational Payoff: From SDP to SOCP

The shift from SOS to SONC is not just a change in algebraic philosophy; it fundamentally changes the underlying algorithms. Standard SOS requires Semidefinite Programming (SDP), which involves large, expensive matrix inequalities.

In contrast, Jie Wang et al. and Victor Magron et al. demonstrated that the cone of SONC polynomials can be fully characterized using Second-Order Cone Programming (SOCP). SOCP solvers are vastly more scalable and numerically stable than SDP solvers. By leveraging SOCP to compute SONC decompositions, these algorithms can efficiently verify exact nonnegativity certificates for sparse polynomials with hundreds of variables and high degrees where traditional SOS completely fails.

Automating the Search for Sparse Proofs

As the theoretical boundaries of sparse certificates expand, finding the exact subset of terms or circuits needed for a proof remains a challenging combinatorial search problem. To automate this, recent work has even begun combining algebraic theory with machine learning.

For example, Banglong Liu et al. introduced a framework that uses Deep Q-Networks (DQN) reinforcement learning to navigate the complex search space of mathematical proofs. By training an agent to identify a sparse subset of basis terms with non-negative coefficients, the system can automatically discover verifiable certificates of nonnegativity without an exhaustive, brute-force computation of all possible terms.

Whether through structural refinements to the Sum of Squares hierarchy, the deployment of AM-GM circuit polynomials, or intelligent search algorithms, the shift toward sparsity-aware nonnegativity certificates represents a fundamental leap forward in making polynomial optimization practical for real-world, high-dimensional systems.

Key Foundational Work

Equivariant Semidefinite Lifts of Regular Polygons (2017) — contributed 2 concept elements to this direction.
The $\mathbf {K}$-moment problem for continuous linear functionals (2012) — 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_sparse_sum_of_squares_certificate_e3044e05,
  title = {sparse sum-of-squares certificate},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sparse-sum-of-squares-certificate/rdr_e3044e05e96b4be7b0f977487d838655},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_sparse_sum_of_squares_certificate_e3044e05_v1,
  title = {sparse sum-of-squares certificate},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sparse-sum-of-squares-certificate/rdr_e3044e05e96b4be7b0f977487d838655/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}

See something wrong? Report a mistake