×

zbMATH — the first resource for mathematics

Diagonal approximation of the Hessian by finite differences for unconstrained optimization. (English) Zbl 1441.49029
Summary: A new quasi-Newton method with a diagonal updating matrix is suggested, where the diagonal elements are determined by forward or by central finite differences. The search direction is a direction of sufficient descent. The algorithm is equipped with an acceleration scheme. The convergence of the algorithm is linear. The preliminary computational experiments use a set of 75 unconstrained optimization test problems classified in five groups according to the structure of their Hessian: diagonal, block-diagonal, band (tri- or penta-diagonal), sparse and dense. Subject to the CPU time metric, intensive numerical experiments show that, for problems with Hessian in a diagonal, block-diagonal or band structure, the algorithm with diagonal approximation of the Hessian by finite differences is top performer versus the well-established algorithms: the steepest descent and the Broyden-Fletcher-Goldfarb-Shanno. On the other hand, as a by-product of this numerical study, we show that the Broyden-Fletcher-Goldfarb-Shanno algorithm is faster for problems with sparse Hessian, followed by problems with dense Hessian.
MSC:
49M15 Newton-type methods
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
Software:
L-BFGS; CUTE ; CUTEr; OPTIMA; tn
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Dennis, JE Jr; Moré, JJ, A characterization of superlinear convergence and its application to quasi-Newton methods, Mathematics of Computation, 28, 549-560 (1974) · Zbl 0282.65042
[2] Dennis, JE Jr; Moré, JJ, Quasi-Newton methods, motivation and theory, SIAM Review, 19, 46-89 (1977) · Zbl 0356.65041
[3] Nocedal, J., Theory of algorithms for unconstrained optimization, Acta Numerica, 1, 199-242 (1992) · Zbl 0766.65051
[4] Dennis, JE Jr; Schnabel, RB, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Englewood Cliffs, NJ: Prentice-Hall, Inc., Englewood Cliffs, NJ
[5] Gill, PE; Murray, W.; Wright, MH, Practical Optimization (1981), London: Academic Press, London
[6] Nocedal, J.; Wright, SJ, Numerical Optimization (2006), Berlin: Springer, Berlin
[7] Bartholomew-Biggs, M., Nonlinear Optimization with Engineering Applications. Springer Optimization and Its Applications (2008), Berlin: Springer, Berlin · Zbl 1167.90001
[8] Andrei, N., Continuous Nonlinear Optimization for Engineering Applications in GAMS Technology. Springer Optimization and Its Applications (2017), Berlin: Springer, Berlin · Zbl 1395.90001
[9] Nazareth, JL, If quasi-Newton then why not quasi-Cauchy?, SIAG/Opt Views-and-news, 6, 11-14 (1995)
[10] Dennis, JE; Wolkowicz, H., Sizing and least-change secant methods, SIAM J. Numerical Analysis, 30, 1291-1314 (1993) · Zbl 0802.65081
[11] Zhu, M.; Nazareth, JL; Wolkowicz, H., The quasi-Cauchy relation and diagonal updating, SIAM J. Optim., 9, 4, 1192-1204 (1999) · Zbl 1013.90137
[12] Leong, WJ; Farid, M.; Hassan, MA, Improved Hessian approximation with modified quasi-Cauchy relation for a gradient-type method, Adv. Model. Optim., 12, 1, 37-44 (2010) · Zbl 1332.90346
[13] Farid, M.; Leong, WJ; Zheng, L., A new diagonal gradient-type method for large scale unconstrained optimization, U.P.B. Sci. Bull. Ser. A, 75, 1, 57-64 (2013) · Zbl 1299.65118
[14] Andrei, N., A diagonal quasi-Newton updating method for unconstrained optimization, Numerical Algorithms, 81, 575-590 (2019) · Zbl 1416.49025
[15] Wolfe, P., Convergence conditions for ascent methods, SIAM Review, 11, 226-235 (1969) · Zbl 0177.20603
[16] Wolfe, P., Convergence conditions for ascent methods. II: some corrections, SIAM Rev., 13, 185-188 (1971) · Zbl 0216.26901
[17] Andrei, N., An acceleration of gradient descent algorithm with backtracking for unconstrained optimization, Numerical Algorithms, 42, 63-73 (2006) · Zbl 1101.65058
[18] Andrei, N., Acceleration of conjugate gradient algorithms for unconstrained optimization, Appl. Math. Comput., 213, 361-369 (2009) · Zbl 1172.65027
[19] Kelley, CT, Iterative Methods for Linear and Nonlinear Equations (1995), Philadelphia: SIAM, Philadelphia
[20] Zoutendijk, G.; Abadie, J., Nonlinear programming, computational methods, Integer and Nonlinear Programming, 37-86 (1970), Amsterdam: North-Holland, Amsterdam
[21] Ortega, JM; Rheinboldt, WC, Iterative Solution of Nonlinear Equations in Several Variables (1970), London: Academic Press, London
[22] Luenberger, DG; Ye, Y., Linear and Nonlinear Programming (2016), New York: Springer, New York
[23] Nash, SG; Nocedal, J., A numerical study of the limited memory BFGS method and the truncated-Newton method for large scale optimization, SIAM J. Optimization, 1, 3, 358-372 (1991) · Zbl 0756.65091
[24] Liu, DC; Nocedal, J., On the limited memory BFGS method for large scale optimization, Math. Programming, 45, 503-528 (1989) · Zbl 0696.90048
[25] Nash, S.G.: User’s Guide for TN/TNBC: Fortran Routines for Nonlinear Optimization. Report 397, Mathematical Sciences Department, The Johns Hopkins University, Baltimore (1984)
[26] Nash, SG, Preconditioning of truncated-Newton methods, SIAM J. Sci. Statist. Comput., 6, 599-616 (1985) · Zbl 0592.65038
[27] Bongartz, I.; Conn, AR; Gould, NIM; Toint, PL, CUTE: constrained and unconstrained testing environments, ACM TOMS, 21, 123-160 (1995) · Zbl 0886.65058
[28] Andrei, N.: A Collection of 75 Unconstrained Optimization Test Problems. Technical Report No. 6/2018, May 10, 2018, pp. 1-9. Research Institute for Informatics, Bucharest (2018)
[29] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004
[30] Gill, P.E., Murray, W.: Conjugate Gradient Methods for Large-Scale Nonlinear Optimization. Technical Report SOL 79-15, Department of Operations Research, Stanford University, Stanford (1979)
[31] Gilbert, JC; Lemaréchal, C., Some numerical experiments with variable-storage quasi-Newton algorithms, Math. Programming Ser. B, 45, 407-435 (1989) · Zbl 0694.90086
[32] Nazareth, J.L.: The Newton-Cauchy Framework: A Unified Approach to Unconstrained Nonlinear Minimization. Lecture Notes in Computer Science 769. Springer, New York (1994) · Zbl 0891.65067
[33] Dennis, J.E., Walker, H.F.: Inaccuracy in quasi-Newton methods: local improvement theorems. In: Mathematical Programming Study, Vol. 22: Mathematical Programming at Oberwolfach II, pp. 70-85. North-Holland, Amsterdam (1984) · Zbl 0566.65038
[34] Ypma, TJ, The effect of rounding errors on Newton-like methods, IMA J. Numer. Anal., 3, 109-118 (1983) · Zbl 0519.65026
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.