Leveraging Christoffel-Darboux Kernels to Strengthen Moment-SOS Relaxations
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915119840100352 |
|---|---|
| author | Ðurašinović, Srećko Azzi, Perla Lasserre, Jean-Bernard Magron, Victor Mula, Olga Zhao, Jun |
| author_facet | Ðurašinović, Srećko Azzi, Perla Lasserre, Jean-Bernard Magron, Victor Mula, Olga Zhao, Jun |
| contents | The classical Moment-Sum Of Squares hierarchy allows to approximate a global minimum of a polynomial optimization problem through semidefinite relaxations of increasing size. However, for many optimization instances, solving higher order relaxations becomes impractical or even impossible due to the substantial computational demands they impose. To address this, existing methods often exploit intrinsic problem properties, such as symmetries or sparsity. Here, we present a complementary approach, which enhances the accuracy of computationally more efficient low-order relaxations by leveraging Christoffel-Darboux kernels. Such strengthened relaxations often yield significantly improved bounds or even facilitate minimizer extraction. We illustrate the efficiency of our approach on several classes of important quadratically constrained quadratic Programs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_14281 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Leveraging Christoffel-Darboux Kernels to Strengthen Moment-SOS Relaxations Ðurašinović, Srećko Azzi, Perla Lasserre, Jean-Bernard Magron, Victor Mula, Olga Zhao, Jun Optimization and Control The classical Moment-Sum Of Squares hierarchy allows to approximate a global minimum of a polynomial optimization problem through semidefinite relaxations of increasing size. However, for many optimization instances, solving higher order relaxations becomes impractical or even impossible due to the substantial computational demands they impose. To address this, existing methods often exploit intrinsic problem properties, such as symmetries or sparsity. Here, we present a complementary approach, which enhances the accuracy of computationally more efficient low-order relaxations by leveraging Christoffel-Darboux kernels. Such strengthened relaxations often yield significantly improved bounds or even facilitate minimizer extraction. We illustrate the efficiency of our approach on several classes of important quadratically constrained quadratic Programs. |
| title | Leveraging Christoffel-Darboux Kernels to Strengthen Moment-SOS Relaxations |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.14281 |