An effective version of Schmüdgen's Positivstellensatz for the hypercube

Monique Laurent, Lucas SlotOptim. Lett 2023 · OpenReview

Abstract

Let $S \subseteq \mathbb{R}^n$ be a compact semialgebraic set and let $f$ be a polynomial nonnegative on $S$. Schmüdgen’s Positivstellensatz states that for any $\eta > 0$, the nonnegativity of $f + \eta$ on $S$ can be certified by expressing $f + \eta$ as a conic combination of products of the polynomials that occur in the inequalities defining $S$, where the coefficients are sum-of-squares (SOS) polynomials. However, it does not provide explicit bounds on the degree of the polynomials required. This paper demonstrates that for the hypercube $S = [-1, 1]^n$, a Schmüdgen-type certificate exists involving polynomials of degree $O(1 / \sqrt{\eta})$. This improves quadratically upon the previously best known estimate of $O(1/\eta)$ by applying the polynomial kernel method, specifically utilizing the Jackson kernel on the interval $[-1, 1]$.

Introduction

In the field of global optimization, determining the minimum value of a polynomial $f$ over a set $S$ is a fundamental yet NP-hard problem. To address this, researchers utilize "certificates of nonnegativity." If one can prove $f - \lambda \ge 0$ for all $x \in S$, then $\lambda$ serves as a valid lower bound for the optimization problem.

Schmüdgen’s Positivstellensatz is a landmark result in real algebraic geometry that guarantees such certificates exist for compact semialgebraic sets. It ensures that any polynomial strictly positive on $S$ can be represented using the constraints of $S$ and SOS polynomials. While theoretically powerful, the theorem's practical utility is limited by the lack of explicit bounds on the degree $r$ of the polynomials involved. High degrees lead to exponential growth in the size of the resulting Semidefinite Programming (SDP) problems. This research focuses on the hypercube $[-1, 1]^n$, a common domain in engineering and computer science, to establish tighter, more effective degree bounds.

Methodology: The Polynomial Kernel Method

To derive improved bounds, the authors move away from purely algebraic proofs, instead employing the polynomial kernel method from functional analysis and approximation theory. The core of their approach involves the multivariate Jackson kernel, which is renowned for its ability to approximate functions with high precision using low-degree polynomials.

The Jackson Kernel and Linear Operators

The authors define a linear operator $\mathbf{K}_r$ based on the Jackson kernel. This operator possesses two critical properties for certification:

  1. It maps any nonnegative polynomial into the "preordering" (the set of polynomials with a Schmüdgen-type certificate).
  2. The approximation error—the distance between the original polynomial and its transformed version—is strictly bounded.
Figure 1: Visualization of the kernel-based approximation of a polynomial $f(x) + \eta$ using the operator $\mathbf{K}_r$ for degrees $r=5$ and $r=7$.

As shown in the figure above, the operator $\mathbf{K}_r$ provides an increasingly accurate approximation of the target polynomial as the degree $r$ increases. The analysis is conducted using the basis of Chebyshev polynomials, as the Jackson kernel diagonalizes within this basis, allowing for a precise analysis of the operator's eigenvalues to derive error bounds.

Key Results: Achieving Quadratic Improvement

The primary contribution of this work is the quadratic improvement in the convergence rate of the Lasserre hierarchy for the hypercube. Previous methods, such as those using the Bernstein operator, yielded a degree bound of $O(1/\eta)$. By utilizing the Jackson kernel, the authors prove a degree bound of $O(1/\sqrt{\eta})$.

Theorem 2 and Convergence Rates

The authors establish that for a polynomial $f$ of degree $d$, the error in the Lasserre hierarchy lower bound $f_{(r)}$ is bounded by:

$$f_{\min} - f_{(r)} \leq \frac{C(n, d)}{r^2} (f_{\max} - f_{\min})$$

where $C(n, d)$ is a constant depending on the dimension $n$ and degree $d$. This $O(1/r^2)$ convergence rate directly implies that to certify the nonnegativity of $f + \eta$, a degree of $r = O(1/\sqrt{\eta})$ is sufficient. Notably, this $O(1/r^2)$ upper bound matches a known lower bound established by Stengle in 1996 for specific interval descriptions, suggesting that this result may be the optimal "natural" limit for such hierarchies.

Discussion and Future Directions

While this paper provides a significant advancement for the hypercube, several questions remain. The current results apply to the preordering, which involves products of all constraints. In practice, many SDP solvers utilize the quadratic module (Putinar-type certificates), which is computationally simpler. It is currently unknown if the $O(1/\sqrt{\eta})$ bound holds for Putinar-type certificates on the hypercube.

Additionally, the constant $C(n, d)$ still maintains a dependence on the number of variables $n$. While dimension-independent bounds exist for spheres and boolean cubes, finding a "dimension-free" constant for the continuous hypercube remains a challenging frontier. Finally, extending this kernel-based approach to more general semialgebraic sets could further revolutionize the efficiency of polynomial optimization solvers.

Summary updated

Abstract

Let \(S \subseteq \mathbb {R}^n\) be a compact semialgebraic set and let f be a polynomial nonnegative on S. Schmüdgen’s Positivstellensatz then states that for any \(\eta > 0\), the nonnegativity of \(f + \eta\) on S can be certified by expressing \(f + \eta\) as a conic combination of products of the polynomials that occur in the inequalities defining S, where the coefficients are (globally nonnegative) sum-of-squares polynomials. It does not, however, provide explicit bounds on the degree of the polynomials required for such an expression. We show that in the special case where \(S = [-1, 1]^n\) is the hypercube, a Schmüdgen-type certificate of nonnegativity exists involving only polynomials of degree \(O(1 / \sqrt{\eta })\). This improves quadratically upon the previously best known estimate in \(O(1/\eta )\). Our proof relies on an application of the polynomial kernel method, making use in particular of the Jackson kernel on the interval \([-1, 1]\).
BibTeX
@inproceedings{laurent2023effective,
  author = {Monique Laurent and Lucas Slot},
  title = {{An effective version of Schmüdgen's Positivstellensatz for the hypercube}},
  booktitle = {Optim. Lett},
  year = {2023},
  url = {https://openreview.net/forum?id=76LOogUEn6},
}
Figure