EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2164. Refined TSSOS
Invited abstract in session TA-38: Special Classes of Convex Conic Optimization problems, stream Conic Optimization: Theory, Algorithms, and Applications.
Tuesday, 8:30-10:00Room: 34 (building: 306)
Authors (first author is the speaker)
| 1. | Daria Shaydurova
|
| Faculty of Mathematics, Otto-von-Guericke-Universität Magdeburg | |
| 2. | Volker Kaibel
|
| Institut für Mathematische Optimierung, Otto-von-Guericke-Universität Magdeburg | |
| 3. | Sebastian Sager
|
| Faculty of Mathematics, Otto-von-Guericke-Universität Magdeburg |
Abstract
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.
Keywords
- Global Optimization
- Programming, Semidefinite
Status: accepted
Back to the list of papers