# An effective version of Schm"udgen's Positivstellensatz for the hypercube

arXiv: https://arxiv.org/abs/2109.09528 · HTML: https://mlsanity.com/paper/2109.09528/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2021.

## Built on by (most cited first, 1 of 1)

- [GloptiNets: Scalable Non-Convex Optimization with Certificates](https://mlsanity.com/paper/2306.14932/) (2023)

## Abstract (arXiv)

Let S subseteq ℝn be a compact semialgebraic set and let f be a polynomial nonnegative on S. Schm"udgen's Positivstellensatz then states that for any η > 0, the nonnegativity of f + η on S can be certified by expressing f + η 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"udgen-type certificate of nonnegativity exists involving only polynomials of degree O(1 / √η). This improves quadratically upon the previously best known estimate in O(1/η). Our proof relies on an application of the polynomial kernel method, making use in particular of the Jackson kernel on the interval [-1, 1].