Open Collections

Optimization over the Hypercube via Sums of Nonnegative Circuit Polynomials

Banff International Research Station for Mathematical Innovation and Discovery

Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube H. One particularly successful way to prove complexity bounds for these types of problems are based on sums of squares (SOS) as nonnegativity certificates. We initiate optimization over H via a recent, alternative certificate called sums of nonnegative circuit polynomials (SONC). We show that key results for SOS based certificates remain valid: First, for polynomials, which are nonnegative over the n-variate boolean hypercube H with constraints of degree at most d there exists a SONC certificate of degree at most n+d. Second, if there exists a degree d SONC certificate for nonnegativity of a polynomial over H, then there also exists a short degree d SONC certificate, that includes at most n^O(d) nonnegative circuit polynomials. Joint work with Timo de Wolff and Adam Kurpisz.

Mathematics; Operations research, mathematical programming; Algebraic geometry; Control/Optimization/Operation Research

video/mp4

Author affiliation: UC San Diego

2020-09-11

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/75979

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/