Bound-constrained polynomial optimization using only elementary calculations

We provide a monotone non increasing sequence of upper bounds $f_k^H$ ($k\ge 1$)convergingtotheglobalminimumofapolynomial$f$ on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, pp. 864–885, 2010] is that only elementary computations are required. For optimization over the hypercube, we show that the new bounds $f_k^H$ have a rate of convergence in $O(1/\sqrt {k})$\mathrm{.}Moreoverweshowastrongerconvergenceratein$O(1/k)$ for quadratic polynomials and more generally for polynomials having a rational minimizer in the hypercube. In comparison, evaluation of all rational grid points with denominator $k$ produces bounds with a rate of convergence in $O(1\mathrm{/}{k}^2)$, but at the cost of $O(k^n)$ function evaluations, while the new bound $f_k^H$ needs only $O(n^k)$ elementary calculations.