Improved convergence analysis of Lasserre’s measure-based upper bounds for polynomial minimization on compact sets

Abstract

Abstract We consider the problem of computing the minimum value $$f_{\min ,K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>min</mml:mo> <mml:mo>,</mml:mo> <mml:mi>K</mml:mi> </mml:mrow> </mml:msub> </mml:math> of a polynomial f over a compact set $$K\subseteq {\mathbb {R}}^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo>⊆</mml:mo> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:math> , which can be reformulated as finding a probability measure $$\nu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ν</mml:mi> </mml:math> on $$K$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>K</mml:mi> </mml:math> minimizing $$\int _Kf d\nu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mo>∫</mml:mo> <mml:mi>K</mml:mi> </mml:msub> <mml:mi>f</mml:mi> <mml:mi>d</mml:mi> <mml:mi>ν</mml:mi> </mml:mrow> </mml:math> . Lasserre showed that it suffices to consider such measures of the form $$\nu = q\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ν</mml:mi> <mml:mo>=</mml:mo> <mml:mi>q</mml:mi> <mml:mi>μ</mml:mi> </mml:mrow> </mml:math> , where q is a sum-of-squares polynomial and $$\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>μ</mml:mi> </mml:math> is a given Borel measure supported on $$K$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>K</mml:mi> </mml:math> . By bounding the degree of q by 2 r one gets a converging hierarchy of upper bounds $$f^{(r)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>r</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> for $$f_{\min ,K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>min</mml:mo> <mml:mo>,</mml:mo> <mml:mi>K</mml:mi> </mml:mrow> </mml:msub> </mml:math> . When K is the hypercube $$[-1, 1]^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mo>[</mml:mo> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>]</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:math> , equipped with the Chebyshev measure, the parameters $$f^{(r)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>r</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> are known to converge to $$f_{\min , K}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>min</mml:mo> <mml:mo>,</mml:mo> <mml:mi>K</mml:mi> </mml:mrow> </mml:msub> </mml:math> at a rate in $$O(1/r^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:msup> <mml:mi>r</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>r</mml:mi> <mml:mo>/</mml:mo> <mml:mi>r</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> when $$K$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>K</mml:mi> </mml:math> satisfies a minor geometrical condition, and in $$O(\log ^2 r / r^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mo>log</mml:mo> <mml:mn>2</mml:mn> </mml:msup> <mml:mi>r</mml:mi> <mml:mo>/</mml:mo> <mml:msup> <mml:mi>r</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> when $$K$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>K</mml:mi> </mml:math> is a convex body, equipped with the Lebesgue measure. This improves upon the currently best known error estimates in $$O(1 / \sqrt{r})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:msqrt> <mml:mi>r</mml:mi> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$O(1/r)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi>

Topics & Concepts