Sum-of-squares hierarchies for polynomial optimization and the Christoffel-Darboux kernel
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909162431053824 |
|---|---|
| author | Slot, Lucas |
| author_facet | Slot, Lucas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_04610 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Sum-of-squares hierarchies for polynomial optimization and the Christoffel-Darboux kernel Slot, Lucas Optimization and Control 90C22, 90C23, 90C26 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. |
| title | Sum-of-squares hierarchies for polynomial optimization and the Christoffel-Darboux kernel |
| topic | Optimization and Control 90C22, 90C23, 90C26 |
| url | https://arxiv.org/abs/2111.04610 |