Numerical Algebra, Control and Optimization (NACO)

Convergence analysis of sparse quasi-Newton updates with positive definite matrix completion for two-dimensional functions

Pages: 61 - 69, Volume 1, Issue 1, March 2011      doi:10.3934/naco.2011.1.61

       Abstract        References        Full Text (161.3K)       Related Articles       

Yuhong Dai - State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, P.O. Box 2719, Beijing 100080, China (email)
Nobuo Yamashita - Graduate School of Informatics, Kyoto University, Yoshida-honmachi, Sakyo-ku, Kyoto, 606-8501, Japan (email)

Abstract: In this paper, we briefly review the extensions of quasi-Newton methods for large-scale optimization. Specially, based on the idea of maximum determinant positive definite matrix completion, Yamashita (2008) proposed a new sparse quasi-Newton update, called MCQN, for unconstrained optimization problems with sparse Hessian structures. In exchange of the relaxation of the secant equation, the MCQN update avoids solving difficult subproblems and overcomes the ill-conditioning of approximate Hessian matrices. A global convergence analysis is given in this paper for the MCQN update with Broyden's convex family assuming that the objective function is uniformly convex and its dimension is only two.
    This paper is dedicated to Professor Masao Fukushima on occasion of his 60th birthday.

Keywords:  Quasi-Newton method, large-scale optimization, sparsity, positive definite matrix completion, global convergence.
Mathematics Subject Classification:  Primary: 90C53, 90C06.

Received: September 2010;      Revised: September 2010;      Available Online: February 2011.