Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm

Chengjing Wang (smawcnus.edu.sg)
Defeng Sun (matsundfnus.edu.sg)
Kim-Chuan Toh (mattohkcnus.edu.sg)

Abstract: We propose a Newton-CG primal proximal point algorithm for solving large scale log-determinant optimization problems. Our algorithm employs the essential ideas of the proximal point algorithm, the Newton method and the preconditioned conjugate gradient solver. When applying the Newton method to solve the inner sub-problem, we find that the log-determinant term plays the role of a smoothing term as in the traditional smoothing Newton technique. Focusing on the problem of maximum likelihood sparse estimation of a Gaussian graphical model, we demonstrate that our algorithm performs favorably comparing to the existing state-of-the-art algorithms and is much more preferred when a high quality solution is required for problems with many equality constraints.

Keywords: Log-determinant optimization problem, Sparse inverse covariance selection, Proximal-point algorithm, Newton's method

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Applications -- Science and Engineering (Statistics )

Citation: National University of Singapore, September, 2009.

Download: [PDF]

Entry Submitted: 09/29/2009
Entry Accepted: 09/29/2009
Entry Last Modified: 10/09/2009

Modify/Update this entry