Sublinear Circuits and the Constrained Signomial Nonnegativity Problem

Riley Murray, Helen Naumann, Thorsten Theobald

TL;DR

This paper introduces "X-circuits," a novel geometric tool to analyze the nonnegativity of signomials (a type of function) over constrained sets. This framework leads to a deeper understanding of "conditional SAGE" methods, offering a more structured and potentially simpler way to certify nonnegativity, with implications for polynomial optimization.

What Problem Does This Paper Address?

Signomials are a broad class of functions with applications in fields like chemical reaction networks and aircraft design. A key question is when these functions are guaranteed to be non-negative over a specific domain (a "constrained set" denoted by X). While methods like "conditional Sums-of-AM/GM-Exponentials" (conditional SAGE) exist to tackle this, their structural properties, especially for constrained domains, were not fully understood. This paper aims to provide a deeper structural analysis of these methods, particularly focusing on how signomials can be decomposed into simpler non-negative components when the domain is constrained. This is crucial for developing more efficient and robust optimization and certification techniques.

Methods

The core contribution is the introduction of X-circuits. These are geometric objects that generalize "simplicial circuits" (used in unconstrained settings) to constrained domains. X-circuits are defined based on a "strict sublinearity condition" of a function related to the domain X and the signomial's exponents. This new concept serves as the primary tool for the structural analysis.

The paper then uses X-circuits to:

  • Generalize existing theory: Extend concepts from unconstrained SAGE and SONC (Sums of Nonnegative Circuit polynomials) to the constrained setting.
  • Develop duality theory: Establish connections between X-circuits and geometric properties of the domain X, leading to an "optimal power cone reconstruction" of signomials.
  • Characterize cones: Define and analyze "X-AGE cones" (signomials with specific nonnegativity certificates) and "X-SAGE cones" (sums of X-AGE cones), ultimately characterizing their extreme rays.
  • Leverage convex analysis: Employ tools like support functions, convex hulls, and conic duality to prove key theorems about the structure of these cones.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • X-circuits as a unifying concept: The introduction of X-circuits provides a powerful geometric lens to understand signomial nonnegativity in constrained settings, unifying concepts from discrete geometry, convex analysis, and function theory.
  • Structure beyond support: The paper highlights that understanding signomial nonnegativity requires more than just looking at the exponents (support) of the signomial; the geometry of the domain X plays a crucial role.
  • Reduced X-circuits: The concept of "reduced" X-circuits is introduced, suggesting that not all X-circuits are equally essential for reconstructing the entire SAGE cone, leading to more efficient representations.
  • Log-convexity connection: The dual of the X-SAGE cone exhibits a property of being "convex under a logarithmic transformation," which has significant implications for understanding the structure of these cones.

Key Results

  • Characterization of X-circuits: The paper provides a precise definition and characterization of X-circuits, particularly for polyhedral domains, where they are linked to the normal fans of the domain.
  • Decomposition of X-SAGE cones: It's shown that X-SAGE cones can be decomposed into sums of "λ-witnessed AGE cones," where λ is a normalized X-circuit. This provides a constructive way to understand these cones.
  • Power cone representability: For polyhedral domains X, the X-SAGE cones are shown to be "power cone representable," a significant result for computational optimization.
  • Complete characterization for univariate case: For the specific case of X being a half-line [0, ∞) and a univariate set of exponents, the paper completely characterizes the extreme rays of the corresponding X-SAGE cone.

Limitations and Future Work

  • Computational complexity: While the paper provides theoretical insights, finding X-circuits can be computationally challenging, especially for high-dimensional problems. The authors mention that Fourier-Motzkin elimination can be used, but it's computationally intensive.
  • Generalization to nonconvex constraints: The current framework primarily focuses on convex constraint sets X. The authors note that extending this to nonconvex constraints would require additional algebraic techniques.
  • Matroid theory connection: Further exploration of the connection between X-circuits and matroid theory, particularly for polyhedral X, is suggested.
  • Exploration of multiplicatively-convex sets: The paper points to the interest in studying sets where the logarithm of the set is convex, which relates to the properties of the dual X-SAGE cones.

Summary updated

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$, which generalize the simplicial circuits of the affine-linear matroid induced by $\mathcal{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.
BibTeX
@article{murray2020sublinear,
  author = {Riley Murray and Helen Naumann and Thorsten Theobald},
  title = {{Sublinear Circuits and the Constrained Signomial Nonnegativity Problem}},
  journal = {Math. Program},
  year = {2020},
}
Figure