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