Chordal Decomposition for Large Scale Semidefinite Programming

This direction is split into other directions: chordal sparsity decomposition. Its last version stays readable and citable here.

Version 1 of 167 papers104 conceptsfrozen 2026-10-04

Semidefinite Programming (SDP) is often described as the "Swiss Army Knife" of optimization. It provides a powerful way to find global solutions to complex, non-convex problems by "relaxing" them into a convex form. However, SDPs have a notorious weakness: they do not scale well. As the number of variables grows, the size of the required matrix constraints explodes, leading to what Jean B. Lasserre calls the "curse of dimensionality."

The research direction explored here provides a way out of this bottleneck. By exploiting the inherent sparsity of real-world systems—from power grids to neural networks—researchers have developed methods to decompose a single, massive matrix constraint into a collection of smaller, overlapping ones. This transformation allows solvers to handle problems with thousands of variables that were previously considered computationally impossible.

The Intuition: Sparsity as a Graph

To understand why this works, imagine a large-scale system like a power grid. While the grid might have thousands of "buses" (nodes), any single bus is only physically connected to a few neighbors. In the language of optimization, this means the variables are "sparsely coupled."

If we represent these interactions as a graph, where nodes are variables and edges are constraints, we find that the graph is not a dense web where everything touches everything else. Instead, it is sparse. Antonis Papachristodoulou and Matthew Newton have shown that even deep neural networks exhibit this property: because neurons only interact layer-by-layer, the resulting optimization problem has a cascading, sparse structure known as chordal sparsity Exploiting Sparsity for Neural Network Verification.

The Mechanism: Chordal Decomposition

The core breakthrough in this field is the use of chordal decomposition. A graph is "chordal" if every cycle of four or more nodes has a "chord"—an edge connecting two non-adjacent nodes in the cycle.

The fundamental theorem driving this research (often attributed to Grone et al.) states that a sparse matrix is positive semidefinite (PSD) if and only if the smaller sub-matrices corresponding to the maximal cliques of its chordal completion are also PSD.

As Yang Zheng and colleagues explain in Fast ADMM for semidefinite programs with chordal sparsity, this allows us to replace one giant constraint ($X \succeq 0$) with many smaller ones ($X_{C_i} \succeq 0$). This is transformative because:

  1. Memory Efficiency: Instead of storing a $10,000 \times 10,000$ matrix, the solver only needs to manage several $10 \times 10$ or $100 \times 100$ blocks.
  2. Computational Speed: Solvers like the Alternating Direction Method of Multipliers (ADMM) can project onto these smaller cones much faster than a single large one.
  3. Parallelism: Because the constraints are localized to cliques, different parts of the problem can often be solved in parallel.

Beyond Variables: Term Sparsity and TSSOS

While chordal sparsity looks at which variables interact, a second layer of efficiency comes from looking at which monomials appear in a polynomial. This is known as term sparsity.

Jie Wang, Jean B. Lasserre, and Victor Magron introduced the TSSOS (Term Sparse SOS) hierarchy to exploit this TSSOS: A Moment-SOS hierarchy that exploits term sparsity. Even if variables are densely connected, the specific combinations of those variables (the terms) might be sparse. By analyzing the "support" of the polynomial, TSSOS breaks down the large moment matrices of the Lasserre hierarchy into block-diagonal structures.

Later, they combined both ideas in Chordal-TSSOS, using chordal extensions to further subdivide these blocks, enabling the certification of global optimality for massive systems like the AC Optimal Power Flow (AC-OPF) with over 6,500 buses Certifying Global Optimality of AC-OPF Solutions via sparse polynomial optimization.

Challenges and Trade-offs

Despite the speedups, decomposition is not a free lunch. Andrew Knyazev pointed out a significant numerical hurdle: degeneracy. When the optimal solution to an SDP is low-rank, the overlapping constraints in a chordal decomposition can become linearly dependent, leading to ill-conditioning and slower convergence in standard solvers Degeneracy in maximal clique decomposition for Semidefinite Programs.

Furthermore, while Richard Y. Zhang has proven that chordal conversion can achieve linear-time complexity per iteration for problems with small "treewidth," the preprocessing step of finding a good chordal completion is itself a complex task Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth.

Summary of Impact

By shifting the focus from the total number of variables to the structure of their interactions, this research direction has moved SDP from a theoretical tool for small problems to a practical engine for industrial-scale engineering. Whether it is proving the safety of a neural network Sparse Polynomial Optimisation for Neural Network Verification or managing the complexities of a continental power grid Equivalent relaxations of optimal power flow, the ability to "divide and conquer" through chordal and term sparsity remains the key to scaling high-order optimization.

Papers in this version

Showing 60 of 67 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_chordal_decomposition_for_large_scale_se_7c0acff8,
  title = {Chordal Decomposition for Large Scale Semidefinite Programming},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/chordal-decomposition-for-large-scale-semidefinite-programming/rdr_7c0acff84638474497bc06340489b5c6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_chordal_decomposition_for_large_scale_se_7c0acff8_v1,
  title = {Chordal Decomposition for Large Scale Semidefinite Programming},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/chordal-decomposition-for-large-scale-semidefinite-programming/rdr_7c0acff84638474497bc06340489b5c6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}