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.