Optimization Online


Quadratic Programs with Hollows

Boshi Yang(boshiy***at***andrew.cmu.edu)
Kurt Anstreicher(kurt-anstreicher***at***uiowa.edu)
Samuel Burer(samuel-burer***at***uiowa.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 )


Download: [PDF]

Entry Submitted: 01/06/2016
Entry Accepted: 01/07/2016
Entry Last Modified: 01/06/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society