Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs

Abstract

Nonconvex quadratic constraints can be linearized to obtain relaxations in a well-understood manner. We propose to tighten the relaxation by using second-order cone constraints, resulting in a convex quadratic relaxation. Our quadratic approximation to the bilinear term is compared to the linear McCormick bounds. The second-order cone constraints are based on linear combinations of pairs of variables. With good bounds on these linear combinations, the resulting constraints strengthen the McCormick bounds. Computational results are given, which indicate that the convex quadratic relaxation can dramatically improve the solution times for some problems.

Keywords:

• quadratically constrained quadratic programs
• second-order cones
• convex outer approximations

Acknowledgements

The work of the first author was supported by the National Science Foundation under grant DMS-0715446 and by the Air Force Office of Sponsored Research under grants FA9550-08-01-0081 and FA9550-11-1-0260. The work of the second author was supported by the Air Force Office of Sponsored Research under grants FA9550-08-1-0061 and FA9550-11-1-0151 and by the National Science Foundation under grant CMMI-0969600. We also thank the referee for careful and thorough reading of this manuscript and several helpful suggestions.