Copositive realxation for genera quadratic programming

Abstract

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

Keywords:

• Copositive Matrics
• Quadratic Programming
• Global Optimization
• Duality Theory
• Semi-definite Optimiztion
• Shor Relaxation