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.
From: Sunyoung Kim [view email]
[v1]
Sat, 20 Jun 2026 01:24:17 UTC (111 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。