Sum-of-squares hierarchies for binary polynomial optimization

Lucas Slot*, Monique Laurent

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

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∈ N a lower bound f ( r ) on the minimum f min of f, given by the largest scalar λ for which the polynomial f- λ is a sum-of-squares on B n with degree at most 2r. We analyze the quality of these bounds by estimating the worst-case error f min- f ( r ) in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed t∈ [ 0, 1 / 2 ], we can show that this worst-case error in the regime r≈ t· n is of the order 1/2-t(1-t) as n tends to ∞. 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.
Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - Proceedings of the 22nd International Conference, IPCO 2021
EditorsMohit Singh, David P. Williamson
Place of PublicationCham
PublisherSpringer Verlag
Pages43-57
ISBN (Print)9783030738785
DOIs
Publication statusPublished - May 2021
EventInternational Conference on Integer Programming and Combinatorial Optimization - Georgia Tech, Atlanta, United States
Duration: 19 May 202121 May 2021
Conference number: 22nd International Conference
https://sites.gatech.edu/ipco-2021/

Publication series

NameLecture Notes in Computer Science
Volume12707

Conference

ConferenceInternational Conference on Integer Programming and Combinatorial Optimization
Abbreviated titleIPCO 2021
Country/TerritoryUnited States
CityAtlanta
Period19/05/2121/05/21
Internet address

Keywords

  • Binary polynomial optimization
  • Lasserre hierarchy
  • sum of squares polynomial
  • polynomial kernel
  • Semidefinite programming
  • Fourier Analysis
  • Krawtchouk polynomials

Fingerprint

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

Cite this