An unconstrained approach for solving low rank SDP relaxations of {-1, 1} quadratic problems

Abstract

We consider low-rank semidefinite programming (LRSDP) relaxations of {-1, 1} quadratic problems that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an efficient and globally convergent algorithm for finding critical points of the LRSDP problem. Finally, we test our code on an extended set of instances of the Max-Cut problem and we report comparisons with other existing codes