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

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 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.

References in corpus (1)

• Two-Term Disjunctions on the Second-Order Cone

Cited by in corpus (2)

• On Minimal Valid Inequalities for Mixed Integer Conic Programs
• Concave Quadratic Cuts for Mixed-Integer Quadratic Problems