期刊名称：Department of Computer and System Sciences Antonio Ruberti Technical Reports
印刷版ISSN：2035-5750
出版年度：2009
卷号：1
期号：13
出版社：Department of Computer and System Sciences Antonio Ruberti. Sapienza, Università di Roma
摘要：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
