Name
Abstract | ||
|---|---|---|
Abstract We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let \(\mathcal{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 \(\mathcal{F }\) is dominated by an alternative methodology based on convexifying the range of the quadratic form \(\genfrac(){0.0pt}{}{1}{x}\genfrac(){0.0pt}{}{1}{x}^T\) for \(x\in \mathcal{F }\). 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10107-012-0602-3 | Math. Program. |
Keywords | Field | DocType |
Quadratically constrained quadratic programming,Convex envelope,Semidefinite programming,Reformulation-linearization technique | Diagonal,Second-order cone programming,Discrete mathematics,Quadratic growth,Mathematical optimization,Combinatorics,Quadratically constrained quadratic program,Quadratic form,Convex hull,Feasible region,Quadratic programming,Mathematics | Journal |
Volume | Issue | ISSN |
136 | 2 | 1436-4646 |
Citations | PageRank | References |
27 | 0.98 | 14 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kurt M. Anstreicher | 1 | 633 | 86.40 |