
arXiv: 2111.04610
Consider the problem of minimizing a polynomial $f$ over a compact semialgebraic set ${\mathbf{X} \subseteq \mathbb{R}^n}$. Lasserre introduces hierarchies of semidefinite programs to approximate this hard optimization problem, based on classical sum-of-squares certificates of positivity of polynomials due to Putinar and Schmüdgen. When $\mathbf{X}$ is the unit ball or the standard simplex, we show that the hierarchies based on the Schmüdgen-type certificates converge to the global minimum of $f$ at a rate in $O(1/r^2)$, matching recently obtained convergence rates for the hypersphere and hypercube $[-1,1]^n$. For our proof, we establish a connection between Lasserre's hierarchies and the Christoffel-Darboux kernel, and make use of closed form expressions for this kernel derived by Xu.
v3: Fixed a technical error in the (proof of) Lemma 18. This has a (minor) impact on the constants appearing in Theorems 3, 4
Polynomial optimization, Positivstellensatz, [MATH] Mathematics [math], Nonconvex programming, global optimization, polynomial optimization Positivstellensatz sum-of-squares hierarchy Christoffel-Darboux kernel polynomial kernel method, Optimization and Control (math.OC), polynomial optimization, Christoffel-Darboux kernel, FOS: Mathematics, sum-of-squares hierarchy, polynomial kernel method, Semidefinite programming, 90C22, 90C23, 90C26, Mathematics - Optimization and Control
Polynomial optimization, Positivstellensatz, [MATH] Mathematics [math], Nonconvex programming, global optimization, polynomial optimization Positivstellensatz sum-of-squares hierarchy Christoffel-Darboux kernel polynomial kernel method, Optimization and Control (math.OC), polynomial optimization, Christoffel-Darboux kernel, FOS: Mathematics, sum-of-squares hierarchy, polynomial kernel method, Semidefinite programming, 90C22, 90C23, 90C26, Mathematics - Optimization and Control
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
