2012/11/23 by Guo, Chuan-Hao, Bai, Yan-Qin, Tang, Li-Ping
#49M20 #90C10 #90C26 #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1211.5406
It has recently been shown (Burer, Math. Program Ser. A 120:479-495, 2009) that a large class of NP-hard nonconvex quadratic programming problems can be modeled as so called completely positive programming problems, which are convex but still NP-hard in general. A basic tractable relaxation is gotten by doubly nonnegative relaxation, resulting in a doubly nonnegative programming. In this paper, we prove that doubly nonnegative relaxation for binary quadratic programming (BQP) problem is equivalent to a tighter semidifinite relaxation for it. When problem (BQP) reduces to max-cut (MC) problem, doubly nonnegative relaxation for it is equivalent to the standard semidifinite relaxation. Furthermore, some compared numerical results are reported.