Exact semidefinite programming relaxations with truncated moment matrix for binary polynomial optimization problems

Shinsaku Sakaue, Akiko Takeda, Sunyoung Kim, Naoki Ito

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

For binary polynomial optimization problems (POPs) of degree d with n variables, we prove that the d(n+d-1)=2eth semidefinite programming (SDP) relaxation in Lasserre's hierarchy of SDP relaxations provides the exact optimal value. If binary POPs involve only even-degree monomials, we show that it can be further reduced to d(n+d-2)=2e. This bound on the relaxation order coincides with the conjecture by Laurent in 2003, which was recently proved by Fawzi, Saunderson, and Parrilo, on binary quadratic optimization problems where d = 2. We also numerically confirm that the bound is tight. More precisely, we present instances of binary POPs that require solving at least the d(n + d - 1)=2eth SDP relaxation for general binary POPs and the d(n + d - 2)=2eth SDP relaxation for even-degree binary POPs to obtain the exact optimal values.

Original languageEnglish
Pages (from-to)565-582
Number of pages18
JournalSIAM Journal on Optimization
Volume27
Issue number1
DOIs
StatePublished - 2017

Keywords

  • Binary polynomial optimization problems
  • Bound for the exact SDP relaxation
  • Chordal graph
  • Even-degree binary polynomial optimization problems
  • Hierarchy of SDP relaxations

Fingerprint

Dive into the research topics of 'Exact semidefinite programming relaxations with truncated moment matrix for binary polynomial optimization problems'. Together they form a unique fingerprint.

Cite this