An inexact interior point method for L 1-regularized sparse covariance selection
- 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.
Metadaten| Author: | Lu Li, Kim-Chuan Toh |
|---|
| DOI: | https://doi.org/10.1007/s12532-010-0020-6 |
|---|
| ISSN: | 1867-2949 |
|---|
| Parent Title (English): | Mathematical Programming Computation |
|---|
| Publisher: | Springer Science and Business Media LLC |
|---|
| Document Type: | Article |
|---|
| Language: | English |
|---|
| Year of Completion: | 2010 |
|---|
| Tag: | Software; Theoretical Computer Science |
|---|
| Volume: | 2 |
|---|
| Issue: | 3-4 |
|---|
| Page Number: | 25 |
|---|
| First Page: | 291 |
|---|
| Last Page: | 315 |
|---|
| Mathematical Programming Computation : | MPC 2010 - Issue 3-4 |
|---|