A New Convex Relaxation for Quadratically Constrained Quadratic Programming

Duzhi Wu, Aiping Hu, Jie Zhou, Songlin Wu

A new relaxation strategy is presented in this paper to approximately solve the quadratically and linearly constrained quadratic programming. To improve the conservation of traditional semidefinite relaxation (SDR) strategy, we introduce a new linear constraint, which can be derived from the constraints of original problem, to the SDR problem. Furthermore, a randomization method is provided to extract good feasible solution of original problem from optimal solution of relaxed problem. Some numerical examples show that the proposed method can efficiently improve the performance of the traditional SDR strategy.