  


Exact SDP Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
Shinsaku Sakaue(shinsaku_sakauemist.i.utokyo.ac.jp) Abstract: For binary polynomial optimization problems (POPs) of degree $d$ with $n$ variables, we prove that the $\lceil(n+d1)/2\rceil$th semidefinite (SDP) relaxation in Lasserre's hierarchy of the SDP relaxations provides the exact optimal value. If binary POPs involve only evendegree monomials, we show that it can be further reduced to $\lceil(n+d2)/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+d1)/2\rceil$th SDP relaxation for general binary POPs and the $\lceil(n+d2)/2\rceil$th SDP relaxation for evendegree 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, evendegree binary polynomial optimization problems, chordal graph Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Global Optimization (Theory ) Citation: METR 201601, Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Bunkyoku, Tokyo 1138656, Japan, January 2016 Download: [PDF] Entry Submitted: 01/08/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  