Name
Abstract | ||
|---|---|---|
Let \(\mathcal {F}\) be a quadratically constrained, possibly nonconvex, bounded set, and let \(\mathcal {E}_1, \ldots , \mathcal {E}_l\) denote ellipsoids contained in \(\mathcal {F}\) with non-intersecting interiors. We prove that minimizing an arbitrary quadratic \(q(\cdot )\) over \(\mathcal {G}:= \mathcal {F}{\setminus } \cup _{k=1}^\ell {{\mathrm{int}}}(\mathcal {E}_k)\) is no more difficult than minimizing \(q(\cdot )\) over \(\mathcal {F}\) in the following sense: if a given semidefinite-programming (SDP) relaxation for \(\min \{ q(x) : x \in \mathcal {F}\}\) is tight, then the addition of l linear constraints derived from \(\mathcal {E}_1, \ldots , \mathcal {E}_l\) yields a tight SDP relaxation for \(\min \{ q(x) : x \in \mathcal {G}\}\). We also prove that the convex hull of \(\{ (x,xx^T) : x \in \mathcal {G}\}\) equals the intersection of the convex hull of \(\{ (x,xx^T) : x \in \mathcal {F}\}\) with the same l linear constraints. Inspired by these results, we resolve a related question in a seemingly unrelated area, mixed-integer nonconvex quadratic programming. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s10107-017-1157-0 | Math. Program. |
Keywords | Field | DocType |
Nonconvex quadratic programming,Semidefinite programming,Convex hull,90C20,90C22,90C25,90C26,90C30 | Discrete mathematics,Mathematical optimization,Quadratic growth,Combinatorics,Bounded set,Convex hull,Quadratic equation,Quadratic programming,Mathematics,Semidefinite programming | Journal |
Volume | Issue | ISSN |
170 | 2 | 0025-5610 |
Citations | PageRank | References |
1 | 0.36 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boshi Yang | 1 | 11 | 1.59 |
| Kurt M. Anstreicher | 2 | 633 | 86.40 |
| Samuel Burer | 3 | 1148 | 73.09 |