|
Article information
2017 , Volume 22, ¹ 5, p.47-57
Zabinyako G.I.
Applications of quasi-Newton algorithms for solving large scale problems
In this paper, numerical stability of quasi-Newton algorithms is studied, and their efficiency is estimated. Two types of quasi-Newton 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 quasi-Newton algorithm, L-BFGS, approximations to the inverse Hessian matrix are constructed. Instead of the inverse Hessian 𝐻𝑘, ○ IAO SB RAS, 2017 L-BFGS stores a few vectors that represent the quasi-Newton updates. The accuracy and efficiency of the BFGS algorithms are compared by solving some test problems. A parallel L-BFGS 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.
[full text]
Keywords: quasi-Newton algorithms, quasi-Newton algorithms with limited memory, unconstrained minimization, OpenMP technology
Author(s):
Zabinyako Gerard Idelfonovich
PhD. , Senior Scientist
Position: Head of Laboratory
Office: ICMMG SB RAS
Address: Russia, Novosibirsk
E-mail: 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. Quasi-Newton methods for unconstrained optimization. Journal of Mathematical Analysis and Applications. 1972; 9(1):91-108.
[3] Matthies, H., Strang, G. The solution of nonlinear finite element equations. International Journal for Numerical Methods in Engineering. 1979; (14):1613-1626.
[4] Nocedal, J. Updating Quasi-Newton Matrices With Limited Storage. Mathematics of Computation. 1980; 35(151):773-782.
[5] Zhu, C., Byrd, R.H., Lu, P., Nocedal, J. Algorithm 778 : L-BFGS-B: Fortran Subroutines for Large-Scale Bound-Constrained Optimization. ACM Transactions on Mathematical Software. 1997; 23(4):550-560.
[6] Byrd, R.H., Schnabel, R.B., Shultz, G.A. Parallel Quasi-Newton methods for unconstrained optimization. Mathematical Programming. 1988; (42):273-306.
[7] Chen, W., Wang, Z., Zhou, J. Large-scale L-BFGS using MapReduce. Advances in Neural information Processing System. 2014; (27):1332-1340.
[8] R. H. Byrd, S. L. Hansen, Jorge Nocedal, Y. Singer A Stochastic Quasi-Newton Method for Large-Scale Optimization. SIAM Journal on Optimization. 2016; 26(2):1008-1031.
[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: Izd-vo 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 quasi-Newton 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):53-72.
[13] Shanno, D.F., Phua, K.H. Minimization of Unconstrained Multivariate Functions. ACM Transactions on Mathematical Software. 1976; 2(1):87-94.
[14] Andrei, N. An Unconstrained Optimization Test Functions Collection. Advanced Modeling and Optimization. 2008; 10(1):147-161.
Bibliography link:
Zabinyako G.I. Applications of quasi-Newton algorithms for solving large scale problems // Computational technologies. 2017. V. 22. ¹ 5. P. 47-57
|
