|
|
Article: A successive linear programming algorithm for SDP relaxation of binary quadratic programming (1).(Technical report)
- Article from:
- Scientia Magna
- Article date:
- December 1, 2007
- Author:
CopyrightCOPYRIGHT 2007 American Research Press. This material is published under license from the publisher through the Gale Group, Farmington Hills, Michigan. All inquiries regarding rights should be directed to the Gale Group. (Hide copyright information)
|
Abstract In this paper, we obtain a successive linear 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.
[section] 1. Introduction
In this paper, we consider ...