Quadratic Programs with Hollows

Let $\F$ be a quadratically constrained, possibly nonconvex, bounded set, and let $\E_1, \ldots, \E_l$ denote ellipsoids contained in $\F$ with non-intersecting interiors. We prove that minimizing an arbitrary quadratic $q(\cdot)$ over $\G := \F \setminus \cup_{k=1}^\ell \myint(\E_k)$ is no more difficult than minimizing $q(\cdot)$ over $\F$ in the following sense: if a given semidefinite-programming (SDP) relaxation for $\min \{ q(x) : x \in \F \}$ is tight, then the addition of $l$ linear constraints derived from $\E_1, \ldots, \E_l$ yields a tight SDP relaxation for $\min \{ q(x) : x \in \G \}$. We also prove that the convex hull of $\{ (x,xx^T) : x \in \G \}$ equals the intersection of the convex hull of $\{ (x,xx^T) : x \in \F \}$ with the same $l$ linear constraints.

Article

Download

View PDF