Necessary and Sufficient Conditions for Rank-One-Generated Cones

C. J. Argue (), Fatma Kılınç-Karzan () and Alex L. Wang ()
Additional contact information
C. J. Argue: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Fatma Kılınç-Karzan: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Alex L. Wang: Department of Computer Science, CarnegieMellon University, Pittsburgh, Pennsylvania

Mathematics of Operations Research, 2023, vol. 48, issue 1, 100-126

Abstract: A closed convex conic subset S of the positive semidefinite (PSD) cone is rank-one generated (ROG) if all of its extreme rays are generated by rank-one matrices. The ROG property of S is closely related to the exactness of semidefinite program (SDP) relaxations of nonconvex quadratically constrained quadratic programs (QCQPs) related to S . We consider the case where S is obtained as the intersection of the PSD cone with finitely many homogeneous linear matrix inequalities and conic constraints and identify sufficient conditions that guarantee that S is ROG. Our general framework allows us to recover a number of well-known results from the literature. In the case of two linear matrix inequalities, we also establish the necessity of our sufficient conditions. This extends one of the few settings from the literature—the case of one linear matrix inequality and the S-lemma—where an explicit characterization for the ROG property exists. Finally, we show how our ROG results on cones can be translated into inhomogeneous SDP exactness results and convex hull descriptions in the original space of a QCQP. We close with a few applications of these results; specifically, we recover the well-known perspective reformulation of a simple mixed-binary set via the ROG toolkit.

Keywords: Primary: 90C20; 90C22; 90C26; secondary: 15A63; 15B48; rank-one; semidefinite program; quadratic program; relaxation (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1254 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:1:p:100-126

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().