论文标题
对Lasserre单变量测量的近距离分析，用于多个多项式优化
Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
论文作者
论文摘要
我们考虑了在紧凑型套装$ k \ subseteq \ mathbb {r}^n $最近提议的lasserre（Arxiv：1907.0977784，2019）最近提出的紧凑型$ k \ subseteq \ mathbb {r}^n $上最小化多项式$ f $的层次结构。该层次结构依赖于使用多项式$ f $在$ k $上的Lebesgue量度的推动力衡量标准，并涉及多项式$ 2R $ $ 2R $的多项式平方的单变量总和。因此，它比Lasserre的早期层次结构弱，但要便宜得多（Siam On Ofiplization on Optimization 21（3），864---885，2011），该等级使用了多变量的正方形。我们表明，这种新的层次结构在$ o（\ log^2 r / r^2）$中的$ f $的全球最低结构收敛，每当$ k $满足均衡的几何条件时，例如，对于凸体而言，对于紧凑型的半差异，该条件具有浓密的内部内部。作为应用程序，此收敛速率也适用于基于多元正方形总和的更强层次结构，该层次将改进并扩展到更早的融合结果到更广泛的紧凑型集合。此外，我们表明，通过证明$ k = [ - 1,1] $的一类多项式的$ω（1/r^2）$的收敛速率的下限，我们的分析几乎是最佳的，该分析是通过利用与正交多元元素的连接获得的。
We consider a hierarchy of upper approximations for the minimization of a polynomial $f$ over a compact set $K \subseteq \mathbb{R}^n$ proposed recently by Lasserre (arXiv:1907.097784, 2019). This hierarchy relies on using the push-forward measure of the Lebesgue measure on $K$ by the polynomial $f$ and involves univariate sums of squares of polynomials with growing degrees $2r$. Hence it is weaker, but cheaper to compute, than an earlier hierarchy by Lasserre (SIAM Journal on Optimization 21(3), 864--885, 2011), which uses multivariate sums of squares. We show that this new hierarchy converges to the global minimum of $f$ at a rate in $O(\log^2 r / r^2)$ whenever $K$ satisfies a mild geometric condition, which holds, e.g., for convex bodies and for compact semialgebraic sets with dense interior. As an application this rate of convergence also applies to the stronger hierarchy based on multivariate sums of squares, which improves and extends earlier convergence results to a wider class of compact sets. Furthermore, we show that our analysis is near-optimal by proving a lower bound on the convergence rate in $Ω(1/r^2)$ for a class of polynomials on $K=[-1,1]$, obtained by exploiting a connection to orthogonal polynomials.
