A Bounded Degree SOS Plus SONC Hierarchy for Polynomial Optimization
Abstract
We propose a bounded degree SOS+SONC hierarchy for constrained polynomial optimization, termed B-SOS+SONC. Starting from Lasserre's bounded-degree SOS framework, we enlarge the certificate cone from SOS to the recently introduced SOS+SONC cone, thereby combining the algebraic strength of semidefinite relaxations with the sparse structure captured by circuit polynomials. We show that, for each fixed certificate degree, the resulting hierarchy is complete, that is, its optimal values are monotone and converge to the global optimum. Moreover, we derive an explicit SDP-REP reformulation, so that each relaxation can be solved within a tractable convex optimization framework over semidefinite and relative entropy cones. Beyond the optimization hierarchy itself, we investigate structural properties of the SONC cone and introduce the notions of first-order and second-order SONC-convexity. This leads to a new sufficient condition for first-level exactness of the B-SOS+SONC hierarchy. Numerical experiments illustrate that the proposed hierarchy often yields tighter lower bounds than the B-SOS relaxation while remaining tractable.
Related
- A bounded degree SDSOS hierarchy for solving SPLD polynomial programs
- Linear Independence of Polynomial Compositions with Bounded Input Degree
- The weak cylinder conjecture for polynomial graphs of bounded degree
- Comment on "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank"
- Convergence rate of the moment-SOS hierarchy for univariate polynomial optimization
BibTeX
@misc{dressler2026bounded,
title = {{A Bounded Degree SOS Plus SONC Hierarchy for Polynomial Optimization}},
author = {Mareike Dressler and Qi Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25954},
eprint = {2609.25954},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25954},
}
RIS
TY - UNPB
TI - A Bounded Degree SOS Plus SONC Hierarchy for Polynomial Optimization
AU - Mareike Dressler
AU - Qi Wang
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.25954
UR - https://arxiv.org/abs/2609.25954
AB - We propose a bounded degree SOS+SONC hierarchy for constrained polynomial optimization, termed B-SOS+SONC. Starting from Lasserre's bounded-degree SOS framework, we enlarge the certificate cone from SOS to the recently introduced SOS+SONC cone, thereby combining the algebraic strength of semidefinite relaxations with the sparse structure captured by circuit polynomials. We show that, for each fixed certificate degree, the resulting hierarchy is complete, that is, its optimal values are monotone and converge to the global optimum. Moreover, we derive an explicit SDP-REP reformulation, so that each relaxation can be solved within a tractable convex optimization framework over semidefinite and relative entropy cones. Beyond the optimization hierarchy itself, we investigate structural properties of the SONC cone and introduce the notions of first-order and second-order SONC-convexity. This leads to a new sufficient condition for first-level exactness of the B-SOS+SONC hierarchy. Numerical experiments illustrate that the proposed hierarchy often yields tighter lower bounds than the B-SOS relaxation while remaining tractable.
ER -