Article information
2017 , Volume 22, ¹ 5, p.4757
Zabinyako G.I.
Applications of quasiNewton algorithms for solving large scale problems
In this paper, numerical stability of quasiNewton algorithms is studied, and their efficiency is estimated. Two types of quasiNewton algorithms are considered. In the BFGS algorithm, iterative approximations to the Hessian matrix 𝐵𝑘, are constructed. The matrix 𝐵𝑘 is maintained in a factored form, 𝐵 = 𝐿𝑘𝐷𝑘𝐿𝑇 , by a procedure based 𝑘 on the reflection method. In the limited  memory quasiNewton algorithm, LBFGS, approximations to the inverse Hessian matrix are constructed. Instead of the inverse Hessian 𝐻𝑘, ○ IAO SB RAS, 2017 LBFGS stores a few vectors that represent the quasiNewton updates. The accuracy and efficiency of the BFGS algorithms are compared by solving some test problems. A parallel LBFGS algorithm based on OpenMP programming interface is developed for solving large scale problems. The algorithm is tested on problems with a large number of variables. The use of the parallel algorithm makes it possible to significantly reduce the execution time in a wide range of the problem dimensions.
Keywords: quasiNewton algorithms, quasiNewton algorithms with limited memory, unconstrained minimization, OpenMP technology
Author(s): Zabinyako Gerard IdelfonovichPhD. , Senior Scientist Position: Head of Laboratory Office: ICMMG SB RAS Address: Russia, Novosibirsk
Email: zabin@rav.sscc.ru References: [1] Gill, P., Murray, W., Wright, M. Prakticheskaya optimizatsiya [Practical optimization]. Moscow: Mir; 1985:509. ( In Russ.) [2] Gill, P.E., Murray, W. QuasiNewton methods for unconstrained optimization. Journal of Mathematical Analysis and Applications. 1972; 9(1):91108. [3] Matthies, H., Strang, G. The solution of nonlinear finite element equations. International Journal for Numerical Methods in Engineering. 1979; (14):16131626. [4] Nocedal, J. Updating QuasiNewton Matrices With Limited Storage. Mathematics of Computation. 1980; 35(151):773782. [5] Zhu, C., Byrd, R.H., Lu, P., Nocedal, J. Algorithm 778 : LBFGSB: Fortran Subroutines for LargeScale BoundConstrained Optimization. ACM Transactions on Mathematical Software. 1997; 23(4):550560. [6] Byrd, R.H., Schnabel, R.B., Shultz, G.A. Parallel QuasiNewton methods for unconstrained optimization. Mathematical Programming. 1988; (42):273306. [7] Chen, W., Wang, Z., Zhou, J. Largescale LBFGS using MapReduce. Advances in Neural information Processing System. 2014; (27):13321340. [8] R. H. Byrd, S. L. Hansen, Jorge Nocedal, Y. Singer A Stochastic QuasiNewton Method for LargeScale Optimization. SIAM Journal on Optimization. 2016; 26(2):10081031. [9] R. H. Byrd, G. M. Chin, Jorge Nocedal, Yuchen Wu Sample size selection in optimization methods for machine learning. Mathematical Programming. Ser. B. 2012; (134):127–155. [10] Antonov, A.S. Parallel'noe programirovanie s ispol'zovaniem tekhnologii Open MP [Parallel programming using Open MP]. Moscow: Izdvo MGU; 2009: 76. (In Russ.) [11] Zabinyako, G.I. Programmy po nelineynomu programmirovaniyu na osnove kvazin'yutonovskogo metoda. Îtchet VTs SO RAN [Programme nonlinear programming based on quasiNewton method. The report of the Computing Center of the SB RAS; State Registration number 0186.0125752; Inventory]. Novosibirsk: VTs SO RAN; 1987: 123. (In Russ.) [12] Powell, M.J.D. Some global convergence properties of a variable metric algorithm for minimization without exact line searches. Nonlinear Programming. 1976; 9(1):5372. [13] Shanno, D.F., Phua, K.H. Minimization of Unconstrained Multivariate Functions. ACM Transactions on Mathematical Software. 1976; 2(1):8794. [14] Andrei, N. An Unconstrained Optimization Test Functions Collection. Advanced Modeling and Optimization. 2008; 10(1):147161.
Bibliography link: Zabinyako G.I. Applications of quasiNewton algorithms for solving large scale problems // Computational technologies. 2017. V. 22. ¹ 5. P. 4757
