Let S denote a subset of Rn defined by quadratic equality and inequality constraints and let S denote its projected semidefinite program (SDP) relaxation. For example, take S and S to be the epigraph of a quadratically constrained quadratic program (QCQP) and the projected epigraph of its SDP relaxation respectively. In this paper, we suggest and analyze a systematic rounding procedure defined in the original space that can be used to decide convex hull exactness, i.e., declare conv(S) = S or output a point in S \ conv(S). The motivation and analysis of this procedure stem from a geometric treatment of the projected SDP relaxation. Specifically, one of the major contributions of this paper is an explicit description of the set of rounding directions at a given point in S using only constraints in the original space. We close with a few applications of our framework recovering a well-known convex hull description, usually derived via the perspective reformulation trick, for a particular convex quadratic mixed integer set as well as new results on the NP-hard partition problem.
Article
View A Geometric View of SDP Exactness in QCQPs and its Applications