Convex Relaxations with Second Order Cone Constraints for Nonconvex Quadratically Constrained Quadratic Programming

In this paper, we present new convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP) problems. Since the basic semidefinite programming relaxation is often too loose for general QCQP, recent research has focused on strengthening convex relaxations using valid linear or second order cone (SOC) inequalities. In this paper, we con- struct valid second order cone constraints for nonconvex QCQP and reduce the duality gap using these valid constraints. Specifically, we decompose and relax the nonconvex constraints to two SOC constraints and then linearize the products of the SOC constraints and linear constraints to achieve some new valid constraints. Moreover, we introduce and generalize two recent tech- niques for generating valid inequalities to further enhance our method. We demonstrate the efficiency of our results with numerical experiments.