A limited memory adaptive trust-region approach for large-scale unconstrained optimization

Document Type: Research Paper

Authors

1 Faculty of Mathematics‎, ‎University of Vienna‎, ‎Oskar-Morge-nstern-Platz 1‎, ‎1090 Vienna‎, ‎Austria.

2 Department of‎ ‎Mathematics‎, ‎Razi University‎, ‎Kermanshah‎, ‎Iran.

3 Department of‎ ‎Mathematics‎, ‎Asadabad Branch‎, ‎Islamic Azad University‎, ‎Asadabad‎, ‎Iran.

4 K.N. Toosi University of Department of‎ ‎Mathematics‎, ‎K‎. ‎N‎. ‎Toosi University of Technology‎, ‎P.O‎. ‎Box 16315-1618‎, ‎Tehran‎, ‎Iran.

Abstract

This study concerns with a trust-region-based method for solving unconstrained optimization problems. The approach takes the advantages of the compact limited memory BFGS updating formula together with an appropriate adaptive radius strategy. In our approach, the adaptive technique leads us to decrease the number of subproblems solving, while utilizing the structure of limited memory quasi-Newton formulas helps to handle large-scale problems. Theoretical analysis indicates that the new approach preserves the global convergence to a first-order stationary point under classical assumptions. Moreover, the superlinear and the quadratic convergence rates are also established under suitable conditions. Preliminary numerical experiments show the effectiveness of the proposed approach for solving large-scale unconstrained optimization problems.

Keywords

Main Subjects


M. Ahookhosh and K. Amini, A nonmonotone trust region method with adaptive radius for unconstrained optimization problems, Comput. Math. Appl. 60 (2010), no. 3, 411--422.

M. Ahookhosh, H. Esmaeili and M. Kimiaei, An effective trust-region-based approach for symmetric nonlinear systems, Int. J. Comput. Math. 90 (2013), no. 3, 671--690.

K. Amini and M. Ahookhosh, A hybrid of adjustable trust-region and nonmonotone algorithms for unconstrained optimization, Appl. Math. Model. 38 (2014), no. 9-10, 2601--2612.

K. Amini and M. Ahookhosh, Combination adaptive trust region method by non-monotone strategy for unconstrained nonlinear programming, Asia-Pac. J. Oper. Res. 28 (2011), no. 5, 585--600.

N. Andrei, An unconstrained optimization test functions collection, Adv. Model. Optim. 10 (2008), no. 1, 147--161.

D. Ataee Tarzanagh, M. R. Peyghami and H. Mesgarani, A new nonmonotone trust region method for unconstrained optimization equipped by an efficient adaptive radius, Optim. Methods Softw. 29 (2014), no. 4, 819--836.

F. Bastin, V. Malmedy, M. Mouffe, Ph. L. Toint and D. Tomanos, A retrospective trust-region method for unconstrained optimization, Math. Programming 123 (2008), no. 2, 395--418.

J. V. Burke, A. Wiegmann and L. Xu, Limited memory BFGS updating in a trust-region framework, SIAM Journal on Optimization. submitted, 2008.

R. H. Byrd, P. Lu and J. Nocedal, A limited memory algorithm for bound constrained optimization, SIAM J. Sci. Comput. 16 (1995), no. 5, 1190--1208.

R. Byrd, J. Nocedal and R. Schnabel, Representation of quasi-Newton matrices and their use in limited memory methods, Math. Programming 63 (1994), no. 2, 129--156.

A. R. Conn, N. I. M. Gould and Ph. L. Toint, LANCELOT. A Fortran package for large scale nonlinear optimization (release A), Springer Series in Computational Mathematics, 17, Springer-Verlag, Berlin, 1992.

A. R. Conn, N. I. M. Gould and Ph. L. Toint, Trust-Region Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2000.

E. Dolan and J. J. Morfie, Benchmarking optimization software with performance profiles, Math. Program. 21 (2002), no. 2, 201--213.

H. Esmaeili and M. Kimiaei, An efficient adaptive trust-region method for systems of nonlinear equations, Int. J. Comput. Math. 92 (2015), no. 1, 151--166.

H. Esmaeili and M. Kimiaei, A new adaptive trust-region method for system of nonlinear equations, Appl. Math. Model. 38 (2014), no. 11--12, 3003--3015.

R. Fletcher, Practical Method of Optimization, Wiley, NewYork, 2000.

N. Gould, S. Lucidi, M. Roma and Ph. L. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim. 9 (1999), no. 2, 504--525.

N. I. M. Gould, D. Orban and A. Sartenaer and P. L. Toint, Sensitivity of trust-region algorithms to their parameters, 4OR 3 (2005), no. 3, 227--241.

D. C. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization, Math. Programming 45 (1989), no. 3, 503--528.

L. Kaufman, Reduced storage, quasi-Newton trust region approaches to function optimization, SIAM J. Optim. 10 (1999), no. 1, 56--69.

J. L. Morales and J. Nocedal, Enriched methods for large-scale unconstrained optimization, Comput. Optim. Appl. 21 (2002), no. 2, 143--154.

 J. L. Morales and J. Nocedal, L-BFGS-B: Remark on Algorithm 778: L-BFGS-B, FOR-TRAN routines for large scale bound constrained optimization, to appear in ACM Trans.Math. Software, 2011.

J. J. Morfie, B. S. Garbow and K. E. Hillstrom, Testing Unconstrained Optimization Software, ACM Trans. Math. Software 7 (1981) 17--41.

S. G. Nash and J. Nocedal, A numerical study of the limited memory BFGS method and the truncated Newton method for large scale optimization, SIAM J. Optim. 1 (1991), no. 3, 358--372.

J. Nocedal, Updating quasi-Newton matrices with limited storage, Mathematics of Computation. 35 (1980), no. 151, 773--782.

J. Nocedal and S. J. Wright, Numerical Optimization, Springer, New York, 2006.

J. Nocedal and Y. Yuan, Combining trust region and line search techniques, in: Y. Yuan (Ed.), Advanced in nonlinear programming, 153--175, Kluwer Acad. Publ., Dordrecht, 1998.

M. J. D. Powell, A new algorithm for unconstrained optimization, In: Rosen JB, Mangasarian OL, Ritter K (eds) Nonlinear programming, 31--66, Academic Press, New York, 1970.

M. J. D. Powell, On the global convergence of trust region algorithms for unconstrained minimization, Math. Programming 29 (1984) 297--303.

A. Sartenaer, Automatic determination of an initial trust region in nonlinear programming, SIAM J. Sci. Statist. Comput. 18 (1997), no. 6, 1788--1803.

R. B. Schnabel and E. Eskow, A new modified Cholesky factorization, SIAM J. Sci. Statist. Comput. 11 (1990), no. 6, 1136--1158.

G. A. Schultz, R. B. Schnabel and R. H. Byrd, A family of trust-region-based algorithms for unconstrained minimization with strong global convergence, SIAM J. Numer. Anal. 22 (1985), no. 1, 47--67.

Z. J. Shi and J. H. Guo, A new trust region method with adaptive radius, Comput. Optim. Appl., 213 (2008), no. 2, 509--520.

T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal. 20 (1983), no. 3, 626--637.

X. S. Zhang, J. L. Zhang and L. Z. Liao, An adaptive trust region method and its convergence, Sci. China Ser. A 45 (2002), no. 5, 620--631.

C. Zhu, R. H. Byrd and J. Nocedal, Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization, ACM Trans. Math. Software 23 (1997), no. 4, 550--560.

http://users.eecs.northwestern.edu/ nocedal/lbfgsb.html