Convergence Rate of Greedy SR1 With Trust Region Method
DOI:
https://doi.org/10.54097/axh66s95Keywords:
superlinear convergence; Quasi-Newton method; SR1 method; Trust Region method.Abstract
Recently, Greedy Quasi-Newton methods have attracted wide interests of some researchers for their explicit superlinear convergence rate. These algorithms which achieve rapid local convergence construct a matrix sequence to approximate the Hessian matrix of the objective function iteratively. This paper proposes an algorithm, GR-SR1-TR, which incorporate Greedy SR1 method with Trust Region framework and employs a new correction technique. We prove that the approximation matrix sequence has a linear descent property under the Frobenius-norm metric. Further, both the global convergence and an explicit superlinear rate are established. The effectiveness of GR-SR1-TR has been verified by preliminary numerical experiments.
Downloads
References
[1] W. C. Davidon. Variable metric method for minimization. SIAM Journal on optimization, 1(1), 1–17, 1991.
[2] R. Fletcher, M. J. D. Powell, A rapidly convergent descent method for minimization. Computer journal, 6(2), 163–168, 1963.
[3] G. Donald, A family of variable-metric methods derived by variational means. Mathematics of computation, 24(109), 23–26, 1970.
[4] R. Fletcher, A new approach to variable metric algorithms. Computer journal, 13(3), 317–322, 1970.
[5] D.F. Shanno, Conditioning of Quasi-Newton methods for function minimization. Mathematics of computation, 24, 647–656, 1970.
[6] A. R. Conn, N. I. M. Gould, P. L. Toint, Convergence of Quasi-Newton matrices generated by the symmetric rank one update. Mathematical Programming, 50(1–3), 177–195, 1991.
[7] H. L. Krauss, C. W. Bostian, and F. H. Raab, Solid State Radio Engineering, New York: J. Wiley & Sons, 1980.
[8] Y. H. Dai, Convergence properties of the BFGS algorithm. SIAM Journal on optimization, 13, 693–701, 2003.
[9] Y. H. Dai, A perfect example for the BFGS method. Mathematical Programming, 138, 501–530, 2013.
[10] D. H. Li, M. Fukushima, On the global convergence of the BFGS method for nonconvex unconstrained optimization problems. SIAM Journal on optimization, 11, 1054–1064, 2001.
[11] W. F. Mascarenhas, The BFGS method with exact line searches fails for non-convex objective functions. Mathematical Programming, 99, 49–61, 2004.
[12] J. J. Moré, J. A. Trangenstein, On the global convergence of Broyden’s method. Mathematics of computation, 30, 523–540, 1976.
[13] C. G. Broyden, J. E. Dennis, J. J. Moré, On the local and superlinear convergence of Quasi-Newton methods. IMA Journal of Applied Mathematics, 12(3), 223–245, 1973.
[14] J. E. Dennis, J.J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods. Mathematics of computation, 28(126), 549–560, 1974.
[15] L. C. W. Dixon, Quasi-Newton algorithms generate identical points. Mathematical Programming, 2(1), 383–387, 1972.
[16] M. J. D. Powell, On the convergence of the variable metric algorithm. IMA Journal of Applied Mathematics, 7(1), 21–36, 1971.
[17] R. H. Byrd, D. C. Liu, J. Nocedal, On the behavior of Broyden’s class of Quasi-Newton methods. SIAM Journal on optimization, 2(4), 533–557, 1992.
[18] J. Engels, H. Martínez, Local and superlinear convergence for partially known Quasi-Newton methods. SIAM Journal on optimization, 1(1), 42–56, 1991.
[19] W. Gao, D. Goldfarb, Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions. Optimization Methods and Software, 34(1), 194–217, 2019.
[20] A. Mokhtari, M. Eisen, A. Ribeiro, IQN: an incremental quasi-Newton method with local superlinear convergence rate. SIAM Journal on optimization, 28(2), 1670–1698, 2018.
[21] H. Yabe, N. Yamaki, Local and superlinear convergence of structured Quasi-Newton methods for nonlinear optimization. Journal of the Operations Research Society of Japan, 39(4), 541–557, 1996.
[22] A. Rodomanov, Y. Nesterov, Greedy Quasi-Newton methods with explicit superlinear convergence. SIAM Journal on optimization, 31(1), 785–811, 2021.
[23] D. Lin, H. Ye, Z. Zhang, Explicit convergence rates of greedy and random Quasi-Newton methods. The Journal of Machine Learning Research, 23(1), 7272–7311, 2022.
[24] A. Rodomanov, Y. Nesterov, Rates of superlinear convergence for classical Quasi-Newton methods. Mathematical Programming, 1–32, 2022.
[25] H. Ye, D. Lin, X. Chang, Z. Zhang, Towards explicit superlinear convergence rate for SR1. Mathematical Programming, 199(1): 1273–1303, 2023.
[26] Q. J. Jin, A. Mokhtari, Non-asymptotic superlinear convergence of standard quasi-Newton methods. Mathematical Programming, 200.1, 425–473, 2023.
[27] Z. Y. Ji, Y. H. Dai, Greedy PSB methods with explicit superlinear convergence. Computational Optimization and Applications, 85, 753 – 786, 2023.
[28] R. H. Byrd, H. F. Khalfan, R. B. Schnabel, Analysis of a symmetric rank-one trust region method. SIAM Journal on optimization, 6, 1025–1039, 1996.
[29] J. Nocedal, S. J. Wright, Numerical Optimization, New York, 1999.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Highlights in Science, Engineering and Technology
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
