Search Results

Documents authored by de Wolff, Timo

Document
DOI: 10.4230/LIPIcs.MFCS.2018.82
Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials

Authors: Mareike Dressler, Adam Kurpisz, and Timo de Wolff

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

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 are based on sums of squares (SOS) as nonnegativity certificates. In this article, we initiate optimization 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, there exists a SONC certificate of degree at most n+d for polynomials which are nonnegative over the n-variate boolean hypercube with constraints of degree 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 n^O(d) nonnegative circuit polynomials. Finally, we show certain differences between SOS and SONC cones: we prove that, in contrast 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 Positivestellensatz. We discuss these results both from algebraic and optimization perspective.
Cite as

Mareike Dressler, Adam Kurpisz, and Timo de Wolff. Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 82:1-82:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dressler_et_al:LIPIcs.MFCS.2018.82,
  author =	{Dressler, Mareike and Kurpisz, Adam and de Wolff, Timo},
  title =	{{Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{82:1--82:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.82},
  URN =		{urn:nbn:de:0030-drops-96643},
  doi =		{10.4230/LIPIcs.MFCS.2018.82},
  annote =	{Keywords: nonnegativity certificate, hypercube optimization, sums of nonnegative circuit polynomials, relative entropy programming, sums of squares}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact