Event
ISR Distinguished Lecturer: L. Vandenberghe, "Sparsity & Decomposition in Semidefinite Optimization"
Tuesday, March 22, 2016
5:00 p.m.
3117 CSIC
Regina King
301 405 6576
rking12@umd.edu
ISR Distinguished Lecturer
Sparsity and decomposition in semidefinite optimization
Lieven Vandenberghe
Professor, Electrical Engineering
University of California, Los Angeles
Host
André Tits
Abstract
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. In several of these applications, semidefinite optimization methods are restricted by the limited scalability of the available general-purpose solvers. The talk will present a survey of results and algorithms from sparse matrix theory that are useful when solving large semidefinite optimization problems with underlying graph structure. Classical theorems on positive semidefinite and Euclidean distance matrix completion of sparse matrices with a chordal sparsity pattern have interesting implications for the structure (sparsity and rank) of the solution of a semidefinite optimization problem with sparse coefficient matrices. Multifrontal algorithms for sparse Cholesky factorization can be extended to other fundamental matrix problems that arise in semidefinite optimization, for example, the computation of the partial inverse of a sparse positive definite matrix, and the evaluation of gradients and Hessians of logarithmic barriers for cones of sparse positive semidefinite matrices and their dual cones. The importance of these techniques for semidefinite optimization will be illustrated with applications to interior-point algorithms and first-order decomposition methods.
Biography
Lieven Vandenberghe is Professor in the Electrical Engineering Department at UCLA, with a courtesy 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, and has held visiting professor positions at K.U. Leuven and the Technical University of Denmark. 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). His research interests are in optimization, systems and control, and signal processing.
