Optimization Online


How to Convexify the Intersection of a Second Order Cone and a Nonconvex Quadratic

Samuel Burer (samuel-burer***at***uiowa.edu)
Fatma Kilinc-Karzan (fkilinc***at***andrew.cmu.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.

Download: [PDF]

Entry Submitted: 06/04/2014
Entry Accepted: 06/04/2014
Entry Last Modified: 05/24/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