A successive linear programming algorithm for SDP relaxation of binary quadratic programming (1).
Scientia Magna › Vol. 3 Nbr. 4, December 2007
Linked as:
Summary
Technical report
See the full content of this document
Extract
A successive linear programming algorithm for SDP relaxation of binary quadratic programming (1).
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 the following binary quadratic programming min [x.sup.T]Qx + [2r.sup.T] x s.t. [x.sup.2.sub.i] = 1, for i = 1, ..., n, (1) where Q is an n x n real symmetric matrices, r is a real n-dimensional column vectors. Without loss of generality, we assume that Q is a positive definite matrix, because of the equivalence between [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all y [member of] R. In mathematical term, it means that Q > 0. The binary quadratic programming is a fundamental problem in optimization theory and practice. VLSI desig...See the full content of this document
Sponsored links
