Speaker: Mituhiro Fukuda, Tokyo Institute of Technology

Title: A new nonmonotone spectral projected gradient method for semidefinite programming problem with log-determinant and l_1 norm objective function

Abstract: The semidefinite programming problem which has a log-determinant and l_1 norm terms in the objective function can be used to solve the covariance selection problem, that is, a problem to estimate a covariance matrix from few observations compared to the dimension of random variables in statistics. This problem is relatedo to the Gaussian Graphical Model. We propose a novel variant of the nonmonotone spectral projected gradient method applied to its dual problem which can solve our target problem with optimality certificate in some simple cases including the covariance selection problem. The implementation is very simple and major computational efforts required per iteration are a Cholesky decomposition and a eigenvalue computation. Numerical experiments on synthetic data shows that it is more efficient than some known algorithms.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491