We consider the problem of computing the minimum value of a polynomial f over a compact set K⊆R^n, which can be reformulated as finding a probability measure ν on K minimizing the expected value of f over K. 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 for the original minimization problem. When K is the hypercube [−1,1]^n, equipped with the Chebyshev measure, these bounds are known to converge to the minimum value of f at a rate in O(1/r^2). 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(log(r)/r) when K satisfies a minor geometrical condition, and in O((log(r)/r)^2) when K is a convex body, equipped with the Lebesgue measure. This improves upon the currently best known error estimates in O(1/sqrt(r)) and O(1/r) for these two respective cases.
Citation
arXiv:1905.08142