Global Optimization via the Dual SONC Cone and Linear Programming

Abstract

Using the dual cone of sums of nonnegative circuits (SONC), we provide a relaxation of the global optimization problem to minimize an exponential sum and, as a special case, a multivariate real polynomial. Our approach builds on two key observations. First, that the dual SONC cone is contained in the primal one. Hence, containment in this cone is a certificate of nonnegativity. Second, we show that membership in the dual cone can be verified by a linear program. We implement the algorithm and present initial experimental results comparing our method to existing approaches.

arXiv commentfinal version; 17 pages, 5 tables

References in corpus (6)

• CVXPY: A Python-Embedded Modeling Language for Convex Optimization
• Newton Polytopes and Relative Entropy Optimization
• Signomial and Polynomial Optimization via Relative Entropy and Partial Dualization
• An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization
• Nonnegative Polynomials and Circuit Polynomials
• The algebraic boundary of the sonc cone

Cited by in corpus (4)

• Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization
• Real Zeros of SONC Polynomials
• Sparse non-SOS Putinar-type Positivstellensätze
• Convexification of box-constrained polynomial optimization problems via monomial patterns