The link between $1$-norm approximation and effective Positivstellensatze for the hypercube

Abstract

The Schmüdgen's Positivstellensatz gives a certificate to verify positivity of a strictly positive polynomial $f$ on a compact, basic, semi-algebraic set $\mathbf{K}\subset {\mathbb{R}}^n$. A Positivstellensatz of this type is called effective if one may bound the degrees of the polynomials appearing in the certificate in terms of properties of $f$. If $\mathbf{K}=[-1,1{]}^n$ and $0 < f_\min := \min_{x \in \mathbf{K}} f(x)$, then the degrees of the polynomials appearing in the certificate may be bounded by $O\left(\sqrt{\frac{f_\max - f_\min}{f_\min}}\right)$, where $f_\max := \max_{x \in \mathbf{K}} f(x)$, as was recently shown by Laurent and Slot [Optimization Letters 17:515-530, 2023]. The big-O notation suppresses dependence on $n$ and the degree $d$ of $f$. In this paper we show a similar result, but with a better dependence on $n$ and $d$. In particular, our bounds depend on the $1$-norm of the coefficients of $f$, that may readily be calculated.