LIDS Colloquium
Chordal sparsity in normal
graphical models and semidefinite
programming.
Lieven Vandenberghe
UCLA
Tuesday,
Dec. 4, 2007
Time:
4:00-5:00 p.m.
Location:
32-141
Refreshments
will be served after the seminar at 5:00 pm at the 6th Floor LIDS
Lounge.
Abstract:
Chordal graphs are important in sparse linear algebra, graphical
models, and sparse semidefinite programming. Their importance derives from the property that positive definite matrices with chordal
sparsity patterns can be factored with zero
fill-in. In matrix optimization, chordal sparsity can be exploited
in fast algorithms for evaluating the function values, gradients, and Hessians
of the logarithmic barrier function of the cone of positive definite matrices
with the given sparsity pattern, and of the
corresponding dual cone. We will discuss
two applications of these techniques. The first is covariance selection
(maximum likelihood estimation of normal graphical models) with large nonchordal graphs, via a chordal
embedding and standard unconstrained minimization methods. The second
application is the implementation of primal and dual barrier methods for semidefinite programms with chordal sparsity. This includes as special cases second-order
cone programming, matrix norm minimization, certain types of robust
optimization problems, and semidefinite programming
with band structure.
Biography:
Lieven Vandenberghe is
Professor in the Electrical Engineering Department at the