Document Zbl 1417.49037

A new diagonal quasi-Newton updating method with scaled forward finite differences directional derivative for unconstrained optimization. (English) Zbl 1417.49037

Numer. Funct. Anal. Optim. 40, No. 13, 1467-1488 (2019).

Summary: A new diagonal quasi-Newton updating algorithm for unconstrained optimization is presented. The elements of the diagonal matrix approximating the Hessian are determined as scaled forward finite differences directional derivatives of the components of the gradient. Under mild classical assumptions, the convergence of the algorithm is proved to be linear. Numerical experiments with 80 unconstrained optimization test problems, of different structures and complexities, as well as five applications from MINPACK-2 collection prove that the suggested algorithm is more efficient and more robust

-: than the quasi-Newton diagonal algorithm retaining only the diagonal elements of the BFGS update,
-: than the weak quasi-Newton diagonal algorithm,
-: than the quasi-Cauchy diagonal algorithm,
-: than the diagonal approximation of the Hessian by the least-change secant updating strategy and minimizing the trace of the matrix,
-: than the Cauchy with Oren and Luenberger scaling algorithm in its complementary form (i.e. the Barzilai-Borwein algorithm),
-: than the steepest descent algorithm, and
-: than the classical BFGS algorithm.

However, our algorithm is inferior to the limited memory BFGS algorithm (L-BFGS).

Cited in 3 Documents

MSC:

49M15	Newton-type methods
65K05	Numerical mathematical programming methods
90C30	Nonlinear programming

Keywords:

diagonal quasi-Newton updating; directional derivatives; global convergence; numerical comparisons; unconstrained optimization

Software:

CUTE; L-BFGS; CUTEr; KELLEY; MINPACK-2; tn

Cite Review PDF

Full Text: DOI

References:

