Relative entropy relaxations for signomial optimization
From MaRDI portal
Publication:2805708
DOI10.1137/140988978zbMATH Open1345.90066arXiv1409.7640OpenAlexW2239251014MaRDI QIDQ2805708FDOQ2805708
Authors: Venkat Chandrasekaran, Parikshit Shah 
Publication date: 13 May 2016
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1409.7640
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
convex optimizationglobal optimizationreal algebraic geometrygeometric programmingarithmetic-geometric-mean inequality
Cites Work
- Title not available (Why is that?)
- Elements of Information Theory
- Convex Analysis
- Global optimization with polynomials and the problem of moments
- The \(K\)-moment problem for compact semi-algebraic sets
- Semidefinite programming relaxations for semialgebraic problems
- Uniform denominators in Hilbert's seventeenth problem
- On an extension of Pólya's Positivstellensatz
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- Class of global minimum bounds of polynomial functions
- Title not available (Why is that?)
- Forms derived from the arithmetic-geometric inequality
- Extremal positive semidefinite forms
- Lower bounds for polynomials using geometric programming
- A tutorial on geometric programming
- Geometric programming with signomials
- Geometric Programming Duals of Channel Capacity and Rate Distortion
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- Anneaux preordonnes
- Positive polynomials and sums of squares
- Linearization method of global optimization for generalized geometric programming
- Geometric Programming for Communication Systems
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- Global optimization of nonconvex polynomial programming problems having rational exponents
- Digital Circuit Optimization via Geometric Programming
- There are significantly more nonnegative polynomials than sums of squares
- Title not available (Why is that?)
- Geometric Programming
- Second-order method of generalized geometric programming for spatial frame optimization
Cited In (36)
- Primal-Dual Interior-Point Methods for Domain-Driven Formulations
- Initial steps in the classification of maximal mediated sets
- Signomial and polynomial optimization via relative entropy and partial dualization
- Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
- Real zeros of SONC polynomials
- Limitations on the Expressive Power of Convex Cones without Long Chains of Faces
- On the Heavy-Tail Behavior of the Distributionally Robust Newsvendor
- Sublinear circuits for polyhedral sets
- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
- 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
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- Algebraic Perspectives on Signomial Optimization
- Performance enhancements for a generic conic interior point algorithm
- Symmetric SAGE and SONC forms, exactness and quantitative gaps
- The dual cone of sums of non-negative circuit polynomials
- Parameter Region for Multistationarity in \({\boldsymbol{n-}}\)Site Phosphorylation Networks
- Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
- A hierarchy of spectral relaxations for polynomial optimization
- Real tropicalization and negative faces of the Newton polytope
- Lieb's concavity theorem, matrix geometric means, and semidefinite optimization
- A Convex Programming Approach to Solve Posynomial Systems
- Lifting for Simplicity: Concise Descriptions of Convex Sets
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- Newton polytopes and relative entropy optimization
- The Algebraic Boundary of the Sonc-Cone
- A Positivstellensatz for Sums of Nonnegative Circuit Polynomials
- Sublinear circuits and the constrained signomial nonnegativity problem
- Functional norms, condition numbers and numerical algorithms in algebraic geometry
- Relative entropy optimization and its applications
- Symmetry Reduction in AM/GM-Based Optimization
- A unified framework of SAGE and SONC polynomials and its duality theory
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
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)
