Convergence Rates of Sum-of-Squares Hierarchies for Polynomial Semidefinite Programs
SIAM Journal on Optimization · 30.06.2026 · 36 (2) · 760-790
DOI: 10.1137/24m1670184 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 29.04.2026. Verfasst von Hoang Anh Tran und 1 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben.
Abstract (Originalsprache)
We introduce a novel moment-sum-of-squares (SOS) hierarchy of lower bounds for a polynomial optimization problem whose feasible set is defined by polynomial matrix inequalities. Our hierarchy avoids the Kronecker product structure in Hol and Scherer’s hierarchy, thus resulting in smaller-sized semidefinite programs. Our approach involves utilizing a penalty function framework to directly address the matrix-based constraint, which is applicable to both discrete and continuous polynomial optimization problems. We investigate the convergence rates of these bounds for both types of problems. The proposed method yields a variant of Putinar’s theorem, tailored for positive polynomials on a compact set [Formula: see text] defined by a polynomial matrix inequality. More specifically, we derive novel insights into the bounds on the degree of the SOS polynomials required to certify positivity over [Formula: see text], based on Jackson’s theorem and a variant of the Łojasiewicz inequality in the matrix setting.
Zitieren
APA
Tran, H. A., & Toh, K. (2026). Convergence Rates of Sum-of-Squares Hierarchies for Polynomial Semidefinite Programs. SIAM Journal on Optimization, 36(2), 760-790. https://doi.org/10.1137/24m1670184
Vancouver
Tran HA, Toh K. Convergence Rates of Sum-of-Squares Hierarchies for Polynomial Semidefinite Programs. SIAM Journal on Optimization. 2026;36(2):760-790. doi:10.1137/24m1670184
BibTeX
@article{Tran2026,
author = {Tran, Hoang Anh and Toh, Kim-Chuan},
title = {Convergence Rates of Sum-of-Squares Hierarchies for Polynomial Semidefinite Programs},
journal = {SIAM Journal on Optimization},
year = {2026},
volume = {36},
number = {2},
pages = {760--790},
doi = {10.1137/24m1670184}
}
EUVIMED