Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs

We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity pattern graph of the data matrices, we formulate the SDP relaxation in terms of clique-wise matrix variables and develop a local-to-global framework for certifying exactness. For each clique-wise matrix variable, we introduce a local sub-SDP with two parameters: a local right-hand-side vector and a consistency matrix specifying the values of entries shared by overlapping clique-wise matrix  variables. In the main theorem, these parameters are determined by an optimal solution of the global clique-wise SDP. The theorem shows that if the resulting local sub-SDPs are exact,  then the original SDP relaxation is exact. Under the additional assumption that any two distinct cliques intersect in at most one node, we present three classes of local QCQPs that can be incorporated into this framework: convex local QCQPs, local QCQPs characterized by sign-pattern conditions, and separable local QCQPs with a limited number of constraints. Examples illustrate how these different local QCQP classes can be combined in sparse QCQPs.

Article

Download

View PDF