- Quadratic Programs with Hollows Boshi Yang(boshiyandrew.cmu.edu) Kurt Anstreicher(kurt-anstreicheruiowa.edu) Samuel Burer(samuel-bureruiowa.edu) Abstract: 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. Keywords: nonconvex quadratic programming, semidefinite programming, convex hull Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Citation: Download: [PDF]Entry Submitted: 01/06/2016Entry Accepted: 01/07/2016Entry Last Modified: 01/06/2016Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.