TY - GEN
T1 - A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
AU - Gribling, Sander
AU - Polak, Sven C.
AU - Slot, Lucas
N1 - Publisher Copyright:
© 2023 Owner/Author.
PY - 2023/7/24
Y1 - 2023/7/24
N2 - 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 moment-SOS 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.
AB - 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 moment-SOS 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.
KW - computational complexity
KW - moment-SOS hierarchy
KW - moments
KW - polynomial optimization
KW - semidefinite programming
KW - sums of squares
UR - http://www.scopus.com/inward/record.url?scp=85167789391&partnerID=8YFLogxK
U2 - 10.1145/3597066.3597075
DO - 10.1145/3597066.3597075
M3 - Conference contribution
T3 - ACM International Conference Proceeding Series
SP - 280
EP - 288
BT - ISSAC 2023 - Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation
A2 - Jeronimo, Gabriela
PB - ACM Digital Library
CY - Tromso
T2 - The 2023 International Symposium on Symbolic and Algebraic Computation
Y2 - 24 July 2023 through 28 July 2023
ER -