EUVIMEDEUVIMED entdecken
Crossref

Convergence Rates of Sum-of-Squares Hierarchies for Polynomial Semidefinite Programs

Hoang Anh Tran, Kim-Chuan Toh

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →