Relative entropy relaxations for signomial optimization
From MaRDI portal
Publication:2805708
Abstract: Signomial programs (SPs) are optimization problems specified in terms of signomials, which are weighted sums of exponentials composed with linear functionals of a decision variable. SPs are non-convex optimization problems in general, and families of NP-hard problems can be reduced to SPs. In this paper we describe a hierarchy of convex relaxations to obtain successively tighter lower bounds of the optimal value of SPs. This sequence of lower bounds is computed by solving increasingly larger-sized relative entropy optimization problems, which are convex programs specified in terms of linear and relative entropy functions. Our approach relies crucially on the observation that the relative entropy function -- by virtue of its joint convexity with respect to both arguments -- provides a convex parametrization of certain sets of globally nonnegative signomials with efficiently computable nonnegativity certificates via the arithmetic-geometric-mean inequality. By appealing to representation theorems from real algebraic geometry, we show that our sequences of lower bounds converge to the global optima for broad classes of SPs. Finally, we also demonstrate the effectiveness of our methods via numerical experiments.
Recommendations
- Signomial and polynomial optimization via relative entropy and partial dualization
- Relative entropy optimization and its applications
- Entropy inequalities for a relaxation scheme
- Entropy optimization models with convex constraints
- Entropy-Like Proximal Methods in Convex Programming
- Relative entropy minimization over Hilbert spaces via Robbins-Monro
- A correspondence principle for relative entropy minimization
- scientific article; zbMATH DE number 6276166
Cites work
- scientific article; zbMATH DE number 527343 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 3272827 (Why is no real title available?)
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- A tutorial on geometric programming
- Anneaux preordonnes
- Class of global minimum bounds of polynomial functions
- Convex Analysis
- Digital Circuit Optimization via Geometric Programming
- Elements of Information Theory
- Extremal positive semidefinite forms
- Forms derived from the arithmetic-geometric inequality
- Geometric Programming
- Geometric Programming Duals of Channel Capacity and Rate Distortion
- Geometric Programming for Communication Systems
- Geometric programming with signomials
- Global optimization of nonconvex polynomial programming problems having rational exponents
- Global optimization with polynomials and the problem of moments
- Linearization method of global optimization for generalized geometric programming
- Lower bounds for polynomials using geometric programming
- On an extension of Pólya's Positivstellensatz
- Positive polynomials and sums of squares
- Second-order method of generalized geometric programming for spatial frame optimization
- Semidefinite programming relaxations for semialgebraic problems
- The \(K\)-moment problem for compact semi-algebraic sets
- There are significantly more nonnegative polynomials than sums of squares
- Uniform denominators in Hilbert's seventeenth problem
Cited in
(36)- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
- On the heavy-tail behavior of the distributionally robust newsvendor
- A convex programming approach to solve posynomial systems
- Lifting for simplicity: concise descriptions of convex sets
- A Positivstellensatz for sums of nonnegative circuit polynomials
- Primal-dual interior-point methods for domain-driven formulations
- Lieb's concavity theorem, matrix geometric means, and semidefinite optimization
- The dual cone of sums of non-negative circuit polynomials
- CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
- Sublinear circuits and the constrained signomial nonnegativity problem
- Initial steps in the classification of maximal mediated sets
- Signomial and polynomial optimization via relative entropy and partial dualization
- Parameter Region for Multistationarity in \({\boldsymbol{n-}}\)Site Phosphorylation Networks
- Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
- Functional norms, condition numbers and numerical algorithms in algebraic geometry
- A hierarchy of spectral relaxations for polynomial optimization
- Robust budget allocation via continuous submodular functions
- The \(\mathcal{S}\)-cone and a primal-dual view on second-order representability
- Spectral inequalities for nonnegative tensors and their tropical analogues
- A unified framework of SAGE and SONC polynomials and its duality theory
- Symmetric SAGE and SONC forms, exactness and quantitative gaps
- Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
- Real tropicalization and negative faces of the Newton polytope
- Algebraic Perspectives on Signomial Optimization
- The algebraic boundary of the sonc-cone
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- Limitations on the Expressive Power of Convex Cones without Long Chains of Faces
- Relative entropy optimization and its applications
- Newton polytopes and relative entropy optimization
- Performance enhancements for a generic conic interior point algorithm
- Symmetry reduction in AM/GM-based optimization
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- Real zeros of SONC polynomials
- Sublinear circuits for polyhedral sets
This page was built for publication: Relative entropy relaxations for signomial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2805708)
