Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

We provide a monotone nonincreasing sequence of upper bounds $f_k^H\left(k\ge 1\right)$ converging to the global minimum of a polynomial f on simple sets like the unit hypercube in ℝⁿ. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21:864–885] is that only elementary computations are required. For optimization over the hypercube [0, 1]ⁿ, we show that the new bounds $f_k^H$ have a rate of convergence in $O\left(1/\sqrt{k}\right)$. Moreover, we show a stronger convergence rate in 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/k²), but at the cost of O(kⁿ) function evaluations, while the new bound $f_k^H$ needs only O(n^k) elementary calculations.