51. Global Optimization via the Dual SONC Cone and Linear Programming
- Author
-
Dressler, Mareike, Heuer, Janin, Naumann, Helen, and de Wolff, Timo
- Subjects
Mathematics - Optimization and Control ,Mathematics - Algebraic Geometry ,12D15, 13J30, 14P05, 90C05, 90C26 - 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., Comment: final version; 17 pages, 5 tables more...
- Published
- 2020
- Full Text
- View/download PDF