Optimization Over the Boolean Hypercube Via Sums of Nonnegative Circuit Polynomials
OPEN ACCESS
Loading...
Author / Producer
Date
2022-04
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube. One particularly successful way to prove complexity bounds for these types of problems is based on sums of squares (SOS) as nonnegativity certificates. In this article, we initiate optimization problems over the boolean hypercube 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 with constraints of degree 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 the boolean hypercube, then there also exists a short degree d SONC certificate that includes at most nO(d) nonnegative circuit polynomials. Moreover, we prove that, in opposite to SOS, the SONC cone is not closed under taking affine transformation of variables and that for SONC there does not exist an equivalent to Putinar’s Positivstellensatz for SOS. We discuss these results from both the algebraic and the optimization perspective.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
22 (2)
Pages / Article No.
365 - 387
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Certificate; Hypercube optimization; Nonnegativity; Sum of nonnegative circuit polynomials; Sum of squares
Organisational unit
09487 - Zenklusen, Rico / Zenklusen, Rico
Notes
Funding
174117 - Theory and Applications of Linear and Semidefinite Relaxations for Combinatorial Optimization Problems (SNF)