Improved convergence analysis of Lasserre’s measure-based upper bounds for polynomial minimization on compact sets
Mathematical Programming , Volume 2020
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.
|Polynomial optimization, Sum-of-squares polynomial, Lasserre hierarchy, Semidefinite programming, Needle polynomial|
|Organisation||Networks and Optimization|
Slot, L.F.H, & Laurent, M. (2020). Improved convergence analysis of Lasserre’s measure-based upper bounds for polynomial minimization on compact sets. Mathematical Programming, 2020. doi:10.1007/s10107-020-01468-3