Please use this identifier to cite or link to this item:
Title: An inexact interior point method for L1-regularized sparse covariance selection
Authors: Li, L.
Toh, K.-C. 
Keywords: Inexact interior point method
Inexact search direction
Iterative solver
Log-determinant semidefinite programming
Sparse inverse covariance selection
Issue Date: 2010
Citation: Li, L., Toh, K.-C. (2010). An inexact interior point method for L1-regularized sparse covariance selection. Mathematical Programming Computation 2 (3-4) : 291-315. ScholarBank@NUS Repository.
Abstract: 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. © Springer and Mathematical Optimization Society 2010.
Source Title: Mathematical Programming Computation
ISSN: 18672949
DOI: 10.1007/s12532-010-0020-6
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jun 12, 2021

Page view(s)

checked on Jun 7, 2021

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.