Foundations and Trends® in Optimization > Vol 1 > Issue 4

Chordal Graphs and Semidefinite Optimization

Lieven Vandenberghe, University of California, Los Angeles, USA, vandenbe@ucla.edu Martin S. Andersen, Technical University of Denmark, Denmark, mskan@dtu.dk
 
Suggested Citation
Lieven Vandenberghe and Martin S. Andersen (2015), "Chordal Graphs and Semidefinite Optimization", Foundations and TrendsĀ® in Optimization: Vol. 1: No. 4, pp 241-433. http://dx.doi.org/10.1561/2400000006

Published: 27 May 2015
© 2015 L. Vandenberghe and M. S. Andersen
 
Subjects
Optimization,  Graphical models,  Operations research,  Statistical Signal Processing: tree-structured methods
 
Keywords
Semidefinite optimizationSemidefinite programmingConvex optimizationSparse matricesMatrix completion problemsGraph theory
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
2. Graphs
3. Chordal Graphs
4. Perfect Elimination Ordering
5. Combinatorial Optimization
6. Graph Elimination
7. Discrete Applications of Graph Elimination
8. Sparse Matrices
9. Positive Semidefinite Matrices
10. Positive Semidefinite Matrix Completion
11. Correlation and Euclidean Distance Matrices
12. Partial Separability in Convex Optimization
13. Conic Optimization
14. Sparse Semidefinite Optimization
Acknowledgments
Notation
References

Abstract

Chordal graphs play a central role in techniques for exploiting sparsity in large semidefinite optimization problems and in related convex optimization problems involving sparse positive semidefinite matrices. Chordal graph properties are also fundamental to several classical results in combinatorial optimization, linear algebra, statistics, signal processing, machine learning, and nonlinear optimization. This survey covers the theory and applications of chordal graphs, with an emphasis on algorithms developed in the literature on sparse Cholesky factorization. These algorithms are formulated as recursions on elimination trees, supernodal elimination trees, or clique trees associated with the graph. The best known example is the multifrontal Cholesky factorization algorithm, but similar algorithms can be formulated for a variety of related problems, including the computation of the partial inverse of a sparse positive definite matrix, positive semidefinite and Euclidean distance matrix completion problems, and the evaluation of gradients and Hessians of logarithmic barriers for cones of sparse positive semidefinite matrices and their dual cones. The purpose of the survey is to show how these techniques can be applied in algorithms for sparse semidefinite optimization, and to point out the connections with related topics outside semidefinite optimization, such as probabilistic networks, matrix completion problems, and partial separability in nonlinear optimization.

DOI:10.1561/2400000006
ISBN: 978-1-68083-038-5
215 pp. $99.00
Buy book
 
ISBN: 978-1-68083-039-2
215 pp. $125.00
Buy E-book
Table of contents:
1. Introduction
2. Graphs
3. Chordal Graphs
4. Perfect Elimination Orderings
5. Combinatorial Optimization
6. Graph Elimination
7. Discrete Applications of Graph Elimination
8. Sparse Matrices
9. Positive Semidefinite Matrices
10. Positive Semidefinite Matrix Completion
11. Correlation and Euclidean Distance Matrices
12. Partial Separability in Convex Optimization
13. Conic Optimization
14. Sparse Semidefinite Optimization
Acknowledgments
Notation
References

Chordal Graphs and Semidefinite Optimization

Chordal graphs play a central role in techniques for exploiting sparsity in large semidefinite optimization problems, and in related convex optimization problems involving sparse positive semidefinite matrices. Chordal graph properties are also fundamental to several classical results in combinatorial optimization, linear algebra, statistics, signal processing, machine learning, and nonlinear optimization.

Chordal Graphs and Semidefinite Optimization covers the theory and applications of chordal graphs, with an emphasis on algorithms developed in the literature on sparse Cholesky factorization. These algorithms are formulated as recursions on elimination trees, supernodal elimination trees, or clique trees associated with the graph. The best known example is the multifrontal Cholesky factorization algorithm but similar algorithms can be formulated for a variety of related problems, such as the computation of the partial inverse of a sparse positive definite matrix, positive semidefinite and Euclidean distance matrix completion problems, and the evaluation of gradients and Hessians of logarithmic barriers for cones of sparse positive semidefinite matrices and their dual cones. This monograph shows how these techniques can be applied in algorithms for sparse semidefinite optimization. It also points out the connections with related topics outside semidefinite optimization, such as probabilistic networks, matrix completion problems, and partial separability in nonlinear optimization.

 
OPT-006