×

On efficiently combining limited-memory and trust-region techniques. (English) Zbl 1368.90103

Summary: Limited-memory quasi-Newton methods and trust-region methods represent two efficient approaches used for solving unconstrained optimization problems. A straightforward combination of them deteriorates the efficiency of the former approach, especially in the case of large-scale problems. For this reason, the limited-memory methods are usually combined with a line search. We show how to efficiently combine limited-memory and trust-region techniques. One of our approaches is based on the eigenvalue decomposition of the limited-memory quasi-Newton approximation of the Hessian matrix. The decomposition allows for finding a nearly-exact solution to the trust-region subproblem defined by the Euclidean norm with an insignificant computational overhead as compared with the cost of computing the quasi-Newton direction in line-search limited-memory methods. The other approach is based on two new eigenvalue-based norms. The advantage of the new norms is that the trust-region subproblem is separable and each of the smaller subproblems is easy to solve. We show that our eigenvalue-based limited-memory trust-region methods are globally convergent. Moreover, we propose improved versions of the existing limited-memory trust-region algorithms. The presented results of numerical experiments demonstrate the efficiency of our approach which is competitive with line-search versions of the L-BFGS method.

MSC:

90C06 Large-scale problems in mathematical programming
90C30 Nonlinear programming
90C53 Methods of quasi-Newton type
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Björk, Å.: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996) · Zbl 0847.65023 · doi:10.1137/1.9781611971484
[2] Brust, J., Erway, J.B., Marcia, R.F.: On solving L-SR1 trust-region subproblems. arXiv:1506.07222 (2015) · Zbl 1364.90239
[3] Buckley, A., LeNir, A.: QN-like variable storage conjugate gradients. Math. Program. 27(2), 155-175 (1983) · Zbl 0519.65038 · doi:10.1007/BF02591943
[4] Burdakov, O.P.: Methods of the secant type for systems of equations with symmetric Jacobian matrix. Numer. Funct. Anal. Optim. 6, 183-195 (1983) · Zbl 0543.65028 · doi:10.1080/01630568308816160
[5] Burdakov, O.P.: Stable versions of the secant method for solving systems of equations. USSR Comput. Math. Math. Phys. 23(5), 1-10 (1983) · Zbl 0561.65038 · doi:10.1016/S0041-5553(83)80150-5
[6] Burdakov, O.P.: On superlinear convergence of some stable variants of the secant method. Z. Angew. Math. Mech. 66(2), 615-622 (1986) · Zbl 0616.65055 · doi:10.1002/zamm.19860661212
[7] Burdakov, O., Gong, L., Zikrin, S., Yuan, Y.: On efficiently combining limited memory and trust-region techniques. Tech. rep. 2013:13, Linköping University (2013) · Zbl 1368.90103
[8] Burdakov, O.P., Martínez, J.M., Pilotta, E.A.: A limited-memory multipoint symmetric secant method for bound constrained optimization. Ann. Oper. Res. 117, 51-70 (2002) · Zbl 1025.90038 · doi:10.1023/A:1021561204463
[9] Burdakov, O., Yuan, Y: On limited-memory methods with shape changing trust-region. In: Proceedings of the first international conference on optimization methods and software, Huangzhou, China, p. 21 (2002) · Zbl 0888.65072
[10] Burke, J.V., Wiegmann, A., Xu, L.: Limited memory BFGS updating in a trust-region framework. Tech. rep., University of Washington (2008) · Zbl 0964.90061
[11] Byrd, R.H., Nocedal, J., Schnabel, R.B.: Representations of quasi-Newton matrices and their use in limited memory methods. Math. Program. 63, 129-156 (1994) · Zbl 0809.90116 · doi:10.1007/BF01582063
[12] Byrd, R.H., Schnabel, R.B., Shultz, G.A.: Approximate solution of the trust-region problem by minimization over two-dimensional subspaces. Math. Program. 40(1-3), 247-263 (1988) · Zbl 0652.90082 · doi:10.1007/BF01580735
[13] Conn, A.R., Gould, N.I.M., Toint, P.L.: Convergence of quasi-Newton matrices generated by the symmetric rank one update. Math. Program. 50(1-3), 177-195 (1991) · Zbl 0737.90062 · doi:10.1007/BF01594934
[14] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-region methods. MPS/SIAM Ser. Optim. 1, SIAM, Philadelphia (2000) · Zbl 0958.65071
[15] Dennis Jr., J.E., Mei, H.H.W.: Two new unconstrained optimization algorithms which use function and gradient values. J. Optim. Theory Appl. 28(4), 453-482 (1979) · Zbl 0388.65022 · doi:10.1007/BF00932218
[16] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[17] Erway, J.B., Gill, P.E., Griffin, J.: Iterative methods for finding a trust-region step. SIAM J. Optim. 20(2), 1110-1131 (2009) · Zbl 1189.49049 · doi:10.1137/070708494
[18] Erway, J.B., Jain, V., Marcia, R.F.: Shifted L-BFGS systems. Optim. Methods Softw. 29(5), 992-1004 (2014) · Zbl 1300.90066 · doi:10.1080/10556788.2014.894045
[19] Erway, J.B., Marcia, R.F.: Limited-memory BFGS systems with diagonal updates. Linear Algebr. Appl. 437(1), 333-344 (2012) · Zbl 1246.65088 · doi:10.1016/j.laa.2012.02.005
[20] Erway, J.B., Marcia, R.F.: Algorithm 943: MSS: MATLAB Software for L-BFGS trust-region subproblems for large-scale optimization. ACM Trans. Math. Softw. 40(4), 28:1-28:12 (2014) · Zbl 1371.65050
[21] Erway, J.B., Marcia, R.F.: On efficiently computing the eigenvalues of limited-memory quasi-Newton matrices. SIAM J. Matrix Anal. Appl. 36(3), 1338-1359 (2015) · Zbl 1337.49048 · doi:10.1137/140997737
[22] Erway, J.B., Marcia, R.F.: On solving limited-memory quasi-Newton equations. arXiv:1510.06378 (2015) · Zbl 1337.49048
[23] Gilbert, J.C., Lemaréchal, C.: Some numerical experiments with variable-storage quasi-Newton algorithms. Math. Program. 45(1-3), 407-435 (1989) · Zbl 0694.90086 · doi:10.1007/BF01589113
[24] Gill, P.E., Leonard, M.W.: Limited-memory reduced-Hessian methods for large-scale unconstrained optimization. SIAM J. Optim. 14, 380-401 (2003) · Zbl 1046.65045 · doi:10.1137/S1052623497319973
[25] Golub, G., Van Loan, C.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013) · Zbl 1268.65037
[26] Gould, N.I.M., Lucidi, S., Roma, M., Toint, P.L.: Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9(2), 504-525 (1999) · Zbl 1047.90510 · doi:10.1137/S1052623497322735
[27] Gould, N.I.M., Orban, D., Toint, P.L.: CUTEr and SifDec: a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29(4), 373-394 (2003) · Zbl 1068.90526 · doi:10.1145/962437.962439
[28] Hager, W., Zhang, H.: A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J. Optim. 16(1), 170-192 (2005) · Zbl 1093.90085 · doi:10.1137/030601880
[29] Kaufman, L.: Reduced storage, quasi-Newton trust-region approaches to function optimization. SIAM J. Optim. 10(1), 56-69 (1999) · Zbl 0964.90061 · doi:10.1137/S1052623496303779
[30] Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45(1-3), 503-528 (1989) · Zbl 0696.90048 · doi:10.1007/BF01589116
[31] Lu, X: A study of the limited memory SR1 method in practice. Doctoral Thesis, University of Colorado at Boulder (1996) · Zbl 0561.65038
[32] Moré, J.J., Sorensen, D.: Computing a trust-region step. SIAM J. Sci. Stat. Comput. 4(3), 553-572 (1983) · Zbl 0551.65042 · doi:10.1137/0904038
[33] Moré, J.J., Thuente, D.J.: Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20(3), 286-307 (1994) · Zbl 0888.65072 · doi:10.1145/192115.192132
[34] Nocedal, J.: Updating quasi-Newton matrices with limited storage. Math. Comp. 35(151), 773-782 (1980) · Zbl 0464.65037 · doi:10.1090/S0025-5718-1980-0572855-7
[35] Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Ser. Oper. Res. Springer, New York (2006) · Zbl 1104.65059
[36] O’Leary, D.: A Matlab implementation of a MINPACK line search algorithm by Jorge J. Moré and David J. Thuente (1991). https://www.cs.umd.edu/users/oleary/software/. Accessed 1 November 2012 · Zbl 0518.65042
[37] Powell, MJD; Rabinowitz, P. (ed.), A hybrid method for nonlinear equations, 87-114 (1970), London · Zbl 0277.65028
[38] Powell, MJD; Rosen, OLMJB (ed.); Ritter, K. (ed.), A new algorithm for unconstrained optimization (1970), New York · Zbl 0228.90043
[39] Steihaug, T.: The conjugate gradient method and trust-regions in large scale optimization. SIAM J. Numer. Anal. 20(3), 626-637 (1983) · Zbl 0518.65042 · doi:10.1137/0720042
[40] Sun, W., Yuan, Y.: Optimization Theory and Methods. Nonlinear Programming, Springer Optimization and Its Applications 1, Springer, New York (2006) · Zbl 1068.90526
[41] Toint, PL; Duff, IS (ed.), Towards an efficient sparsity exploiting Newton method for minimization, 57-88 (1981), London · Zbl 0463.65045
[42] Wolfe, P.: Convergence conditions for ascent methods. SIAM Rev. 11(2), 226-235 (1969) · Zbl 0177.20603 · doi:10.1137/1011036
[43] Yuan, Y., Stoer, J.: A subspace study on conjugate gradient algorithms. ZAMM Z. Angew. Math. Mech. 75(1), 69-77 (1995) · Zbl 0823.65061 · doi:10.1002/zamm.19950750118
[44] Yuan, Y.: Recent advances in trust-region algorithms. Math. Program. 151(1), 249-281 (2015) · Zbl 1317.65141 · doi:10.1007/s10107-015-0893-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.