How to Convexify the Intersection of a Second Order Cone and a Nonconvex Quadratic
Samuel Burer (samuel-bureruiowa.edu)
Abstract: A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown---by several authors using different techniques---that the convex hull of the intersection of an ellipsoid, $\E$, and a split disjunction, $(l - x_j)(x_j - u) \le 0$ with $l < u$, equals the intersection of $\E$ with an additional second-order-cone representable (SOCr) set. In this paper, we study more general intersections of the form $\K \cap \Q$ and $\K \cap \Q \cap H$, where $\K$ is a SOCr cone, $\Q$ is a nonconvex cone defined by a single homogeneous quadratic, and $H$ is an affine hyperplane. Under several easy-to-verify conditions, we derive a simple, computable convex relaxations $\K \cap \S$ and $\K \cap \S \cap H$, where $\S$ is a SOCr cone. Under further conditions, we prove that these two sets capture precisely the corresponding conic/convex hulls. Our approach unifies and extends previous results, and we illustrate its applicability and generality with many examples.
Keywords: convex hull, disjunctive programming, mixed-integer linear programming, mixed-integer nonlinear programming, mixed-integer quadratic programming, nonconvex quadratic programming, second-order-cone programming, trust-region subproblem.
Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )
Category 2: Global Optimization (Theory )
Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )
Citation: Technical report, Department of Management Sciences, University of Iowa, June 2014.
Entry Submitted: 06/04/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|