Lieven Vandenberghe UCLA “Sparsity and decomposition in semidefinite optimization” Wednesday, January 18, 2017 2:00 – 3:00PM EEB 132 Abstract: Semidefinite optimization is an important tool in control and signal processing, machine learning, combinatorial optimization, and other disciplines. It is also heavily used in convex optimization modeling software. Large semidefinite optimization problems often have coefficients with a common, `aggregate' sparsity pattern. This sparsity pattern typically represents the underlying graph structure in the application, as is the case, for example, in semidefinite relaxations of power flow optimization problems. In semidefinite relaxations of polynomial optimization problems, the sparsity pattern expresses partially separable structure in the original problem. Aggregate sparsity in a semidefinite optimization problem has important implications for the structure (sparsity and rank) of the solutions of the problem. Exploiting these properties is crucial in theoretical analysis and algorithm development. The talk will focus on applications of classical results in sparse matrix theory, and, in particular, the fact that, for chordal sparsity patterns, zero-fill Cholesky factorizations, maximum-determinant and minimum-rank positive semidefinite completions, and minimum-dimension Euclidean distance matrix completions are simple to characterize and easy to compute. Data structures and techniques familiar from the sparse matrix literature, such as elimination trees, supernodal elimination trees, and multifrontal algorithms, will play a central role in the derivation of the key results and algorithms. Biography: Lieven Vandenberghe is Professor in the Electrical 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, 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.
