A successive quadratic programming algorithm for sdp relaxation of the binary quadratic programming
Bull. Korean Math. Soc. 2005 Vol. 42, No. 4, 837-849
Published online 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.
Keywords : binary quadratic programming, successive quadratic programming algorithm, semidefinite programming, randomized method
MSC numbers : 90C22, 90C55
Full-Text :

   

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd