EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

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:00
Room: 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

Status: accepted


Back to the list of papers