Optimization Online


On convex relaxations for quadratically constrained quadratic programming

Kurt Anstreicher(kurt-anstreicher***at***uiowa.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society