Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth

Richard Y. ZhangMath. Program 2023

Introduction

Semidefinite Programming (SDP) serves as a cornerstone for various optimization problems, ranging from control theory to combinatorial optimization. However, its practical application is often limited by the high computational cost of standard interior-point methods (IPMs). For an SDP involving $n \times n$ matrices and $m$ linear constraints, a direct application of IPMs typically requires $O(n^3)$ time per iteration. As $n$ grows into the thousands, this cubic scaling becomes a significant barrier for large-scale engineering and data science applications.

To address this, researchers have long employed "chordal conversion" (CC) to exploit problem sparsity. By decomposing a large semidefinite constraint into a collection of smaller ones based on the treewidth of the problem's sparsity graph, CC has enabled the solution of massive SDPs. Despite its empirical success, a rigorous theoretical foundation explaining why and when CC achieves linear scaling has been missing—until now.

The Theoretical Gap: Why Treewidth is Not Enough

The standard approach to analyzing sparsity in SDPs involves the aggregate sparsity graph $G$, which tracks the non-zero entries across all data matrices. It was previously hypothesized that a small treewidth in $G$ would be sufficient to guarantee efficient computation.

However, this paper demonstrates that $G$ alone is insufficient. Consider a diagonal SDP: its sparsity graph has a treewidth of zero, yet if the constraints couple the variables in a complex manner, the Schur complement matrix can still be dense, leading to $O(n^3)$ complexity. This discrepancy highlights a "coupling" effect where constraints link variables together, a factor not captured by the standard sparsity graph. This theoretical gap meant that practitioners could not always predict when chordal conversion would yield the expected speedups.

The Innovation: The Extended Aggregate Sparsity Graph ($\bar{G}$)

To bridge this gap, the author introduces the extended aggregate sparsity graph ($\bar{G}$). This new construct is formed by taking the standard sparsity graph $G$ and forcing each constraint matrix $A_i$ to be its own clique (a fully connected subgraph).

By accounting for the structure of individual constraints, $ar{G}$ captures the true coupling of the problem. The paper proves that the computational bottleneck of IPMs—solving the Schur complement equation—is directly governed by the treewidth of this extended graph. Specifically, if $tw(\bar{G})$ is small and independent of $m$ and $n$, the per-iteration cost of chordal conversion drops to $O(m+n)$.

Complexity and Convergence Guarantees

The paper provides the first formal proof that for SDPs with small extended treewidth, chordal conversion allows an IPM to achieve:

  • Linear Per-Iteration Complexity: $O(m+n)$ time per iteration.
  • Efficient Convergence: An $\epsilon$-accurate solution is reached in at most $O(\sqrt{m+n}\log(1/\epsilon))$ iterations.

This result provides a theoretical justification for why CC is often faster than the alternative Clique-Tree Conversion (CTC). While CTC is easier to analyze theoretically, it often incurs a significant performance penalty in preprocessing and per-iteration overhead. This work shows that the faster CC method is theoretically sound under the right conditions, justifying its use in high-performance solvers.

Empirical Validation and Applications

The theory is validated across several high-impact domains where chordal conversion has seen practical use:

  • Lovász Theta Problem: On synthetic $k$-trees, the author solved problems with up to 1,000,000 vertices in under 30 minutes. In these cases, $G$ and $\bar{G}$ are identical, explaining the natural efficiency.
  • AC Optimal Power Flow (OPF): Using the MATPOWER suite, the paper analyzes 72 real-world power system cases. For a massive 82,000-bus system, the proposed approach finished in 4 hours on a standard 4-core workstation—a task that previously required high-performance clusters with 24 cores.
  • Broad Applicability: The sufficient condition of small $tw(\bar{G})$ is shown to hold for MAX-$k$-CUT relaxations, sensor network localization, and polynomial optimization, aligning theoretical guarantees with years of practical experience.

Conclusion

By introducing the extended aggregate sparsity graph, this research provides the missing link between the empirical success of chordal conversion and its theoretical complexity. It establishes that the "gluing" effect of constraints is the primary driver of SDP complexity in sparse settings. This work not only justifies the use of CC in large-scale applications but also provides a framework for identifying which new problems are likely to benefit from these powerful decomposition techniques.

Summary updated

Abstract

If a sparse semidefinite program (SDP), specified over $n\times n$ matrices and subject to $m$ linear constraints, has an aggregate sparsity graph $G$ with small treewidth, then chordal conversion will sometimes allow an interior-point method to solve the SDP in just $O(m+n)$ time per-iteration, which is a significant speedup over the $Ω(n^{3})$ time per-iteration for a direct application of the interior-point method. Unfortunately, the speedup is not guaranteed by an $O(1)$ treewidth in $G$ that is independent of $m$ and $n$, as a diagonal SDP would have treewidth zero but can still necessitate up to $Ω(n^{3})$ time per-iteration. Instead, we construct an extended aggregate sparsity graph $\bar{G}\supseteq G$ by forcing each constraint matrix $A_{i}$ to be its own clique in $G$. We prove that a small treewidth in $\bar{G}$ does indeed guarantee that chordal conversion will solve the SDP in $O(m+n)$ time per-iteration, to $ε$-accuracy in at most $O(\sqrt{m+n}\log(1/ε))$ iterations. This sufficient condition covers many successful applications of chordal conversion, including the MAX-$k$-CUT relaxation, the Lovász theta problem, sensor network localization, polynomial optimization, and the AC optimal power flow relaxation, thus allowing theory to match practical experience.
BibTeX
@article{zhang2023complexity,
  author = {Richard Y. Zhang},
  title = {{Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth}},
  journal = {Math. Program.},
  year = {2023},
}
Figure