Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials

Mareike Dressler, Adam Kurpisz, Timo de Wolff

TL;DR

This paper introduces "sums of nonnegative circuit polynomials" (SONC) as a new tool for tackling optimization problems over the boolean hypercube, offering an alternative to the established "sums of squares" (SOS) method. The authors demonstrate that SONC certificates can provide analogous complexity bounds to SOS, particularly for hypercube optimization, and show that SONC certificates can be made "short" (using few terms) without sacrificing their degree.

What Problem Does This Paper Address?

Many problems in theoretical computer science can be framed as polynomial optimization problems over the boolean hypercube. A common technique for analyzing these problems and proving complexity bounds is the use of "sums of squares" (SOS) as a nonnegativity certificate. However, SOS methods have known weaknesses: they can require very high degrees for certain problems, and finding SOS certificates can be computationally expensive due to potentially large coefficients. This paper explores a newer nonnegativity certificate, "sums of nonnegative circuit polynomials" (SONC), to see if it can overcome some of these limitations for hypercube optimization problems.

Methods

The core of the paper is the analysis of SONC certificates for polynomials that are nonnegative over the boolean hypercube. The authors establish two main results:

  1. Degree Bounds: They show that for any polynomial nonnegative over an n-variate hypercube with constraints of degree d, there exists a SONC certificate of degree at most n + d. This is analogous to known results for SOS.
  2. Short Certificates: They prove that if a polynomial has a degree d SONC certificate, it also has a "short" degree d SONC certificate, meaning it can be represented using a number of terms that grows sub-polynomially with d (specifically, no(d)). This addresses a key bottleneck in SOS, where certificates can have exponentially large bit complexity.

The paper also investigates structural properties of SONCs, showing they are not closed under multiplication or affine transformations, which distinguishes them from SOS. They also demonstrate that SONCs do not admit a direct equivalent of Putinar's Positivstellensatz, a powerful result for SOS.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • SONC as a Viable Alternative: The paper strongly suggests that SONCs are a promising alternative to SOS for hypercube optimization, offering comparable theoretical guarantees.
  • "Shortness" is Achievable for SONCs: A crucial finding is that SONC certificates can be made "short" (using a sub-polynomial number of terms) without increasing their degree. This is a significant advantage over SOS, where short certificates are not always guaranteed.
  • SONC's Unique Structure: The SONC cone has different closure properties than the SOS cone (e.g., not closed under multiplication), leading to distinct theoretical behaviors and potential algorithmic implications.
  • No Direct Putinar Equivalent: The paper shows that a direct generalization of Putinar's Positivstellensatz from SOS to SONCs is not possible, highlighting fundamental differences between the two certificate types.

Key Results

  • Degree Bound: For a polynomial nonnegative over an n-variate hypercube with constraints of degree d, a SONC certificate of degree at most n + d exists.
  • Short Certificate Guarantee: If a polynomial has a degree d SONC certificate, then a SONC certificate of degree d with at most no(d) terms exists.
  • SONC Cone Properties: The SONC cone is not closed under multiplication or affine transformations of variables.
  • Putinar's Positivstellensatz: An example is provided showing that a direct equivalent of Putinar's Positivstellensatz for SONCs does not exist.

Limitations and Future Work

  • Algorithmic Efficiency: While the paper establishes theoretical bounds and the existence of short SONC certificates, it explicitly notes that translating these results into efficient algorithms remains an open problem. The difficulty lies in efficiently searching the space of SONC certificates.
  • SONC vs. SOS Complexity: The paper hints that SONCs might offer advantages in certain scenarios where SOS struggles, but a comprehensive comparison of their practical algorithmic performance is left for future work.
  • Generalization of Putinar's Result: The negative result regarding Putinar's Positivstellensatz opens avenues for exploring what can be achieved with SONCs in terms of Positivstellensatz-like theorems for specific classes of sets.

Summary updated

BibTeX
@article{dressler2022optimization,
  author = {Mareike Dressler and Adam Kurpisz and Timo de Wolff},
  title = {{Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials}},
  journal = {Found. Comput. Math},
  year = {2022},
  doi = {10.1007/s10208-021-09496-x},
}
Figure