An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization

Abstract

Finding the minimum of a multivariate real polynomial is a well-known hard problem with various applications. We present a polynomial time algorithm to approximate such lower bounds via sums of nonnegative circuit polynomials (SONC). As a main result, we carry out the first large-scale comparison of SONC, using this algorithm and different geometric programming (GP) solvers, with the classical sums of squares (SOS) approach, using several of the most common semidefinite programming (SDP) solvers. SONC yields bounds competitive to SOS in several cases, but using significantly less time and memory. In particular, SONC/GP can handle much larger problem instances than SOS/SDP.

arXiv comment25 pages, 3 figures, 8 tables

Cited by in corpus (8)

• Newton Polytopes and Relative Entropy Optimization
• Signomial and Polynomial Optimization via Relative Entropy and Partial Dualization
• Global Optimization via the Dual SONC Cone and Linear Programming
• On Supports of Sums of Nonnegative Circuit Polynomials
• A second order cone characterization for sums of nonnegative circuits
• Exact Optimization via Sums of Nonnegative Circuits and Sums of AM/GM Exponentials
• Improved Lower Bounds for Global Polynomial Optimisation
• Convexification of box-constrained polynomial optimization problems via monomial patterns