Sparsity and decomposition in semidefinite programming

Professor Lieven Vandenberghe
Professor, UCLA
Given on: November 15, 2012


Sparse semidefinite programs can be viewed as linear conic optimization problems with respect to two types of convex matrix cones: the cone of positive semidefinite matrices with a given sparsity pattern and its dual cone, the cone of matrices with the same sparsity that have a positive semidefinite completion. If the sparsity pattern is chordal, the dual cone is partially separable, i.e., an intersection of simpler lower-dimensional convex cones. In this talk we apply ideas from multifrontal sparse matrix factorization algorithms to exploit chordal structure in interior-point methods for sparse semidefinite programming. We also discuss connections between the multifrontal algorithms and decomposition methods for conic optimization with partially separable cones.

Joint work with Martin Andersen.


Lieven Vandenberghe is Professor in the Electrical Engineering Department and the Mathematics Department at the University of California, Los Angeles. He received a Ph.D. in Electrical Engineering from the K.U. Leuven, Belgium, in 1992, and has held visiting Professor positions at K.U. Leuven and the Technical University of Denmark. He is author (with S. Boyd) of the book Convex Optimization (2004) and editor (with H. Wolkowicz and R. Saigal) of the Handbook of Semidefinite Programming (2000).