Abstract:
Semidefinite programming is an extension of linear programming in which
the componentwise vector inequalities are replaced with semidefinite
matrix inequalities.
Applications can be found in a variety of fields, including control
theory, statistics and machine learning, and combinatorial optimization.
Semidefinite programming is also used extensively in the popular convex
optimization modeling software packages CVX and YALMIP.
While many algorithms for linear programming can be extended to
semidefinite programming, the problem of exploiting sparsity in
semidefinite programming is substantially more difficult than in
linear programming, due to the nonlinear coupling of the variables in
the matrix inequalities.
In this talk we will discuss approaches to sparse semidefinite
programming, based on properties of positive semidefinite matrices
with chordal sparsity patterns, results from matrix completion theory,
and first-order splitting algorithms for convex optimization.
|
