2026-07-24T08:49:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16420 2024-03-06T10:57:26Z ddc:004 open_access

A Faster Interior-Point Method for Sum-Of-Squares Optimization Jiang, Shunhua Natura, Bento Weinstein, Omri Interior Point Methods Sum-of-squares Optimization Dynamic Matrix Inverse We present a faster interior-point method for optimizing sum-of-squares (SOS) polynomials, which are a central tool in polynomial optimization and capture convex programming in the Lasserre hierarchy. Let p = ∑_i q²_i be an n-variate SOS polynomial of degree 2d. Denoting by L : = binom(n+d,d) and U : = binom(n+2d,2d) the dimensions of the vector spaces in which q_i’s and p live respectively, our algorithm runs in time Õ(LU^{1.87}). This is polynomially faster than state-of-art SOS and semidefinite programming solvers [Jiang et al., 2020; Huang et al., 2021; Papp and Yildiz, 2019], which achieve runtime Õ(L^{0.5} min{U^{2.37}, L^{4.24}}). The centerpiece of our algorithm is a dynamic data structure for maintaining the inverse of the Hessian of the SOS barrier function under the polynomial interpolant basis [Papp and Yildiz, 2019], which efficiently extends to multivariate SOS optimization, and requires maintaining spectral approximations to low-rank perturbations of elementwise (Hadamard) products. This is the main challenge and departure from recent IPM breakthroughs using inverse-maintenance, where low-rank updates to the slack matrix readily imply the same for the Hessian matrix. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shunhua Jiang and Bento Natura and Omri Weinstein 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.79 urn:nbn:de:0030-drops-164205 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.79 eng https://creativecommons.org/licenses/by/4.0/legalcode