On efficiently combining limited-memory and trust-region techniques
Tóm tắt
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.
Tài liệu tham khảo
Björk, Å.: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996)
Brust, J., Erway, J.B., Marcia, R.F.: On solving L-SR1 trust-region subproblems. arXiv:1506.07222 (2015)
Buckley, A., LeNir, A.: QN-like variable storage conjugate gradients. Math. Program. 27(2), 155–175 (1983)
Burdakov, O.P.: Methods of the secant type for systems of equations with symmetric Jacobian matrix. Numer. Funct. Anal. Optim. 6, 183–195 (1983)
Burdakov, O.P.: Stable versions of the secant method for solving systems of equations. USSR Comput. Math. Math. Phys. 23(5), 1–10 (1983)
Burdakov, O.P.: On superlinear convergence of some stable variants of the secant method. Z. Angew. Math. Mech. 66(2), 615–622 (1986)
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)
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)
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)
Burke, J.V., Wiegmann, A., Xu, L.: Limited memory BFGS updating in a trust-region framework. Tech. rep., University of Washington (2008)
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)
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)
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)
Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-region methods. MPS/SIAM Ser. Optim. 1, SIAM, Philadelphia (2000)
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)
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)
Erway, J.B., Gill, P.E., Griffin, J.: Iterative methods for finding a trust-region step. SIAM J. Optim. 20(2), 1110–1131 (2009)
Erway, J.B., Jain, V., Marcia, R.F.: Shifted L-BFGS systems. Optim. Methods Softw. 29(5), 992–1004 (2014)
Erway, J.B., Marcia, R.F.: Limited-memory BFGS systems with diagonal updates. Linear Algebr. Appl. 437(1), 333–344 (2012)
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)
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)
Erway, J.B., Marcia, R.F.: On solving limited-memory quasi-Newton equations. arXiv:1510.06378 (2015)
Gilbert, J.C., Lemaréchal, C.: Some numerical experiments with variable-storage quasi-Newton algorithms. Math. Program. 45(1–3), 407–435 (1989)
Gill, P.E., Leonard, M.W.: Limited-memory reduced-Hessian methods for large-scale unconstrained optimization. SIAM J. Optim. 14, 380–401 (2003)
Golub, G., Van Loan, C.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013)
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)
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)
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)
Kaufman, L.: Reduced storage, quasi-Newton trust-region approaches to function optimization. SIAM J. Optim. 10(1), 56–69 (1999)
Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45(1–3), 503–528 (1989)
Lu, X: A study of the limited memory SR1 method in practice. Doctoral Thesis, University of Colorado at Boulder (1996)
Moré, J.J., Sorensen, D.: Computing a trust-region step. SIAM J. Sci. Stat. Comput. 4(3), 553–572 (1983)
Moré, J.J., Thuente, D.J.: Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20(3), 286–307 (1994)
Nocedal, J.: Updating quasi-Newton matrices with limited storage. Math. Comp. 35(151), 773–782 (1980)
Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Ser. Oper. Res. Springer, New York (2006)
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
Powell, M.J.D.: A hybrid method for nonlinear equations. In: Rabinowitz, P. (ed.) Numerical Methods for Nonlinear Algebraic Equations, pp. 87–114. Gordon and Breach, London (1970)
Powell, M.J.D.: A new algorithm for unconstrained optimization. In: Rosen, O.L.M.J.B., Ritter, K. (eds.) Nonlinear Programming. Academic Press, New York (1970)
Steihaug, T.: The conjugate gradient method and trust-regions in large scale optimization. SIAM J. Numer. Anal. 20(3), 626–637 (1983)
Sun, W., Yuan, Y.: Optimization Theory and Methods. Nonlinear Programming, Springer Optimization and Its Applications 1, Springer, New York (2006)
Toint, P.L.: Towards an efficient sparsity exploiting Newton method for minimization. In: Duff, I.S. (ed.) Sparse Matrices and Their Uses, pp. 57–88. Academic Press, London (1981)
Wolfe, P.: Convergence conditions for ascent methods. SIAM Rev. 11(2), 226–235 (1969)
Yuan, Y., Stoer, J.: A subspace study on conjugate gradient algorithms. ZAMM Z. Angew. Math. Mech. 75(1), 69–77 (1995)
Yuan, Y.: Recent advances in trust-region algorithms. Math. Program. 151(1), 249–281 (2015)