Newton polytopes and relative entropy optimization
From MaRDI portal
Publication:2067684
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.
Recommendations
- Combinatorial optimization with information geometry: the Newton method
- A Quadratically Convergent Polynomial Algorithm for Solving Entropy Optimization Problems
- Entropy methods in asymptotic convex geometry
- scientific article; zbMATH DE number 5788395
- Relative entropy optimization and its applications
- Entropy optimization models with convex constraints
- Entropy optimization and mathematical programming
- Signomial and polynomial optimization via relative entropy and partial dualization
- scientific article; zbMATH DE number 2248400
Cites work
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- A penalty treatment of equality constraints in generalized geometric programming
- A Positivstellensatz for sums of nonnegative circuit polynomials
- A tutorial on geometric programming
- Amoebas, nonnegative polynomials and sums of squares supported on circuits
- An algorithmic approach to Schmüdgen's Positivstellensatz
- Anneaux preordonnes
- Class of global minimum bounds of polynomial functions
- Coercive Polynomials and Their Newton Polytopes
- CVXPY: a Python-embedded modeling language for convex optimization
- Designing globally optimal delta-sigma modulator topologies via signomial programming
- Extremal psd forms with few terms
- Forms derived from the arithmetic-geometric inequality
- Generalization of primal-dual interior-point methods to convex optimization problems in conic form
- Global injectivity and multiple equilibria in uni- and bi-molecular reaction networks
- Global optimization of nonconvex polynomial programming problems having rational exponents
- Global optimization with polynomials and the problem of moments
- scientific article; zbMATH DE number 5567196 (Why is no real title available?)
- scientific article; zbMATH DE number 3940124 (Why is no real title available?)
- scientific article; zbMATH DE number 49991 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- Inductor design using signomial programming
- Linearization method of global optimization for generalized geometric programming
- Lower bounds for polynomials using geometric programming
- Lower bounds for polynomials with simplex Newton polytopes based on geometric programming
- Lower bounds on the global minimum of a polynomial
- On the bijectivity of families of exponential/generalized polynomial maps
- Optimal design of a membrane separation process using signomial programming
- Optimization and \(\mathrm{NP}_{\mathbb{R}}\)-completeness of certain fewnomials
- Positive polynomials and sums of squares
- Relative entropy relaxations for signomial optimization
- Sign conditions for injectivity of generalized polynomial maps with applications to chemical reaction networks and real algebraic geometry
- Some NP-complete problems in quadratic and nonlinear programming
- Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
- Sparsity in sums of squares of polynomials
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- The Ronkin number of an exponential sum
Cited in
(25)- Sublinear circuits for polyhedral sets
- Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- Sublinear circuits and the constrained signomial nonnegativity problem
- A fast Newton algorithm for entropy maximization in phase determination
- Combinatorial optimization with information geometry: the Newton method
- The algebraic boundary of the sonc-cone
- Nonnegative Polynomials and Circuit Polynomials
- Symmetry reduction in AM/GM-based optimization
- Algebraic Perspectives on Signomial Optimization
- Real algebraic geometry with a view toward Koopman operator methods. Abstracts from the workshop held March 12--17, 2023
- Parameter Region for Multistationarity in \({\boldsymbol{n-}}\)Site Phosphorylation Networks
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- Symmetric SAGE and SONC forms, exactness and quantitative gaps
- Convex hulls of monomial curves, and a sparse positivstellensatz
- Spectrahedral shadows and completely positive maps on real closed fields
- A characterization for tightness of the sparse moment-SOS hierarchy
- The duality of SONC: advances in circuit-based certificates
- Relative entropy methods in constrained polynomial and signomial optimization
- Empirically exploring the space of monostationarity in dual phosphorylation
- Polynomial optimization for nonlinear dynamics: theory, algorithms and applications. Abstracts from the workshop held July 28 -- August 2, 2024
- Initial application of SONC to Lyapunov stability of dynamical systems
- Study of the cone of sums of squares plus sums of nonnegative circuit forms
- Spectral methods for polynomial optimization
- Signomial and polynomial optimization via relative entropy and partial dualization
This page was built for publication: Newton polytopes and relative entropy optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2067684)
