We consider the problem of computing the minimum value fmin,K of a polynomial f over a compact set K⊆Rn, which can be reformulated as finding a probability measure ν on K minimizing ∫Kfdν. Lasserre showed that it suffices to consider such measures of the form ν=qμ, where q is a sum-of-squares polynomial and μ is a given Borel measure supported on K. By bounding the degree of q by 2r one gets a converging hierarchy of upper bounds f(r) for fmin,K. When K is the hypercube [−1,1]n, equipped with the Chebyshev measure, the parameters f(r) are known to converge to fmin,K at a rate in O(1/r2). We extend this error estimate to a wider class of convex bodies, while also allowing for a broader class of reference measures, including the Lebesgue measure. Our analysis applies to simplices, balls and convex bodies that locally look like a ball. In addition, we show an error estimate in O(logr/r) when K satisfies a minor geometrical condition, and in O(log2r/r2) when K is a convex body, equipped with the Lebesgue measure. This improves upon the currently best known error estimates in O(1/r√) and O(1/r) for these two respective cases.

, , , ,
doi.org/10.1007/s10107-020-01468-3
Mathematical Programming
Mixed-Integer Nonlinear Optimization
Networks and Optimization

Slot, L., & Laurent, M. (2020). Improved convergence analysis of Lasserre’s measure-based upper bounds for polynomial minimization on compact sets. Mathematical Programming, 193, 831–871. doi:10.1007/s10107-020-01468-3