Low-Complexity Relaxations and Convex Hulls of Disjunctions on the Positive Semidefinite Cone and General Regular Cones

In this paper we analyze general two-term disjunctions on a regular cone $\K$ and derive a general form for a family of convex inequalities which are valid for the resulting nonconvex sets. Under mild technical assumptions, these inequalities collectively describe the closed convex hulls of these disjunctions, and if additional conditions are satisfied, a single inequality from this family is sufficient. In the cases where $\K$ is the positive semidefinite cone or a direct product of second-order cones and a nonnegative orthant, we show that these convex inequalities admit equivalent conic forms for certain choices of disjunctions. Our approach relies on and generalizes the work of Kilinc-Karzan and Yildiz which considers general two-term disjunctions on the second-order cone. Along the way, we establish a connection between two-term disjunctions and nonconvex sets defined by rank-two quadratics, through which we extend our convex hull results to intersections of a regular cone with such quadratic sets.

Article

Download

View PDF