<p>The moment-SOS hierarchy, which is based on Putinar-type (quadratic module) and Schmüdgen-type (preordering) sum-of-squares positivity certificates, is a widely applicable framework to address polynomial optimization problems over basic semi-algebraic sets. Recent works show that the convergence rate of this hierarchy over certain simple sets, namely, the unit ball, hypercube, and standard simplex, is of the order <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\textrm{O}(1/r^2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>O</mtext> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <msup> <mi>r</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <i>r</i> denotes the level of the moment-SOS hierarchy. This paper aims to provide a comprehensive understanding of the convergence rate of the Schmüdgen-type moment-SOS hierarchy by estimating the Hausdorff distance between the set of truncated pseudo-moment sequences and the set of truncated moment sequences through a projection-based method derived from Tchakaloff’s theorem. Our results provide a connection between the convergence rate of the Schmüdgen-type moment-SOS hierarchy and the Łojasiewicz exponent <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\textit{\L} \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Ł</mi> </math></EquationSource> </InlineEquation> of the domain under the compactness assumption, where we establish the convergence rate of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\textrm{O}(1/r^\textit{\L} )\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>O</mtext> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <msup> <mi>r</mi> <mi mathvariant="normal">Ł</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Consequently, we obtain the convergence rate of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\textrm{O}(1/r)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>O</mtext> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>r</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for polytopes and sets satisfying the constraint qualification condition, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\textrm{O}(1/\sqrt{r})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>O</mtext> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <msqrt> <mi>r</mi> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for domains that either satisfy the Polyak-Łojasiewicz condition or are defined by locally strongly convex polynomials. We also use our method to reprove the convergence rate of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\textrm{O}(1/r^2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>O</mtext> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <msup> <mi>r</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for general polynomials over a sphere.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the convergence rates of moment-SOS hierarchies approximation of truncated moment sequences

  • Hoang Anh Tran,
  • Kim-Chuan Toh

摘要

The moment-SOS hierarchy, which is based on Putinar-type (quadratic module) and Schmüdgen-type (preordering) sum-of-squares positivity certificates, is a widely applicable framework to address polynomial optimization problems over basic semi-algebraic sets. Recent works show that the convergence rate of this hierarchy over certain simple sets, namely, the unit ball, hypercube, and standard simplex, is of the order \(\textrm{O}(1/r^2)\) O ( 1 / r 2 ) , where r denotes the level of the moment-SOS hierarchy. This paper aims to provide a comprehensive understanding of the convergence rate of the Schmüdgen-type moment-SOS hierarchy by estimating the Hausdorff distance between the set of truncated pseudo-moment sequences and the set of truncated moment sequences through a projection-based method derived from Tchakaloff’s theorem. Our results provide a connection between the convergence rate of the Schmüdgen-type moment-SOS hierarchy and the Łojasiewicz exponent \(\textit{\L} \) Ł of the domain under the compactness assumption, where we establish the convergence rate of \(\textrm{O}(1/r^\textit{\L} )\) O ( 1 / r Ł ) . Consequently, we obtain the convergence rate of \(\textrm{O}(1/r)\) O ( 1 / r ) for polytopes and sets satisfying the constraint qualification condition, \(\textrm{O}(1/\sqrt{r})\) O ( 1 / r ) for domains that either satisfy the Polyak-Łojasiewicz condition or are defined by locally strongly convex polynomials. We also use our method to reprove the convergence rate of \(\textrm{O}(1/r^2)\) O ( 1 / r 2 ) for general polynomials over a sphere.