Parameterized Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth

arXiv2306.15288MaRDI QIDQ6441637

Richard Zhang

Publication date: 27 June 2023

Abstract: If a sparse semidefinite program (SDP), specified over $nimesn$ matrices and subject to $m$ linear constraints, has an aggregate sparsity graph $G$ with small treewidth, then chordal conversion will frequently allow an interior-point method to solve the SDP in just $O(m+n)$ time per-iteration. This is a significant reduction over the minimum $Omega(n^3)$ time per-iteration for a direct solution, but a definitive theoretical explanation was previously unknown. Contrary to popular belief, the speedup is not guaranteed by a small treewidth in $G$, as a diagonal SDP would have treewidth zero but can still necessitate up to $Omega(n^3)$ time per-iteration. Instead, we construct an extended aggregate sparsity graph $overlineGsupseteqG$ by forcing each constraint matrix $A_i$ to be its own clique in $G$. We prove that a small treewidth in $overlineG$ does indeed guarantee that chordal conversion will solve the SDP in $O(m+n)$ time per-iteration, to $epsilon$-accuracy in at most $O(sqrtm+nlog(1/epsilon))$ iterations. For classical SDPs like the MAX-$k$-CUT relaxation and the Lovasz Theta problem, the two sparsity graphs coincide $G=overlineG$, so our result provide a complete characterization for the complexity of chordal conversion, showing that a small treewidth is both necessary and sufficient for $O(m+n)$ time per-iteration. Real-world SDPs like the AC optimal power flow relaxation have different graphs $GsubseteqoverlineG$ with similar small treewidths; while chordal conversion is already widely used on a heuristic basis, in this paper we provide the first rigorous guarantee that it solves such SDPs in $O(m+n)$ time per-iteration. [Supporting code at https://github.com/ryz-codes/chordalConv/]

Has companion code repository: https://github.com/ryz-codes/chordalconv

This page was built for publication: Parameterized Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6441637)