  We propose a method for low-rank semidefinite programming in application to
the semidefinite relaxation of unconstrained binary quadratic problems. The
method improves an existing solution of the semidefinite programming relaxation
to achieve a lower rank solution. This procedure is computationally efficient
as it does not require projecting on the cone of positive-semidefinite
matrices. Its performance in terms of objective improvement and rank reduction
is tested over multiple graphs of large-scale Gset graph collection and over
binary optimization problems from the Biq Mac collection.

Optimization and Control;Computational Complexity