×

A limited memory BFGS-type method for large-scale unconstrained optimization. (English) Zbl 1155.90441

Summary: A new numerical method for solving large-scale unconstrained optimization problems is presented. It is derived from a modified BFGS-type update formula by Wei, Li, and Qi. It is observed that the update formula can be extended to the framework of limited memory scheme with hardly more storage or arithmetic operations. Under some suitable conditions, the global convergence property is established. The implementations of the method on a set of CUTE problems indicate that this extension is beneficial to the performance of the algorithm.

MSC:

90C26 Nonconvex programming, global optimization
90C53 Methods of quasi-Newton type

Software:

L-BFGS; tn
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Nash, S.G., A survey of truncated-Newton methods, J. comput. appl. math., 124, 45-59, (2000) · Zbl 0969.65054
[2] Dembo, R.; Steihaug, T., Truncated-Newton algorithms for large-scale unconstrained optimization, Math. program., 26, 190-212, (1983) · Zbl 0523.90078
[3] Liu, D.; Nocedal, J., On the limited memory BFGS method for large-scale optimization, Math. program., 45, 503-528, (1989) · Zbl 0696.90048
[4] Nocedal, J., Updating quasi-Newton matrices with limited storage, Math. comput., 35, 773-782, (1980) · Zbl 0464.65037
[5] Hager, W.W.; Zhang, H., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. optim., 16, 170-192, (2005) · Zbl 1093.90085
[6] Gilbert, J.C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM J. optim., 2, 21-42, (1992) · Zbl 0767.90082
[7] Zhang, L.; Zhou, W.; Li, D.H., Global convergence of a modified fletcher – reeves conjugate gradient method with Armijo-type line search, Numer. math., 104, 561-572, (2006) · Zbl 1103.65074
[8] Zhang, L.; Zhou, W.; Li, D.H., A descent modified polak – ribière – polyak conjugate gradient method and its global convergence, IMA J. numer. anal., 26, 629-640, (2006) · Zbl 1106.65056
[9] Hager, W.W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pacific J. optim., 2, 35-58, (2006) · Zbl 1117.90048
[10] Gould, N.I.M.; Orban, D.; Toint, Ph.L., Numerical methods for large-scale nonlinear optimization, Acta numer., 14, 299-361, (2005) · Zbl 1119.65337
[11] Nocedal, J., Large scale unconstrained optimization, (1997), Duff and Watson, pp. 311-338 · Zbl 0881.65055
[12] Wei, Z.; Yu, G.; Yuan, G.; Lian, Z., The superlinear convergence of a modified BFGS-type method for unconstrained optimization, Comput. optim. appl., 29, 315-332, (2004) · Zbl 1070.90089
[13] Zhang, J.Z.; Deng, N.Y.; Chen, L.H., New quasi-Newton equation and related methods for unconstrained optimization, J. optim. theory appl., 102, 147-167, (1999) · Zbl 0991.90135
[14] Wei, Z.; Li, G.; Qi, L., New quasi-Newton methods for unconstrained optimization problems, Appl. math. comput., 175, 1156-1188, (2006) · Zbl 1100.65054
[15] Broyden, C.G.; Dennis, J.E.; Moré, J.J., On the local and superlinear convergence of quasi-Newton methods, J. inst. math. appl., 12, 223-246, (1973) · Zbl 0282.65041
[16] Byrd, R.H.; Nocedal, J., A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. numer. anal., 26, 727-739, (1989) · Zbl 0676.65061
[17] Byrd, R.H.; Nocedal, J.; Yuan, Y., Global convergence of a class of quasi-Newton methods on convex problems, SIAM J. numer. anal., 24, 1171-1189, (1987) · Zbl 0657.65083
[18] Dai, Y.H., Convergence properties of the BFGS algorithm, SIAM J. optim., 13, 693-701, (2002) · Zbl 1036.65052
[19] Mascarenhas, W.F., The BFGS method with exact line search fails for non-convex objective functions, Math. program., 99, 49-61, (2004) · Zbl 1082.90108
[20] Li, D.H.; Fukushima, M., A modified BFGS method and its global convergence in nonconvex minimization, J. comput. appl. math., 129, 15-35, (2001) · Zbl 0984.65055
[21] Li, D.H.; Fukushima, M., On the global convergence of the BFGS methods for nonconvex unconstrained optimization problems, SIAM J. optim., 11, (2001), 1054-164 · Zbl 1010.90079
[22] Conn, A.R.; Gouldc, N.I.M.; Toint, Ph.L., CUTE: constrained and unconstrained testing environment, ACM trans. math. softw., 21, 123-160, (1995) · Zbl 0886.65058
[23] Dolan, E.D.; Moré, J.J., Benchmarking optimization software with performance profiles, Math. program., 91, 201-213, (2002) · Zbl 1049.90004
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.