Semidefinite Programming Relaxation for Nonconvex Quadratic Programs
Tetsuya Fujie and Masakazu Kojima
Any quadratic inequality in the n-dimensional
Euclidean space can be relaxed into a linear matrix inequality in
(1+n) times (1+n) symmetric matrices. Based on this principle,
we extend the Lovasz-Schrijver SDP (semidefinite programming)
relaxation developed for a 0-1 integer program to a general
nonconvex QP (quadratic program), and present some fundamental
characterization of the SDP relaxation including its equivalence
to a relaxation using convex-quadratic valid inequalities for
the feasible region of the QP.
Report B-298,
Dept. of Mathematical and Computing Sciences, Tokyo Institute
of Technology, Tokyo, May 1995; revised August 1996. To
appear in Journal of Global Optimization.
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)