Sublinear circuits and the constrained signomial nonnegativity problem
Riley Murray, Helen Naumann, Thorsten Theobald · Mathematical Programming · 2022
Abstract Conditional Sums-of-AM/GM-Exponentials (conditional SAGE) is a decomposition method to prove nonnegativity of a signomial or polynomial over some subset X of real space. In this article, we undertake the first structural analysis of conditional SAGE signomials for convex sets X . We introduce the X -circuits of a finite subset $${\mathcal {A}}\subset {\mathbb {R}}^n$$ A ⊂ R n , which generalize the simplicial circuits of the affine-linear matroid induced by $${\mathcal {A}}$$ A to a constrained setting. The X -circuits serve as the main tool in our analysis and exhibit particularly rich combinatorial properties for polyhedral X , in which case the set of X -circuits is comprised of one-dimensional cones of suitable polyhedral fans. The framework of X -circuits transparently reveals when an X -nonnegative conditional AM/GM-exponential can in fact be further decomposed as a sum of simpler X -nonnegative signomials. We develop a duality theory for X -circuits with connections to geometry of sets that are convex according to the geometric mean. This theory provides an optimal power cone reconstruction of conditional SAGE signomials when X is polyhedral. In conjunction with a notion of reduced X -circuits, the duality theory facilitates a characterization of the extreme rays of conditional SAGE cones. Since signomials under logarithmic variable substitutions give polynomials, our results also have implications for nonnegative polynomials and polynomial optimization.