ECE
ECE
ECE ECE


MIDAS Seminar

Sparsity and Decomposition in Semidefinite Optimization

Lieven Vandenberghe, PhD


Electrical and Computer Engineering Dept of Mathematics University of California, Los Angeles
 
Friday, April 06, 2018
4:00pm - 5:00pm
Weiser Hall, Low Rise, Room 182

Add to Google Calendar

About the Event

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.

Biography

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).

Additional Information

Contact: Alison Martin

Phone: (734) 615-8945

Email: aalison@umich.edu

Sponsor(s): MIDAS

Faculty Sponsor: Al Hero

Open to: Public

Web Page: http://midas.umich.edu/event/lieven-vandenberghe-phd-ucla-midas-seminar-series/