EXACT SEMIDEFINITE PROGRAMMING RELAXATIONS WITH TRUNCATED MOMENT MATRIX FOR BINARY POLYNOMIAL OPTIMIZATION PROBLEMS
- 주제(키워드) binary polynomial optimization problems , hierarchy of SDP relaxations , bound for the exact SDP relaxation , even-degree binary polynomial optimization problems , chordal graph
- 관리정보기술 faculty
- 등재 SCIE, SCOPUS
- 발행기관 SIAM PUBLICATIONS
- 발행년도 2017
- URI http://www.dcollection.net/handler/ewha/000000147333
- 본문언어 영어
- Published As http://dx.doi.org/10.1137/16M105544X
초록/요약
For binary polynomial optimization problems (POPs) of degree d with n variables, we prove that the [(n+d-1)/2]th 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 [(n+d-2)/2]. 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 [(n+d-1)/2]th SDP relaxation for general binary POPs and the [(n+d-2)/2]th SDP relaxation for even-degree binary POPs to obtain the exact optimal values.
more