Journal article
On convex relaxations for quadratically constrained quadratic programming
Mathematical programming, Vol.136(2), pp.233-251
12/01/2012
DOI: 10.1007/s10107-012-0602-3
Abstract
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 for . We next show that the use of "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.
Details
- Title: Subtitle
- On convex relaxations for quadratically constrained quadratic programming
- Creators
- Kurt M. Anstreicher - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.136(2), pp.233-251
- Publisher
- Springer Nature
- DOI
- 10.1007/s10107-012-0602-3
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Number of pages
- 19
- Language
- English
- Date published
- 12/01/2012
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380546702771
Metrics
3 Record Views