Sparsity and decomposition in semidefinite programming

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.