Abstract
This research establishes the first specialized degree bounds for Putinar’s Positivstellensatz on the hypercube $[-1, 1]^n$, a fundamental domain in polynomial optimization and computer science. The authors derive an upper bound of $O(f_{max}/f_{min})$ and a lower bound of $\Omega(\sqrt[8]{f_{max}/f_{min}})$, significantly narrowing the theoretical gap for the convergence rate of the moment-SOS hierarchy. These results provide a rigorous foundation for the efficiency of Putinar-type certificates in practical Semidefinite Programming (SDP) applications.
Introduction
A core challenge in polynomial optimization is certifying that a polynomial $f$ is strictly positive over a semi-algebraic set $S$. Real algebraic geometry addresses this through Positivstellensätze, which provide algebraic identities serving as certificates of positivity. Typically, these certificates represent $f$ as a Sum of Squares (SOS) combined with the inequalities defining $S$.
Two primary types of certificates dominate the literature:
- Schmüdgen-type: These utilize a "preordering," involving products of all defining inequalities. While they have well-established degree bounds, they require an exponential number of terms ($2^n$), making them computationally prohibitive for large-scale problems.
- Putinar-type: These utilize a "quadratic module," involving only individual defining inequalities. This results in a linear number of terms ($n+1$), which is highly efficient for Semidefinite Programming (SDP) via the Lasserre (moment-SOS) hierarchy.
Despite their practical utility, Putinar-type representations have historically lacked sharp degree bounds for specific domains. This paper addresses this gap for the hypercube, a ubiquitous domain in engineering and computer science.
Methodology
The authors employ a "lifting" strategy to derive the upper bound. Rather than analyzing the Putinar representation in isolation, they leverage the relationship between Schmüdgen and Putinar representations:
- Outer Approximation: The authors define a slightly larger "scaled" hypercube where the polynomial $f$ remains positive.
- Schmüdgen to Putinar Lifting: Utilizing known effective versions of Schmüdgen’s theorem for this larger domain, they "lift" the resulting representation into the more restrictive Putinar quadratic module of the original hypercube.
- Polynomial Identities: This lifting process relies on specific polynomial identities that demonstrate how products of inequalities can be expressed as sums of individual inequalities within defined degree constraints.
- Markov Brothers’ Inequality: To ensure the validity of the outer approximation, the authors use this classical tool from approximation theory to bound the derivatives of the polynomials.
For the lower bound, the authors construct a specific bivariate polynomial $(1-x^2)(1-y^2) + \varepsilon$. By applying quantitative versions of "non-stability" arguments, they demonstrate that as the polynomial approaches zero (i.e., as $\varepsilon \to 0$), the required degree for a Putinar certificate must grow at a specific polynomial rate.
Key Insights and Results
The research yields several critical insights into the behavior of Putinar representations on the hypercube:
Improved Upper Bounds
Previously, the best general bound for Putinar representations on the hypercube was $O((f_{max}/f_{min})^{10})$. This work slashes the exponent, establishing a linear relationship: $$r \geq O\left(d^2 \log n \cdot \frac{f_{max}}{f_{min}}\right)$$ where $r$ is the required degree, $d$ is the degree of $f$, and $n$ is the number of variables.
First Lower Bound for Non-Empty Interior
The authors establish the first lower bound for a set with a non-empty interior: $$r = \Omega\left(\sqrt[8]{\frac{f_{max}}{f_{min}}}\right)$$ This result proves that degree bounds must grow polynomially with the "flatness" of the function (the ratio $f_{max}/f_{min}$). It rules out the possibility of universal logarithmic degree bounds for general polynomials on the hypercube.
Convergence of the Lasserre Hierarchy
These bounds directly quantify the convergence rate of the Lasserre hierarchy. Specifically, the error in the lower bounds produced by the hierarchy is shown to decrease at a rate of $O(1/r)$, providing a theoretical guarantee for the performance of SOS-based optimization.
Discussion and Future Work
While this paper significantly narrows the gap between upper and lower bounds, several open questions remain. The current gap between the linear upper bound and the eighth-root lower bound suggests that further sharpening is possible. Additionally, while the dependence on the $f_{max}/f_{min}$ ratio is much improved, the constants related to the number of variables ($n$) and the intrinsic degree ($d$) could be further optimized.
Finally, the authors suggest that if a polynomial satisfies "strict local optimality"—meaning it does not remain "flat" near its minimum—much better (potentially logarithmic) bounds might be achievable, analogous to recent findings in trigonometric polynomial optimization.
Summary updated