  


Quadratic Programs with Hollows
Boshi Yang(boshiyandrew.cmu.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 nonintersecting 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 semidefiniteprogramming (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 (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 01/06/2016 Modify/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  