Newton polytopes and relative entropy optimization

Riley Murray, Venkat Chandasekaran, Adam WiermanFound. Comput. Math 2021 · DOI · OpenReview

TL;DR

This paper introduces a new framework for proving that mathematical functions called "signomials" are always positive. By leveraging geometric properties of "Newton polytopes" and convex optimization techniques, they show that this new method, called SAGE, can efficiently solve a broad class of previously intractable optimization problems and even certify nonnegativity of polynomials without being limited by their degree.

What Problem Does This Paper Address?

Certifying that a function is always non-negative (or positive) is a fundamental problem in mathematics with applications ranging from proving stability of systems to finding optimal solutions in optimization. For general functions, this is incredibly difficult. While there are methods for specific types of functions like polynomials (e.g., Sums of Squares), many real-world problems involve "signomials" – a more general class of functions that are harder to analyze. Existing methods for signomials are often computationally expensive or don't cover all cases. This paper tackles the challenge of efficiently and reliably certifying nonnegativity for signomials, and then extends these insights to polynomials.

Methods

The core of the paper revolves around Sums-of-AM/GM-Exponentials (SAGE) decomposition. The authors build upon prior work by Chandrasekaran and Shah, which showed that if a signomial can be decomposed into a sum of "AGE" (Arithmetic-Geometric Mean Exponential) functions, it's guaranteed to be non-negative. The key innovation here is a deeper theoretical understanding of SAGE certificates. They achieve this by:

  • Convex Duality and Relative Entropy: They use the connection between proving nonnegativity and solving convex optimization problems (specifically, relative entropy programs) to analyze SAGE certificates.
  • Newton Polytopes: They leverage the geometric structure of Newton polytopes, which are convex hulls of the exponent vectors of signomial terms. The shape and properties of these polytopes are crucial for understanding when SAGE certificates are equivalent to true nonnegativity.
  • Structural Properties of SAGE Cones: They uncover new properties of the "SAGE cone" (the set of coefficients that yield SAGE functions), including sparsity preservation and characterizations of its extreme rays. This allows for more efficient computations.
  • Bridging Signomials and Polynomials: A significant contribution is showing how these signomial results can be efficiently applied to certify nonnegativity of polynomials, even those of very high degree, by transforming them into a signomial representation.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • SAGE as a Powerful Certificate: The paper solidifies SAGE decomposition as a powerful and computationally tractable tool for proving function nonnegativity, especially for signomials.
  • Geometry Matters: The structure of Newton polytopes plays a surprisingly critical role in determining when SAGE certificates are sufficient to guarantee nonnegativity. Simplicial Newton polytopes are particularly important.
  • Sparsity Preservation: SAGE decompositions naturally preserve sparsity, meaning the terms in the decomposition are related to the original terms of the function. This is crucial for computational efficiency.
  • Polynomial Nonnegativity Without Degree Limits: The most striking insight is that their SAGE-based approach can certify polynomial nonnegativity with complexity independent of the polynomial's degree, a significant advantage over methods like Sums of Squares.
  • Convex Relaxation Power: The work demonstrates the broad applicability of convex relaxation techniques for solving problems that are otherwise intractable due to non-convexity.

Key Results

  • New Structural Properties of SAGE: The paper provides characterizations of the extreme rays of SAGE cones and proves a sparsity-preserving property for SAGE decompositions.
  • Conditions for Equivalence: They establish new conditions under which signomial nonnegativity is equivalent to the existence of a SAGE decomposition, broadening the class of problems solvable by convex relaxation.
  • Efficient Polynomial Nonnegativity Certification: They develop methods to certify polynomial nonnegativity with complexity independent of the polynomial's degree.
  • Theoretical Foundation for SAGE: The paper provides a rigorous mathematical framework for understanding and applying SAGE certificates, connecting them to convex duality and geometric properties of Newton polytopes.

Limitations and Future Work

  • Tightness of Conditions: The paper includes examples (Examples 23-25) that suggest the conditions derived for SAGE to be equivalent to nonnegativity might be tight, meaning they cannot be significantly relaxed without losing the equivalence.
  • Conjecture on Regularity: They propose a conjecture (Conjecture 27) about when SAGE and nonnegativity cones coincide under certain regularity conditions on the exponent matrix, suggesting further avenues for research.
  • Future Work on Optimization Hierarchies: The paper outlines how SAGE can be used to construct sparsity-preserving hierarchies for constrained polynomial optimization problems, which could lead to improved computational methods.
  • Potential for Broader Applications: The techniques developed could potentially be applied to other areas of computational mathematics where certifying nonnegativity is important.

Summary updated

Abstract

Certifying function nonnegativity is a ubiquitous problem in computational mathematics, with especially notable applications in optimization. We study the question of certifying nonnegativity of signomials based on the recently proposed approach of Sums-of-AM/GM-Exponentials (SAGE) decomposition due to the second author and Shah. The existence of a SAGE decomposition is a sufficient condition for nonnegativity of a signomial, and it can be verified by solving a tractable convex relative entropy program. We present new structural properties of SAGE certificates such as a characterization of the extreme rays of the cones associated to these decompositions as well as an appealing form of sparsity preservation. These lead to a number of important consequences such as conditions under which signomial nonnegativity is equivalent to the existence of a SAGE decomposition; our results represent the broadest-known class of nonconvex signomial optimization problems that can be solved efficiently via convex relaxation. The analysis in this paper proceeds by leveraging the interaction between the convex duality underlying SAGE certificates and the face structure of Newton polytopes. After proving our main signomial results, we direct our machinery toward the topic of globally nonnegative polynomials. This leads to (among other things) efficient methods for certifying polynomial nonnegativity, with complexity independent of the degree of a polynomial.
BibTeX
@article{murray2021newton,
  author = {Riley Murray and Venkat Chandasekaran and Adam Wierman},
  title = {{Newton polytopes and relative entropy optimization}},
  journal = {Found. Comput. Math.},
  year = {2021},
  doi = {10.1007/s10208-021-09497-w},
}
Figure