Refined TSSOS
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916118310944768 |
|---|---|
| author | Shaydurova, Daria Kaibel, Volker Sager, Sebastian |
| author_facet | Shaydurova, Daria Kaibel, Volker Sager, Sebastian |
| contents | The moment-sum of squares hierarchy by Lasserre has become an established technique for solving polynomial optimization problems. It provides a monotonically increasing series of tight bounds, but has well-known scalability limitations. For structured optimization problems, the term-sparsity SOS (TSSOS) approach scales much better due to block-diagonal matrices, obtained by completing the connected components of adjacency graphs. This block structure can be exploited by semidefinite programming solvers, for which the overall runtime then depends heavily on the size of the largest block. However, already the first step of the TSSOS hierarchy may result in large diagonal blocks. We suggest a new approach that refines TSSOS iterations using combinatorial optimization and results in block-diagonal matrices with reduced maximum block sizes. Numerical results on a benchmark library show the large potential for computational speedup for unconstrained and constrained polynomial optimization problems, while obtaining almost identical bounds in comparison to established methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05444 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Refined TSSOS Shaydurova, Daria Kaibel, Volker Sager, Sebastian Optimization and Control 14P10, 90C25, 12D15, 12Y05, 90C10 The moment-sum of squares hierarchy by Lasserre has become an established technique for solving polynomial optimization problems. It provides a monotonically increasing series of tight bounds, but has well-known scalability limitations. For structured optimization problems, the term-sparsity SOS (TSSOS) approach scales much better due to block-diagonal matrices, obtained by completing the connected components of adjacency graphs. This block structure can be exploited by semidefinite programming solvers, for which the overall runtime then depends heavily on the size of the largest block. However, already the first step of the TSSOS hierarchy may result in large diagonal blocks. We suggest a new approach that refines TSSOS iterations using combinatorial optimization and results in block-diagonal matrices with reduced maximum block sizes. Numerical results on a benchmark library show the large potential for computational speedup for unconstrained and constrained polynomial optimization problems, while obtaining almost identical bounds in comparison to established methods. |
| title | Refined TSSOS |
| topic | Optimization and Control 14P10, 90C25, 12D15, 12Y05, 90C10 |
| url | https://arxiv.org/abs/2402.05444 |