  


How to Convexify the Intersection of a Second Order Cone and a Nonconvex Quadratic
Samuel Burer (samuelbureruiowa.edu) Abstract: A recent series of papers has examined the extension of disjunctiveprogramming techniques to mixedinteger secondordercone programming. For example, it has been shownby several authors using different techniquesthat 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 secondordercone 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 easytoverify 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, mixedinteger linear programming, mixedinteger nonlinear programming, mixedinteger quadratic programming, nonconvex quadratic programming, secondordercone programming, trustregion subproblem. Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 2: Global Optimization (Theory ) Category 3: Linear, Cone and Semidefinite Programming (SecondOrder Cone Programming ) Citation: Technical report, Department of Management Sciences, University of Iowa, June 2014. Download: [PDF] Entry Submitted: 06/04/2014 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  