Signomial and Polynomial Optimization via Relative Entropy and Partial Dualization

Abstract

We describe a generalization of the Sums-of-AM/GM Exponential (SAGE) relaxation methodology for obtaining bounds on constrained signomial and polynomial optimization problems. Our approach leverages the fact that relative entropy based SAGE certificates conveniently and transparently blend with convex duality, in a manner that Sums-of-Squares certificates do not. This more general approach not only retains key properties of ordinary SAGE relaxations (e.g. sparsity preservation), but also inspires a novel perspective-based method of solution recovery. We illustrate the utility of our methodology with a range of examples from the global optimization literature, along with a publicly available software package.

Software at https://rileyjmurray.github.io/sageopt/. Nine tables, one figure. Forty pages (with large margins). Ten pages of computational experiments; print pages 1-25 and 36-40 to skip the computational experiments. Version 2: minor simplification to section 4.2.1

References in corpus (2)

• Newton Polytopes and Relative Entropy Optimization
• An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization

Cited by in corpus (7)

• Performance enhancements for a generic conic interior point algorithm
• Global Optimization via the Dual SONC Cone and Linear Programming
• Revealing hidden physical nonclassicality with nonnegative polynomials
• A Positivstellensatz for Conditional SAGE Signomials
• Real Zeros of SONC Polynomials
• Harmonic Hierarchies for Polynomial Optimization
• Convex scalarizations of the mean-variance-skewness-kurtosis problem in portfolio selection