[1]	Davidon, W. C., Variable Metric Method for Minimization. Technical Report ANL-5990 (Revised) (1959), Argonne, IL: Argonne National Laboratory, Argonne, IL
[2]	Broyden, C. G., The convergence of a class of double-rank minimization algorithms. I. General considerations, IMA J. Appl. Math, 6, 1, 76-90 (1970) · Zbl 0223.65023 · doi:10.1093/imamat/6.1.76
[3]	Fletcher, R., A new approach to variable metric algorithms, Comput. J, 13, 3, 317-322 (1970) · Zbl 0207.17402 · doi:10.1093/comjnl/13.3.317
[4]	Goldfarb, D., A family of variable metric method derived by variation mean, Math. Comp, 23, 23-26 (1970) · Zbl 0196.18002 · doi:10.1090/S0025-5718-1970-0258249-6
[5]	Shanno, D. F., Conditioning of quasi-Newton methods for function minimization, Math. Comp, 24, 111, 647-656 (1970) · Zbl 0225.65073 · doi:10.1090/S0025-5718-1970-0274029-X
[6]	Powell, M. J. D.; Rosen, J. B.; Mangasarian, O. L.; Ritter, K., Nonlinear Programming, A new algorithm for unconstrained optimization, 31-66 (1970), New York: Academic Press, New York
[7]	Dennis, J. E.; Moré, J. J., A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp, 28, 126, 549-560 (1974) · Zbl 0282.65042 · doi:10.1090/S0025-5718-1974-0343581-1
[8]	Dennis, J. E.; Moré, J. J., Quasi-Newton methods, motivation and theory, SIAM Rev, 19, 46-89 (1977) · Zbl 0356.65041 · doi:10.1137/1019005
[9]	Dennis, J. E., Schnabel, R. B. (1981). A new derivation of symmetric positive definite secant updates. In: Mangasarian, O. L., Meyer, R. R., Robinson, S. M., eds. Nonlinear Programming 4. Proceedings of the Nonlinear Programming Symposium 4 Conducted by the Computer Sciences Department at the University of Wisconsin-Madison, July 14-16, 1980. New York, NY: Academic Press, pp. 167-199.
[10]	Fletcher, R., Practical Methods of Optimization 1, Unconstrained Optimization (1987), New York: Wiley, New York · Zbl 0905.65002
[11]	Gill, P. E.; Murray, W.; Wright, M. H., Practical Optimization (1981), London: Academic Press, London · Zbl 0503.90062
[12]	Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice Hall Series in Computational Mathematics (1983), Englewood Cliffs, NJ: Prentice Hall, Englewood Cliffs, NJ · Zbl 0579.65058
[13]	Nocedal, J., Theory of algorithms for unconstrained optimization, Acta Numer, 1, 1-37 (1992) · doi:10.1017/S0962492900002270
[14]	Luenberger, D. G., Introduction to Linear and Nonlinear Programming (1973), Reading, Massachusetts: Addison-Wesley Publishing Company, Reading, Massachusetts · Zbl 0297.90044
[15]	Bertsekas, D. P., Nonlinear Programming (1995), Belmont, MA: Athena Scientific, Belmont, MA · Zbl 0935.90037
[16]	Kelley, C. T., Iterative Methods for Optimization (1999), Philadelphia: SIAM, Philadelphia · Zbl 0934.90082
[17]	Nocedal, J.; Wright, S. J., Numerical Optimization (2006), Springer Science + Business Media · Zbl 1104.65059
[18]	Andrei, N., Continuous Nonlinear Optimization for Engineering Applications in GAMS Technology. Springer Optimization and Its Applications 121 (2017), Berlin: Springer, Berlin · Zbl 1395.90001
[19]	Liu, D. C.; Nocedal, J., On the limited-memory BFGS method for large scale optimization, Mathematical Programming, 45, 1-3, 503-528 (1989) · Zbl 0696.90048 · doi:10.1007/BF01589116
[20]	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
[21]	Nash, S. G., Preconditioning of truncated-Newton methods, SIAM J. Sci. Stat. Comput, 6, 3, 599-616 (1985) · Zbl 0592.65038 · doi:10.1137/0906042
[22]	Wolfe, P., Convergence conditions for ascent methods, SIAM Rev, 11, 2, 226-235 (1969) · Zbl 0177.20603 · doi:10.1137/1011036
[23]	Wolfe, P., Convergence conditions for ascent methods. II: Some corrections, SIAM Rev, 13, 2, 185-188 (1971) · Zbl 0216.26901 · doi:10.1137/1013035
[24]	Nazareth, J. L., If Quasi-Newton then why not Quasi-Cauchy? Endif, SIAG/Opt Views-and News, 6, 11-14 (1995)
[25]	Dennis, J. E.; Wolkowicz, H., Sizing and least-change secant methods, SIAM J. Numer. Anal, 30, 5, 1291-1314 (1993) · Zbl 0802.65081 · doi:10.1137/0730067
[26]	Zhu, M.; Nazareth, J. L.; Wolkowicz, H., The quasi-Cauchy relation and diagonal updating, SIAM J. Optim, 9, 4, 1192-1204 (1999) · Zbl 1013.90137 · doi:10.1137/S1052623498331793
[27]	Leong, W. J.; Farid, M.; Hassan, M. A., Improved Hessian approximation with modified quasi-Cauchy relation for a gradient-type method, AMO-Adv Model Optim, 12, 1, 37-44 (2010) · Zbl 1332.90346
[28]	Leong, W. J.; Farid, M.; Hassan, M. A., Scaling on diagonal quasi-Newton update for large-scale unconstrained optimization, Bull. Malays. Math. Sci. Soc, 35, 2, 247-256 (2012) · Zbl 1246.65092
[29]	Farid, M.; Leong, W. J.; 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 1254.90226 · doi:10.1155/2012/875494
[30]	Andrei, N., A diagonal quasi-Newton updating method for unconstrained optimization, Numer. Algorithms (2018) · Zbl 1416.49025 · doi:10.1007/s11075-018-0562-7
[31]	Andrei, N., A diagonal quasi-Newton updating method based on minimizing the measure function of Byrd and Nocedal for unconstrained optimization, Optimization, 67, 9, 1553-1568 (2018) · Zbl 1402.65049 · doi:10.1080/02331934.2018.1482298
[32]	Cauchy, A., Méthodes générales pour la esolution des systémes déquations simultanées, C.R. Acad. Sci. Par, 25, 536-538 (1848)
[33]	Luenberger, D. G., Linear and Nonlinear Programming (1994), Reading, MA: Addison-Wesley, Reading, MA
[34]	Barzilai, J.; Borwein, J. M., Two point step size gradient methods, IMA J. Numer. Anal, 8, 1, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[35]	Gill, P. E.; Murray, W., Conjugate Gradient Methods for Large-scale Nonlinear Optimization. Technical Report SOL 79-15 (1979), Stanford, CA: Department of Operations Research, Stanford University, Stanford, CA
[36]	Gilbert, J. C.; Lemaréchal, C., Some numerical experiments with variable-storage quasi-Newton algorithms, Math. Prog. Ser. B, 45, 1-3, 407-435 (1989) · Zbl 0694.90086 · doi:10.1007/BF01589113
[37]	Andrei, N. (2018). UOP—A Collection of 80 Unconstrained Optimization Test Problems. ICI Technical Report No. 7/2018, November 17. Bucharest, Romania: Research Institute for Informatics.
[38]	Averick, B. M.; Carter, R. G.; Moré, J. J.; Xue, G., The MINPACK-2 Test Problem Collection. Preprint MCS-P153-0692, Mathematics and Computer Science Division (1992), Argonne, IL: Argonne National Laboratory
[39]	Kelley, C. T., Iterative Methods for Linear and Nonlinear Equations (1995), Philadelphia: SIAM, Philadelphia · Zbl 0832.65046
[40]	Luenberger, D. G.; Ye, Y., Linear and Nonlinear Programming (2016), New York: Springer. International Series in Operations Research & Management Science, New York · Zbl 1319.90001
[41]	Bongartz, I.; Conn, A. R.; Gould, N. I. M.; Toint, P. L., CUTE: Constrained and unconstrained testing environments, ACM Trans. Math. Softw, 21, 1, 123-160 (1995) · Zbl 0886.65058 · doi:10.1145/200979.201043
[42]	Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Prog, 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[43]	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
[44]	Andrei, N., An acceleration of gradient descent algorithm with backtracking for unconstrained optimization, Numer. Algor, 42, 1, 63-73 (2006) · Zbl 1101.65058 · doi:10.1007/s11075-006-9023-9

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.