A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
Open access
Date
2023Type
- Conference Paper
Abstract
The moment-sum-of-squares (moment-SOS) hierarchy is one of the most celebrated and widely applied methods for approximating the minimum of an n-variate polynomial over a feasible region defined by polynomial (in)equalities. A key feature of the hierarchy is that, at a fixed level, it can be formulated as a semidefinite program of size polynomial in the number of variables n. Although this suggests that it may therefore be computed in polynomial time, this is not necessarily the case. Indeed, as O'Donnell [16] and later Raghavendra & Weitz [20] show, there exist examples where the sos-representations used in the hierarchy have exponential bit-complexity. We study the computational complexity of the momentSOS hierarchy, complementing and expanding upon earlier work of Raghavendra & Weitz [20]. In particular, we establish algebraic and geometric conditions under which polynomial-time computation is guaranteed to be possible. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000627799Publication status
publishedExternal links
Book title
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic ComputationPages / Article No.
Publisher
Association for Computing MachineryEvent
Subject
moment-SOS hierarchy; sums of squares; moments; computational complexity; polynomial optimization; semidefinite programmingOrganisational unit
09622 - Steurer, David / Steurer, David
More
Show all metadata