A Caltech Library Service

Newton Polytopes and Relative Entropy Optimization

Murray, Riley and Chandrasekaran, Venkat and Wierman, Adam (2021) Newton Polytopes and Relative Entropy Optimization. Foundations of Computational Mathematics . ISSN 1615-3375. (In Press)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© SFoCM 2021. Received 08 October 2018; Revised 12 May 2020; Accepted 20 December 2020; Published 05 March 2021. The authors are thankful for the detailed suggestions of anonymous referees, which have led to a much-improved revision of our original manuscript. V.C. would like to acknowledge helpful conversations with Parikshit Shah, particularly on the connections between SAGE and SDSOS polynomials. R.M. was supported in part by NSF grant CCF-1637598 and by an NSF Graduate Research Fellowship. V.C. was supported in part by NSF grants CCF-1350590 and CCF-1637598, AFOSR grant FA9550-16-1-0210, and a Sloan Research Fellowship. A.W. was supported in part by NSF grant CCF-1637598.
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0210
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:Arithmetic-geometric-mean inequality; Certifying nonnegativity; Fewnomials; SAGE; Signomials; Sparse polynomials
Classification Code:Mathematics Subject Classification: 52A40; 90C30; 14P15
Record Number:CaltechAUTHORS:20190627-102049940
Persistent URL:
Official Citation:Murray, R., Chandrasekaran, V. & Wierman, A. Newton Polytopes and Relative Entropy Optimization. Found Comput Math (2021).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96779
Deposited By: Tony Diaz
Deposited On:27 Jun 2019 18:49
Last Modified:10 Mar 2021 18:49

Repository Staff Only: item control page