On convex relaxations for quadratically constrained quadratic programming

摘要

We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let ? 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 ? is dominated by an alternative methodology based on convexifying the range of the quadratic form (1 x) (1 x)T for xεFscr;. We next show that the use of "alpha BB" 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. (difference of convex) underestimators is dominated by a relaxation that combines semidefiniteness with RLT constraints.