Optimization Online


Exact SDP Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems

Shinsaku Sakaue(shinsaku_sakaue***at***mist.i.u-tokyo.ac.jp)
Akiko Takeda(takeda***at***mist.i.u-tokyo.ac.jp)
Sunyoung Kim(skim***at***ewha.ac.kr)
Naoki Ito(naoki_ito***at***mist.i.u-tokyo.ac.jp)

Abstract: For binary polynomial optimization problems (POPs) of degree $d$ with $n$ variables, we prove that the $\lceil(n+d-1)/2\rceil$th semidefinite (SDP) relaxation in Lasserre's hierarchy of the SDP relaxations provides the exact optimal value. If binary POPs involve only even-degree monomials, we show that it can be further reduced to $\lceil(n+d-2)/2\rceil$. 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 $\lceil(n+d-1)/2\rceil$th SDP relaxation for general binary POPs and the $\lceil(n+d-2)/2\rceil$th SDP relaxation for even-degree binary POPs to obtain the exact optimal values.

Keywords: Binary polynomial optimization problems, the hierarchy of the SDP relaxations, the bound for the exact SDP relaxation, even-degree binary polynomial optimization problems, chordal graph

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Global Optimization (Theory )

Citation: METR 2016-01, Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Bunkyo-ku, Tokyo 113-8656, Japan, January 2016

Download: [PDF]

Entry Submitted: 01/08/2016
Entry Accepted: 01/08/2016
Entry Last Modified: 01/08/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society