Analysis of Sparse Quasi-Newton Updates with Positive Definite Matrix Completion  

作　　者：Yu-Hong Dai Nobuo Yamashita 

机构地区：[1]State Key Laboratory of Scientific and Engineering Computing,Institute of Computational Mathematics and Scientific/Engineering Computing,Academy of Mathematics and Systems Science,Chinese Academy of Sciences,P.O.Box 2719,Beijing 100080,People’s Republic of China [2]Department of Applied Mathematics and Physics,Graduate School of Informatics,Kyoto University,Kyoto 606-8501,Japan

出　　处：《Journal of the Operations Research Society of China》2014年第1期39-56,共18页中国运筹学会会刊（英文）

基　　金：This work was supported by the Chinese NSF Grants(Nos.11331012 and 81173633);the China National Funds for Distinguished Young Scientists(No.11125107);the CAS Program for Cross&Coorperative Team of the Science&Technology Innovation;The authors are grateful to Professors Masao Fukushima and Ya-xiang Yuan for their warm encouragement and valuable suggestions.They also thank the two anonymous referees very much for their useful comments on an early version of this paper.

摘　　要：Based on the idea of maximum determinant positive definite matrix completion,Yamashita(Math Prog 115(1):1–30,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.However,local and superlinear convergence results were only established for the MCQN update with the DFP method.In this paper,we extend the convergence result to the MCQN update with the whole Broyden’s convex family.Numerical results are also reported,which suggest some efficient ways of choosing the parameter in the MCQN update the Broyden’s family.

关 键 词：Quasi-Newton method Large-scale problems SPARSITY Positive definite matrix completion Superlinear convergence 

分 类 号：O17[理学—数学]