Spectral scaling BFGS method. (English) Zbl 1198.90355
Summary: In this paper, we scale the quasiNewton equation and propose a spectral scaling BFGS method. The method has a good selfcorrecting property and can improve the behavior of the BFGS method. Compared with the standard BFGS method, the single-step convergence rate of the spectral scaling BFGS method will not be inferior to that of the steepest descent method when minimizing an \(n\)-dimensional quadratic function. In addition, when the method with exact line search is applied to minimize an \(n\)-dimensional strictly convex function, it terminates within \(n\) steps. Under appropriate conditions, we show that the spectral scaling BFGS method with Wolfe line search is globally and R-linear convergent for uniformly convex optimization problems. The reported numerical results show that the spectral scaling BFGS method outperforms the standard BFGS method.
References:
| [1] | Gill, P.E., Leonard, M.W.: Reduced-Hessian quasiNewton methods for unconstrained optimization. SIAM J. Optim. 12, 209–237 (2001) · Zbl 1003.65068 · doi:10.1137/S1052623400307950 |
| [2] | Oren, S.S., Luenberger, D.G.: Self-scaling variables metric (SSVM) algorithms, part I: criteria and sufficient conditions for scaling a class of algorithms. Manage. Sci. 20, 845–862 (1974) · Zbl 0316.90064 · doi:10.1287/mnsc.20.5.845 |
| [3] | Oren, S.S.: Self-scaling variable metric algorithm, part II: implementation and experiments. Manage. Sci. 20, 863–874 (1974) · Zbl 0316.90065 · doi:10.1287/mnsc.20.5.863 |
| [4] | Nocedal, J., Yuan, Y.: Analysis of a selfscaling quasiNewton method. Math. Program. 61, 19–37 (1993) · Zbl 0794.90067 · doi:10.1007/BF01582136 |
| [5] | Al-Baali, M.: Analysis of a family of selfscaling quasiNewton methods. Technical Report, Department of Mathematics and Computer Science, United Arab Emirates University (1993) |
| [6] | Al-Baali, M.: Global and superlinear convergence of a class of selfscaling methods with inexact line searches. Comput. Optim. Appl. 9, 191–203 (1998) · Zbl 0904.90127 · doi:10.1023/A:1018315205474 |
| [7] | Al-Baali, M.: Numerical experience with a class of selfscaling quasiNewton algorithms. J. Optim. Theory Appl. 96, 533–553 (1998) · Zbl 0907.90240 · doi:10.1023/A:1022608410710 |
| [8] | Yuan, Y.: A modified BFGS algorithm for unconstrained optimization. IMA J. Numer. Anal. 11, 325–332 (1991) · Zbl 0733.65039 · doi:10.1093/imanum/11.3.325 |
| [9] | Bard, Y.: On a numerical instability of Davidon-like methods. Math. Comput. 22, 665–666 (1968) · Zbl 0165.50303 · doi:10.1090/S0025-5718-1968-0232533-5 |
| [10] | Barzilai, J., Borwein, J.M.: Two-point step size gradient method. IMA J. Numer. Anal. 8, 141–148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141 |
| [11] | Bryden, C.G.: Quasi-Newton methods and their application to function minimization. Math. Comput. 21, 368–381 (1967) · Zbl 0155.46704 · doi:10.1090/S0025-5718-1967-0224273-2 |
| [12] | Loewner, C.: Advanced matrix theory. Lecture Notes, Standford University, Winter (1957) |
| [13] | Luenberger, D.G.: Introduction to Linear and Nonlinear Programming. Addison-Wesley, Reading (1973) · Zbl 0297.90044 |
| [14] | Dixon, L.C.W.: Variable metric algorithms: necessary and sufficient conditions for identical behavior of nonquadratic functions. J. Optim. Theory Appl. 10, 34–40 (1972) · Zbl 0226.49014 · doi:10.1007/BF00934961 |
| [15] | Byrd, R.H., Nocedal, J.: A tool for the analysis of quasiNewton methods with application to unconstrained optimization. SIAM J. Numer. Anal. 26, 727–739 (1989) · Zbl 0676.65061 · doi:10.1137/0726042 |
| [16] | Byrd, R.H., Liu, D.C., Nocedal, J.: Global convergence of a class of quasiNewton methods on convex problems. SIAM J. Numer. Anal. 24, 1171–1190 (1987) · Zbl 0657.65083 · doi:10.1137/0724077 |
| [17] | Powell, M.J.D.: Updating conjugate directions by the BFGS formula. Math. Program. 38, 693–726 (1987) · Zbl 0642.90086 · doi:10.1007/BF02591850 |
| [18] | Zhang, J.Z., Xu, C.X.: Properties and numerical performance of quasiNewton methods with modified quasiNewton equations. J. Comput. Appl. Math. 137, 269–278 (2001) · Zbl 1001.65065 · doi:10.1016/S0377-0427(00)00713-5 |
| [19] | Xu, C.X., Zhang, J.Z.: A survey of quasiNewton equations and quasiNewton methods for optimization. Ann. Oper. Res. 103, 213–234 (2001) · Zbl 1007.90069 · doi:10.1023/A:1012959223138 |
| [20] | Moré, J.J., Thuente, D.J.: Line search algorithms with guaranteed sufficient decrease. ACM Trans. Math. Softw. 20, 286–307 (1994) · Zbl 0888.65072 · doi:10.1145/192115.192132 |
| [21] | Bongartz, I., Conn, A.R., Gould, N.I.M., Toint, P.I.: CUTE: constrained and unconstrained testing environments. ACM Trans. Math. Softw. 21, 123–160 (1995) · Zbl 0886.65058 · doi:10.1145/200979.201043 |
| [22] | 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 |
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.
