A successive quadratic programming algorithm for sdp relaxation of the binary quadratic programming
Bull. Korean Math. Soc. 2005 Vol. 42, No. 4, 837-849 Printed December 1, 2005
Xuewen Mu, Sanyang Liu, and Yaling Zhang Xidian University, Xdian University, Xi'an University of Science and Technology
Abstract : In this paper, we obtain a successive quadratic programming algorithm for solving the semidefinite programming (SDP) relaxation of the binary quadratic programming. Combining with a randomized method of Goemans and Williamson, it provides an efficient approximation for the binary quadratic programming. Furthermore, its convergence result is given. At last, We report some numerical examples to compare our method with the interior-point method on Maxcut problem.