Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs
Abstract
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.
Related
- Global Extendability of Local Atoms in Sparse Moment Relaxations
- Local Reflexivity and Exactness for Reduced C*-Algebras of Wreath Products
- Sparse Moore-local realisations of binary irreducible polynomials on near-square lattice regions
- Robust Global Testing for Mean Functions in Sparse and Dense Functional and Longitudinal Data
- Sparse Koopman Autoencoders Identify Local Dynamical Regimes in Multibasin Systems
BibTeX
@misc{kojima2026localtoglobal,
title = {{Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs}},
author = {Masakazu Kojima and Sunyoung Kim and Naohiko Arima},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.21823},
eprint = {2606.21823},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.21823},
}
RIS
TY - UNPB
TI - Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs
AU - Masakazu Kojima
AU - Sunyoung Kim
AU - Naohiko Arima
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2606.21823
UR - https://arxiv.org/abs/2606.21823
AB - 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.
ER -