Newton Polytopes and Relative Entropy Optimization

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. While our primary focus is on signomials, we also discuss how our results provide efficient methods for certifying polynomial nonnegativity, with complexity independent of the degree of a polynomial.

Body shortened from 29 to 24 pages. Additional consideration to related work. Some claims made in Section 5 have been formalized. Revised within 2 months of first-round reviews

References in corpus (3)

• An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization
• On "A Homogeneous Interior-Point Algorithm for Non-Symmetric Convex Conic Optimization"
• On Supports of Sums of Nonnegative Circuit Polynomials

Cited by in corpus (11)

• Signomial and Polynomial Optimization via Relative Entropy and Partial Dualization
• Global Optimization via the Dual SONC Cone and Linear Programming
• Revealing hidden physical nonclassicality with nonnegative polynomials
• Real Zeros of SONC Polynomials
• Spectrahedral Shadows and Completely Positive Maps on Real Closed Fields
• A second order cone characterization for sums of nonnegative circuits
• Optimisation of time-ordered processes in the finite and asymptotic regime
• Exact Optimization via Sums of Nonnegative Circuits and Sums of AM/GM Exponentials
• Sparse non-SOS Putinar-type Positivstellensätze
• Improved Lower Bounds for Global Polynomial Optimisation
• On Newton-polytope-type sufficiency conditions for coercivity of polynomials