A hierarchy of eigencomputations for polynomial optimization on the sphere
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918090751606784 |
|---|---|
| author | Lovitz, Benjamin Johnston, Nathaniel |
| author_facet | Lovitz, Benjamin Johnston, Nathaniel |
| contents | We introduce a convergent hierarchy of lower bounds on the minimum value of a real form over the unit sphere. The main practical advantage of our hierarchy over the real sum-of-squares (RSOS) hierarchy is that the lower bound at each level of our hierarchy is obtained by a minimum eigenvalue computation, as opposed to the full semidefinite program (SDP) required at each level of RSOS. In practice, this allows us to compute bounds on much larger forms than are computationally feasible for RSOS. Our hierarchy outperforms previous alternatives to RSOS, both asymptotically and in numerical experiments. We obtain our hierarchy by proving a reduction from real optimization on the sphere to Hermitian optimization on the sphere, and invoking the Hermitian sum-of-squares (HSOS) hierarchy. This opens the door to using other Hermitian optimization techniques for real optimization, and gives a path towards developing spectral hierarchies for more general constrained real optimization problems. To this end, we use our techniques to develop a hierarchy of eigencomputations for computing the real tensor spectral norm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_17827 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A hierarchy of eigencomputations for polynomial optimization on the sphere Lovitz, Benjamin Johnston, Nathaniel Optimization and Control Data Structures and Algorithms Algebraic Geometry Quantum Physics We introduce a convergent hierarchy of lower bounds on the minimum value of a real form over the unit sphere. The main practical advantage of our hierarchy over the real sum-of-squares (RSOS) hierarchy is that the lower bound at each level of our hierarchy is obtained by a minimum eigenvalue computation, as opposed to the full semidefinite program (SDP) required at each level of RSOS. In practice, this allows us to compute bounds on much larger forms than are computationally feasible for RSOS. Our hierarchy outperforms previous alternatives to RSOS, both asymptotically and in numerical experiments. We obtain our hierarchy by proving a reduction from real optimization on the sphere to Hermitian optimization on the sphere, and invoking the Hermitian sum-of-squares (HSOS) hierarchy. This opens the door to using other Hermitian optimization techniques for real optimization, and gives a path towards developing spectral hierarchies for more general constrained real optimization problems. To this end, we use our techniques to develop a hierarchy of eigencomputations for computing the real tensor spectral norm. |
| title | A hierarchy of eigencomputations for polynomial optimization on the sphere |
| topic | Optimization and Control Data Structures and Algorithms Algebraic Geometry Quantum Physics |
| url | https://arxiv.org/abs/2310.17827 |