Sparsity and Decomposition in Semidefinite Optimization
Semidefinite optimization is an important tool in control, signal processing, machine learning, combinatorial optimization, and other disciplines. It is also heavily used in convex optimization modeling software. However, in large-scale applications, semidefinite optimization approaches are still limited by the scalability of the available general-purpose solvers. The talk will present a survey of results from sparse matrix theory that are useful in algorithms for large semidefinite programs with sparse coefficients. The sparsity pattern typically represents the graph structure in the underlying application as, for example, in semidefinite relaxations of power flow optimization problems, sensor network node localization problems, or Euclidean distance matrix problems in machine learning. In semidefinite relaxations of polynomial optimization problems, the sparsity pattern expresses partially separable structure in the polynomials. Sparsity in a semidefinite optimization problem has important implications for the structure (sparsity and rank) of the solutions.
The talk will focus on applications of classical results in linear algebra and graph theory, and, in particular, the fact that for chordal sparsity patterns it is easy to compute zero-fill Cholesky factorizations, and maximum-determinant or minimum-rank positive semidefinite completions. It will be shown how these results can be used in semidefinite optimization algorithms (interior-point, first-order, and decomposition algorithms). Data structures and techniques from the sparse matrix literature, such as elimination trees, supernodal elimination trees, and multifrontal algorithms will play a unifying role in the derivation of the key results and algorithms.
Lieven Vandenberghe is Professor in the Electrical and Computer Engineering Department at UCLA, with a joint appointment in the Department of Mathematics. He received a Ph.D. in Electrical Engineering from K.U. Leuven, Belgium, in 1992. He joined UCLA in 1997, following postdoctoral appointments at K.U. Leuven and Stanford University. He is author (with Stephen Boyd) of the book Convex Optimization (2004) and editor (with Henry Wolkowicz and Romesh Saigal) of the Handbook of Semidefinite Programming (2000).