Sum-of-squares hierarchies for binary polynomial optimization

Lucas Slot*, Monique Laurent

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)


We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial f over the boolean hypercube B-n = {0, 1}(n). This hierarchy provides for each integer r epsilon N a lower bound f((r)) on the minimum f(min) of f, given by the largest scalar lambda for which the polynomial f - lambda is a sum-of-squares on B-n with degree at most 2r. We analyze the quality of these bounds by estimating the worstcase error f(min) - f((r)) in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed t epsilon [0, 1/2], we can show that this worst-case error in the regime r approximate to t . n is of the order 1/2- root t(1 - t) as n tends to infinity. Our proof combines classical Fourier analysis on B-n with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds f((r)) and another hierarchy of upper bounds f((r)), for which we are also able to establish the same error analysis. Our analysis extends to the minimization of a polynomial over the q-ary cube (Z/qZ)(n). Furthermore, our results apply to the setting ofmatrix-valued polynomials.
Original languageEnglish
Pages (from-to)621-660
Number of pages40
JournalMathematical Programming
Publication statusPublished - Feb 2023


  • Binary polynomial optimization
  • Lasserre hierarchy
  • Sum-of-squares polynomials
  • Fourier analysis
  • Krawtchouk polynomials
  • Polynomial kernels
  • Semidefinite programming
  • Polynomial matrices
  • CUT


Dive into the research topics of 'Sum-of-squares hierarchies for binary polynomial optimization'. Together they form a unique fingerprint.

Cite this