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.