Exactness and Effective Degree Bound of Lasserre's Relaxation for Polynomial Optimization over Finite Variety
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2021
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908386638954496 |
|---|---|
| author | Hua, Zheng Qu, Zheng |
| author_facet | Hua, Zheng Qu, Zheng |
| contents | In this paper, we address the effective degree bound problem for Lasserre's hierarchy of moment-sum-of-squares (SOS) relaxations in polynomial optimization involving $n$ variables. We assume that the first $n$ equality constraint polynomials $g_1,\ldots,g_n$ do not share any nontrivial common complex zero locus at infinity and that the optimal solutions are nonsingular. Under these conditions, we derive an effective degree bound for the exactness of Lasserre's hierarchy. Importantly, the assumption of no solutions at infinity holds on a Zariski open set within the space of polynomials of fixed degrees. As a direct consequence, we provide the first explicit degree bound for gradient-type SOS relaxation under a generic condition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_13766 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Exactness and Effective Degree Bound of Lasserre's Relaxation for Polynomial Optimization over Finite Variety Hua, Zheng Qu, Zheng Optimization and Control 90C23, 68Q25, 90C60 In this paper, we address the effective degree bound problem for Lasserre's hierarchy of moment-sum-of-squares (SOS) relaxations in polynomial optimization involving $n$ variables. We assume that the first $n$ equality constraint polynomials $g_1,\ldots,g_n$ do not share any nontrivial common complex zero locus at infinity and that the optimal solutions are nonsingular. Under these conditions, we derive an effective degree bound for the exactness of Lasserre's hierarchy. Importantly, the assumption of no solutions at infinity holds on a Zariski open set within the space of polynomials of fixed degrees. As a direct consequence, we provide the first explicit degree bound for gradient-type SOS relaxation under a generic condition. |
| title | Exactness and Effective Degree Bound of Lasserre's Relaxation for Polynomial Optimization over Finite Variety |
| topic | Optimization and Control 90C23, 68Q25, 90C60 |
| url | https://arxiv.org/abs/2110.13766 |