Copositive Relaxation for General Quadratic Programming

A.J. Quist, E. de Klerk, C. Roos, T. Terlaky

We consider general, typically nonconvex, Quadratic Programming Problems. The Semi-definite relaxation proposed by Shor provides bounds on the optimal solution, but it does not always provide sufficiently strong bounds if linear constraints are also involved. To get rid of the linear side-constraints, another, stronger convex relaxation is derived. This relaxation uses copositive matrices. Special cases are discussed for which both relaxations are equal. At the end of the paper, the complexity and solvability of the relaxations are discussed.

Optimization Group TU Delft, Faculty of Information Technology and Systems, Delft University of Technology. To appear in Optimization Methods and Software.