Optimization Online


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

Sercan Yildiz(syildiz***at***andrew.cmu.edu)
Fatma Kilinc-Karzan(fkilinc***at***andrew.cmu.edu)

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

Keywords: Mixed-integer conic programming, semidefinite programming, cutting-planes, disjunctive inequalities

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 04/07/2016
Entry Accepted: 04/07/2016
Entry Last Modified: 04/07/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