Abstract
Given a nonnegative polynomial $f$, we provide an explicit expression for its best $\ell_1$-norm approximation by a sum of squares of given degree.
Introduction
Determining the nonnegativity of a polynomial is a fundamental problem in optimization and algebraic geometry. While checking if $f(x) \geq 0$ for all $x \in \mathbb{R}^n$ is NP-hard, a common relaxation is to check if $f$ is a Sum of Squares (SOS). If $f(x) = \sum h_i(x)^2$, it is clearly nonnegative. The advantage of SOS polynomials is that their existence can be verified efficiently using Semidefinite Programming (SDP).
However, not all nonnegative polynomials are SOS. This "gap" motivates the search for the best SOS approximation to a given nonnegative polynomial. While SOS polynomials are known to be dense in the set of nonnegative polynomials, finding an explicit best approximation for a fixed degree has remained a challenge. This paper addresses this by providing an explicit expression for the best $\ell_1$-norm approximation.
Methodology
The core contribution is the formulation of the best $\ell_1$-approximation as a convex optimization problem. The distance between polynomials is measured using the $\ell_1$-norm of their coefficients.
Lasserre proves that for a polynomial $f(x)$ of degree $2d$, the best SOS approximation $g(x)$ of the same or higher degree has a remarkably simple structure: $$g(x) = f(x) + \lambda^*_0 + \sum_{i=1}^n \lambda^*_i x_i^{2d}$$ This implies that the optimal SOS approximation is a specific perturbation of the original polynomial, adding only a constant and high-degree pure power terms. The coefficients $\lambda^* = (\lambda^*_0, \dots, \lambda^*_n)$ are determined by solving a standard SDP. Using duality theory and the theory of moments, the author shows that the total $\ell_1$ error, denoted $\rho_d$, is exactly the sum of these optimal weights: $\rho_d = \sum_{i=0}^n \lambda^*_i$.
Experimental Validation
The method is validated using the Motzkin-like polynomial: $$f(x_1, x_2) = x_1^2 x_2^2 (x_1^2 + x_2^2 - 1) + 1/27$$ This polynomial is nonnegative but not a sum of squares, making it a standard benchmark for testing SOS approximations.
Key Results
The approximation was computed for degrees $2d \in \{6, 8, 10\}$ (corresponding to $d=3, 4, 5$). The results demonstrate that as the degree $d$ increases, the approximation error $\rho_d$ decreases significantly.
As shown in the table above, for $d=3$, the error is approximately $1.6 \times 10^{-2}$. By $d=5$, the error drops to $8 \times 10^{-5}$, indicating a rapid convergence of the SOS approximation to the nonnegative polynomial as the degree increases.
Discussion and Conclusion
The primary insight of this work is the simplicity of the optimal perturbation. Finding the best SOS approximation does not require complex transformations but rather a targeted addition of specific terms. Because the problem reduces to a standard SDP, it can be solved in polynomial time for a fixed degree using existing software like GloptiPoly.
While the approach is theoretically sound and computationally accessible for moderate dimensions, the combinatorial growth of SDP matrices with respect to $n$ and $d$ remains a challenge for very high-dimensional problems. Future research may explore different norms, such as the $\ell_2$-norm or domain-specific norms, and the integration of these approximations into practical safety-critical systems.
Summary updated