Mathematical Programming Computation, Volume 2, Numbers 3-4, December 2010

Font Size:  Small  Medium  Large

An inexact interior point method for L1-regularized sparse covariance selection

Lu Li, Kim-Chuan Toh


Sparse covariance selection problems can be formulated as logdeterminant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms.

Full Text: PDF

mpc footer
© MPS 2008-2017