On convex relaxations for quadratically constrained quadratic programming

Kurt Anstreicher(kurt-anstreicheruiowa.edu)

Abstract: We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let F denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on F is dominated by an alternative methodology based on convexifying the range of the quadratic form (1;x)(1,x') for x in F. We next show that the use of "alphaBB" underestimators as computable estimates of convex lower envelopes is dominated by a relaxation of the convex hull of the quadratic form that imposes semidefiniteness and linear constraints on diagonal terms. Finally, we show that the use of a large class of "D.C." underestimators is dominated by a relaxation that combines semidefiniteness with RLT constraints.

Keywords: Quadratically constrained quadratic programming, convex envelope, semidefinite programming, reformulation-linearization technique

Category 1: Global Optimization (Theory )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Department of Management Sciences, University of Iowa, July 2010.

Download: [PDF]

Entry Submitted: 08/04/2010
Entry Accepted: 08/04/2010
Entry Last Modified: 08/04/2010

Modify/Update this entry