The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911916738215936 |
|---|---|
| author | Plávala, Martin Ligthart, Laurens T. Gross, David |
| author_facet | Plávala, Martin Ligthart, Laurens T. Gross, David |
| contents | We construct a convergent family of outer approximations for the problem of optimizing polynomial functions over convex bodies subject to polynomial constraints. This is achieved by generalizing the polarization hierarchy, which has previously been introduced for the study of polynomial optimization problems over state spaces of $C^*$-algebras, to convex cones in finite dimensions. If the convex bodies can be characterized by linear or semidefinite programs, then the same is true for our hierarchy. Convergence is proven by relating the problem to a certain de Finetti theorem for general probabilistic theories, which are studied as possible generalizations of quantum mechanics. We apply the method to the problem of nonnegative matrix factorization, and in particular to the nested rectangles problem. A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_09506 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank Plávala, Martin Ligthart, Laurens T. Gross, David Optimization and Control Quantum Physics We construct a convergent family of outer approximations for the problem of optimizing polynomial functions over convex bodies subject to polynomial constraints. This is achieved by generalizing the polarization hierarchy, which has previously been introduced for the study of polynomial optimization problems over state spaces of $C^*$-algebras, to convex cones in finite dimensions. If the convex bodies can be characterized by linear or semidefinite programs, then the same is true for our hierarchy. Convergence is proven by relating the problem to a certain de Finetti theorem for general probabilistic theories, which are studied as possible generalizations of quantum mechanics. We apply the method to the problem of nonnegative matrix factorization, and in particular to the nested rectangles problem. A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem. |
| title | The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank |
| topic | Optimization and Control Quantum Physics |
| url | https://arxiv.org/abs/2406.09506 |