Complexity of chordal conversion for sparse semidefinite programs with small treewidth

If a sparse semidefinite program (SDP), specified over \(n\times n\) $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)\) $O(m+n)$ time per-iteration, which is a significant speedup over the \(\varOmega (n^{3})\) $\Omega (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 \(\varOmega (n^{3})\) $\Omega (n^3)$ time per-iteration. Instead, we construct an extended aggregate sparsity graph \(\overline{G}\supseteq G\) $\overline{G}\supseteq G$ by forcing each constraint matrix \(A_{i}\) $A_i$ to be its own clique in G. We prove that a small treewidth in \(\overline{G}\) $\overline{G}$ does indeed guarantee that chordal conversion will solve the SDP in \(O(m+n)\) $O(m+n)$ time per-iteration, to \(\epsilon \) $ϵ$ -accuracy in at most \(O(\sqrt{m+n}\log (1/\epsilon ))\) $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.