The X-circuits Behind Conditional SAGE Certificates

Riley Murray, Helen Naumann, Thorsten Theobald

Abstract

Conditional SAGE certificates are a decomposition method to prove nonnegativity of a signomial or polynomial over some subset $X$ of Euclidean real space. In the case when $X$ is convex, membership in the signomial can be completely characterized by a relative entropy program involving the support function of $X$. Following promising computational experiments, and a recently proven completeness result for a hierarchy of $X$-SAGE relaxations for signomial optimization, we undertake a structural analysis of signomial $X$-SAGE cones. Our approach begins by determining a suitable notion of an $X$-circuit, in such a way as to generalize classical affine-linear simplicial circuits from matroid theory. Our definition of an $X$-circuit is purely convex-geometric, with no reference to signomials or SAGE certificates. We proceed by using $X$-circuits to characterize the more elementary $X$-AGE which comprise a given $X$-SAGE cone. Our deepest results are driven by a duality theory for $X$-circuits, which is applicable to primal and dual $X$-SAGE cones in their usual forms, as well as to a certain logarithmic transform of the dual cone. In conjunction with a notion of reduced $X$-circuits this facilitates to characterize the extreme rays of the $X$-SAGE cones. Our results require no regularity conditions on $X$ beyond those which ensure a given $X$-SAGE cone is proper; particularly strong conclusions are obtained when $X$ is a polyhedron.

Introduction

In mathematical optimization, proving that a function remains non-negative over a specific domain $X$ is a fundamental challenge with applications ranging from chemical reaction networks to aircraft design. While Sums-of-Squares (SOS) programming has historically been the primary tool for such proofs, it often falters when dealing with sparse functions or signomials—functions of the form $f(x) = \sum c_i e^{\alpha_i \cdot x}$.

The SAGE (Sums-of-AM/GM-Exponentials) framework emerged as a powerful alternative, leveraging the Arithmetic-Geometric Mean inequality to certify non-negativity. However, "Conditional SAGE"—which addresses non-negativity over a constrained convex set $X$—has largely functioned as a computational "black box." This research provides the first comprehensive structural analysis of $X$-SAGE cones, introducing the $X$-circuit as the fundamental geometric building block that bridges the gap between abstract matroid theory and practical convex optimization.

The Geometry of $X$-Circuits

The primary contribution of this work is the generalization of "simplicial circuits" from matroid theory to the constrained setting. In global SAGE optimization, circuits represent the minimal sets of points capturing the dependencies between a function's terms. The $X$-circuit extends this by incorporating the geometry of the constraint set $X$ via its support function $h_X(v) = \sup_{x \in X} v \cdot x$.

An $X$-circuit is defined purely through convex geometry, independent of the specific signomials being tested. This abstraction allows the authors to show that $X$-circuits are the natural evolution of classical circuits; when $X$ is the entire space $\mathbb{R}^n$, the definition collapses back to the standard affine-linear simplicial circuit. Essentially, an $X$-circuit is a vector where the support function exhibits "strict sublinearity."

Duality and Multiplicative Convexity

A significant portion of the paper is dedicated to the duality theory of $X$-SAGE cones. The authors demonstrate that the dual of an $X$-SAGE cone possesses a property known as multiplicative convexity (or log-convexity). Specifically, if one takes the logarithm of the dual set, the resulting set is convex in the traditional sense.

This insight allows for a mapping between separating hyperplanes in a "circuit-generated" space and the original function space. By analyzing the dual cone through this lens, the authors characterize the extreme rays of $X$-SAGE cones using "reduced $X$-circuits"—the specific geometric structures that act as the "load-bearing pillars" of the cone.

Finiteness and Power-Cone Representability

For practitioners, the most impactful results concern the case where $X$ is a polyhedron (a set defined by linear inequalities). The paper establishes several key theorems for polyhedral $X$:

  1. Theorem 3.7: The set of normalized $X$-circuits is finite and corresponds to the one-dimensional cones of a polyhedral fan. This transforms an uncountably infinite problem into a combinatorial one.
  2. Theorem 4.4: Every $X$-SAGE function can be decomposed into a sum of simpler $X$-AGE functions, each "witnessed" by a specific $X$-circuit.
  3. Corollary 4.5: $X$-SAGE cones for polyhedral $X$ are power-cone representable.

This last result is a major win for practitioners. While general $X$-SAGE membership is checked via relative entropy programming, power-cone programming is often more numerically stable and mature in modern solvers. This theoretical result guarantees that constrained non-negativity problems over polyhedra can be solved using efficient, standardized methods.

Illustrative Examples

The authors validate their theoretical framework using illustrative "running examples":

  • The Half-Line ($X = [0, \infty)$): Used to provide a complete characterization of extreme rays in the univariate case (Proposition 6.1), offering explicit formulas for the coefficients.
  • Polyhedral Fans: Used to demonstrate how $X$-circuits relate to the geometry of normal fans in polyhedral theory, showing that $X$-circuits are comprised of one-dimensional cones of a polyhedral fan.

Conclusion and Future Directions

By uncovering the "skeleton" of Conditional SAGE certificates, this work transforms our understanding of constrained non-negativity. The introduction of $X$-circuits provides a combinatorial way to view what was previously an uncountably infinite problem.

While the number of $X$-circuits can grow exponentially with the number of terms, the move toward power-cone representability offers a clear path for improving numerical solvers like sageopt. Future research may extend these concepts to non-convex sets or further explore the properties of multiplicatively-convex sets in broader optimization contexts.

Summary updated

Abstract

Conditional SAGE certificates are a decomposition method to prove nonnegativity of a signomial or polynomial over some subset X of Euclidean real space. In the case when X is convex, membership in the signomial can be completely characterized by a relative entropy program involving the support function of X. Following promising computational experiments, and a recently proven completeness result for a hierarchy of X-SAGE relaxations for signomial optimization, we undertake a structural analysis of signomial X-SAGE cones. Our approach begins by determining a suitable notion of an X-circuit, in such a way as to generalize classical affine-linear simplicial circuits from matroid theory. Our definition of an X-circuit is purely convex-geometric, with no reference to signomials or SAGE certificates. We proceed by using X-circuits to characterize the more elementary X-AGE which comprise a given X-SAGE cone. Our deepest results are driven by a duality theory for X-circuits, which is applicable to primal and dual X-SAGE cones in their usual forms, as well as to a certain logarithmic transform of the dual cone. In conjunction with a notion of reduced X-circuits this facilitates to characterize the extreme rays of the X-SAGE cones. Our results require no regularity conditions on X beyond those which ensure a given X-SAGE cone is proper; particularly strong conclusions are obtained when X is a polyhedron.
BibTeX
@article{murray2020x,
  author = {Riley Murray and Helen Naumann and Thorsten Theobald},
  title = {{The X-circuits Behind Conditional SAGE Certificates}},
  journal = {Math. Program},
  year = {2020},
}

Loading related content...

Figure