Sufficient conditions for a real polynomial to be a sum of squares

Jean B. Lasserre

Abstract: We provide explicit conditions for a real polynomial $f$ of degree 2d to be a sum of squares (s.o.s.), stated only in terms of the coefficients of $f$, i.e. with no lifting. All conditions are simple and provide an explicit description of a convex polyhedral subcone of the cone of s.o.s. polynomials of degree at most 2d. We also provide a simple condition to ensure that $f$ is s.o.s., possibly modulo a constant.

Introduction

In the fields of global optimization, control theory, and robotics, a recurring challenge is determining whether a real polynomial $f(x)$ is non-negative for all inputs. Because verifying non-negativity is NP-hard, the "Sum of Squares" (SOS) condition is widely used as a tractable sufficient condition. A polynomial is SOS if it can be expressed as $f = \sum g_i^2$, which immediately guarantees $f(x) \geq 0$.

The Challenge of Lifting and SDP

Standard methods for checking the SOS property rely on Semidefinite Programming (SDP). This involves a process known as "lifting," where the problem is transformed into a higher-dimensional space by introducing a large number of auxiliary variables to represent a "Gram matrix." While powerful, the computational complexity of SDP grows rapidly with the degree and number of variables, making it a bottleneck for large-scale problems. Furthermore, there has historically been no simple, direct description of the SOS cone using only the original coefficients of the polynomial.

A Direct Coefficient-Based Approach

Jean B. Lasserre addresses these limitations by identifying explicit, linear conditions on a polynomial's coefficients that guarantee it is SOS. This approach identifies a convex polyhedral subcone within the broader SOS cone. Unlike the full SOS cone, which is semidefinite and "curved," a polyhedral cone is defined by flat-sided linear inequalities, making it significantly easier to verify.

Methods and the Moment Matrix

The theoretical foundation of this work lies in the duality between polynomials and "moments." Lasserre defines a linear mapping $L_y$ and an associated moment matrix $M_d(y)$. A polynomial is SOS if and only if $L_y(f) \geq 0$ for all sequences $y$ that result in a positive semidefinite moment matrix.

To derive the sufficient conditions, Lasserre analyzes the block structure of these matrices. By partitioning the moment matrix and applying the Budan-Fourier theorem—a classical result relating the signs of a polynomial's derivatives to its real roots—the author constructs a univariate polynomial that, if root-free in a specific range, ensures the original polynomial is SOS.

Block structure of the moment matrix $M_d(y)$ used to derive sufficient SOS conditions.

Key Insights and Theoretical Results

The core contribution of the paper is the derivation of direct coefficient bounds that bypass the need for SDP solvers:

  • Theorem 3: This theorem provides the primary sufficient condition. It states that if the coefficients of the "essential" even-power terms (the constant term $f_0$ and the highest-degree terms $f_{i2d}$) are sufficiently large relative to the absolute values of the other coefficients, the polynomial is guaranteed to be SOS.
  • Polyhedral Efficiency: Because these conditions are piecewise linear and concave, they define a convex set that can be tested with basic arithmetic. This offers a "cheap" alternative to full SOS decomposition.
  • Handling Intermediate Powers: Corollary 4 extends these results to polynomials with intermediate even powers ($X_i^{2k}$ for $k < d$), providing flexibility for polynomials with many non-zero coefficients.

Limitations and Future Directions

It is important to note that these conditions are sufficient but not necessary. The identified polyhedral cone is a subset of the full SOS cone, meaning many SOS polynomials will not satisfy these specific linear bounds. The conditions are most effective for sparse polynomials; for dense polynomials, the bounds may become overly conservative.

Despite these limitations, Lasserre’s work provides a significant step toward more efficient polynomial optimization. These conditions can be used to improve approximations of non-negative polynomials and may serve as a fast pre-processing step or alternative to the full Lasserre hierarchy in large-scale optimization tasks.

Summary updated

Abstract

We provide explicit conditions for a real polynomial $f$ of degree 2d to be a sum of squares (s.o.s.), stated only in terms of the coefficients of $f$, i.e. with no lifting. All conditions are simple and provide an explicit description of a convex polyhedral subcone of the cone of s.o.s. polynomials of degree at most 2d. We also provide a simple condition to ensure that $f$ is s.o.s., possibly modulo a constant.
BibTeX
@inproceedings{lasserre2007sufficient,
  author = {Jean B. Lasserre},
  title = {{Sufficient conditions for a real polynomial to be a sum of squares}},
  booktitle = {Archiv},
  year = {2007},
  doi = {10.1007/s00013-007-2251-y},
}
Figure