S-SOS: Stochastic Sum-Of-Squares for Parametric Polynomial Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910485349138432 |
|---|---|
| author | Zhu, Richard L. Oster, Mathias Khoo, Yuehaw |
| author_facet | Zhu, Richard L. Oster, Mathias Khoo, Yuehaw |
| contents | Global polynomial optimization is an important tool across applied mathematics, with many applications in operations research, engineering, and physical sciences. In various settings, the polynomials depend on external parameters that may be random. We discuss a stochastic sum-of-squares (S-SOS) algorithm based on the sum-of squares hierarchy that constructs a series of semidefinite programs to jointly find strict lower bounds on the global minimum and extract candidates for parameterized global minimizers. We prove quantitative convergence of the hierarchy as the degree increases and use it to solve unconstrained and constrained polynomial optimization problems parameterized by random variables. By employing $n$-body priors from condensed matter physics to induce sparsity, we can use S-SOS to produce solutions and uncertainty intervals for sensor network localization problems containing up to 40 variables and semidefinite matrix sizes surpassing $800 \times 800$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_08954 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | S-SOS: Stochastic Sum-Of-Squares for Parametric Polynomial Optimization Zhu, Richard L. Oster, Mathias Khoo, Yuehaw Optimization and Control Global polynomial optimization is an important tool across applied mathematics, with many applications in operations research, engineering, and physical sciences. In various settings, the polynomials depend on external parameters that may be random. We discuss a stochastic sum-of-squares (S-SOS) algorithm based on the sum-of squares hierarchy that constructs a series of semidefinite programs to jointly find strict lower bounds on the global minimum and extract candidates for parameterized global minimizers. We prove quantitative convergence of the hierarchy as the degree increases and use it to solve unconstrained and constrained polynomial optimization problems parameterized by random variables. By employing $n$-body priors from condensed matter physics to induce sparsity, we can use S-SOS to produce solutions and uncertainty intervals for sensor network localization problems containing up to 40 variables and semidefinite matrix sizes surpassing $800 \times 800$. |
| title | S-SOS: Stochastic Sum-Of-Squares for Parametric Polynomial Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2406.08954 |