Duality of sum of nonnegative circuit polynomials and optimal SONC bounds. (January 2023)

• Record Type: Journal Article
• Authors: Papp, Dávid
• Is Part Of: Journal of symbolic computation. Volume 114(2023)
• Page Start: 246
• Page End: 266
• Publication Date: 2023-01
• Subjects: 14Q30 -- 90C23 -- 49M29 -- 90C25; Polynomial optimization -- Nonnegativity certificates -- Circuit polynomials -- Convex optimization -- Duality -- Power cone; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.04.015
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: Circuit polynomials are polynomials with properties that make it easy to compute sharp and certifiable global lower bounds for them. Consequently, one may use them to find certifiable lower bounds for any polynomial by writing it as a sum of circuit polynomials with known lower bounds. Recent work has shown that sums of nonnegative circuit polynomials (or SONC polynomials for short) can be used to compute global lower bounds (called SONC bounds) for polynomials in this manner very efficiently both in theory and in practice, if the polynomial is bounded from below and its support satisfies a certain nondegeneracy assumption. The quality of the SONC bound depends on the circuits used in the computation but finding the set of circuits that yield the best attainable SONC bound among the astronomical number of candidate circuits is a non-trivial task that has not been addressed so far. We propose an efficient method to compute the optimal SONC lower bound by iteratively identifying the optimal circuits to use in the SONC bounding process. The method is derived from a new proof of the result that every SONC polynomial decomposes into SONC polynomials on the same support. This proof is based on convex programming duality and motivates a column generation approach that is particularly attractive for sparse polynomials of high degree and with many unknowns. The method is implemented and tested on a large set of sparse polynomial optimization problems with up to 40 unknowns, of degree up to 60, and up to 3000 monomials in the support. The results indicate that the method is efficient in practice and requires only a small number of iterations to identify the optimal circuits.