Optimization Over the Boolean Hypercube Via Sums of Nonnegative Circuit Polynomials

Mareike Dressler, Adam Kurpisz, Timo de Wolff

Introduction

Optimization over the boolean hypercube $\{0, 1\}^n$ is a fundamental challenge in theoretical computer science, underpinning landmark NP-hard problems such as Max-Cut and the Independent Set problem. To address these, researchers typically employ hierarchies of convex relaxations. For decades, the Sums of Squares (SOS) hierarchy has been the standard approach, certifying nonnegativity by decomposing polynomials into squared components. However, SOS faces significant hurdles, including high-degree requirements for certain problems (e.g., the Knapsack Problem) and the substantial numerical complexity of Semidefinite Programming (SDP) solvers.

This research investigates Sums of Nonnegative Circuit Polynomials (SONC) as a robust alternative to SOS for hypercube optimization. The authors demonstrate that SONC achieves theoretical parity with SOS in key benchmarks while offering distinct algebraic properties that may overcome traditional SOS limitations.

Methodology: The SONC Framework

Unlike the SOS approach, which is rooted in the principle that squares are inherently nonnegative, the SONC framework leverages the Arithmetic-Geometric Mean (AM-GM) inequality.

A "circuit polynomial" is a sparse polynomial whose nonnegativity is efficiently verifiable via a "circuit number." A SONC is a sum of these fundamental units. By utilizing tools from algebraic geometry—specifically Gröbner bases and Newton polytopes—the authors prove that any polynomial nonnegative on the boolean hypercube can be represented as a SONC. Furthermore, they apply Carathéodory’s Theorem to establish the existence of sparse certificates, which is critical for computational efficiency.

Key Theoretical Insights

The paper reveals several critical properties of the SONC cone in the context of the hypercube:

  • Theoretical Parity with SOS: The authors establish that for a polynomial of degree $d$ nonnegative over a hypercube, a SONC certificate of degree at most $n+d$ always exists. This mirrors the completeness results known for SOS.
  • Lack of Affine Invariance: A significant finding is that the SONC cone is not invariant under affine transformations. Unlike SOS, where a coordinate shift or scaling preserves the certificate's structure, SONC certificates can become significantly more complex under such changes. This "brittleness" highlights a fundamental structural difference between the two methods.
  • Sparsity and "Short" Certificates: The research proves that if a degree $d$ SONC certificate exists, there is a version containing at most $n^{O(d)}$ terms. This suggests SONC is particularly well-suited for high-dimensional problems with local or low-degree interactions.
  • Absence of a Putinar-type Shortcut: In SOS theory, Putinar’s Positivstellensatz provides simplified representations under specific conditions. The authors demonstrate that a direct SONC equivalent does not exist, further distinguishing the two algebraic frameworks.

Results and Computational Complexity

The study provides concrete bounds on the existence and complexity of SONC certificates:

  1. Existence Bound: Every $n$-variate polynomial nonnegative on the boolean hypercube has a SONC certificate of degree at most $n$.
  2. Complexity Bound: Identifying a degree $d$ SONC certificate can be reduced to a Relative Entropy Program (REP). While REPs are convex and generally efficient, the existence of certificates with only $n^{O(d)}$ circuit polynomials provides a theoretical upper bound on proof size.
  3. Structural Boundaries: Through explicit constructions, the authors map the boundaries of SONC, identifying polynomials that are nonnegative but fail to meet simplified SONC criteria.

Conclusion and Future Directions

While the authors prove the existence of short SONC certificates, the algorithmic challenge of efficiently locating them within the vast space of circuit polynomials remains. Future research is directed toward:

  • Developing algorithms to identify "SONC-friendly" affine transformations.
  • Empirical testing on combinatorial problems where SOS is known to be inefficient, such as the Knapsack or Planted Clique problems.
  • Extending these results from the boolean hypercube to more general finite varieties.

Summary updated

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 the analysis of 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 $n^{O(d)}$ nonnegative circuit polynomials.
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