(198d) Relaxations of Nonconvex, Quadratically-Constrained Quadratic Programs

Quadratic programming problems arise frequently in various industrial application settings, including facility location, multiperiod refinery, and circle packing problems. The general nonconvex quadratically constrained quadratic programming (QCQP) problem is NP hard and presents a significant challenge. We present a tight linear relaxation scheme for QCQP that can be used in the context of a branch-and-bound global optimization algorithm for this problem.

Most of the current approaches rely on convex relaxations of the QCQP problem which are either nonlinear [7, 2] or relaxing each nonconvex term separately [1, 5]. The main idea of our approach is to relax the entire quadratic constraints by linear underestimations. We propose a relaxation that is tighter than standard linear relaxation based on the convex envelope of multilinear functions [4, 3, 6] and develop an efficient mechanism to tighten the standard relaxation via a class of multilinear cutting planes. Computational experience shows the favorable features of the proposed relaxation.

[1] F. A. Al-Khayyal, C. Larsen, and T. V. Voorhis. A relaxation method for nonconvex quadratically constrained quadratic programs. Journal of Global Optimization, 6:215–230, 1995.

[2] S. Burer and D. Vandenbussche. A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Mathematical Programming, 2006. Published on-line, 12 December 2006, DOI 10.1007/s10107-006-0080-6.

[3] A. D. Rikun. A convex envelope formula for multilinear functions. Journal of Global Optimization, 10:425–437, 1997.

[4] H. D. Sherali. Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets. Acta Mathematica Vietnamica, 22:245–270, 1997.

[5] H. D. Sherali and C. H. Tuncbilek. A reformulation-convexification approach for solving nonconvex quadratic programming problems. Journal of Global Optimization, 7:1–31, 1995.

[6] M. Tawarmalani and N. V. Sahinidis. Convex extensions and convex envelopes of l.s.c. functions. Mathematical Programming, 93:247–263, 2002.

[7] N. V. Thoai. Duality bound method for the general quadratic programming problem with quadratic constraints. Journal of Optimization Theory and Applications, 107:331–354, 2000.