The equivalence between doubly nonnegative relaxation and semidefinite relaxation for binary quadratic programming problems

arXiv1211.5406MaRDI QIDQ6237399FDOQ6237399

Chuanhao Guo, Liping Tang, Yanqin Bai

Publication date: 22 November 2012

Abstract: 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.

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Integer programming (90C10) Numerical methods of relaxation type (49M20)

This page was built for publication: The equivalence between doubly nonnegative relaxation and semidefinite relaxation for binary quadratic programming problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237399)