×

The global and superlinear convergence of a new nonmonotone MBFGS algorithm on convex objective functions. (English) Zbl 1152.65068

This article extends two existing papers, namely one by J. Han and G. Liu [Comput. Optim. Appl. 7, No. 3, 277–289 (1997; Zbl 0876.90072)] and one by Z. Wei, G. Yu, G. Yuan and Z. Lian [Comput. Optim. Appl. 29, No. 3, 315–332 (2004; Zbl 1070.90089)], these could have been cited properly to shorten the discussed work.
As in the latter reference the authors introduce a slightly modified Broyden-Fletcher-Goldfarb-Shanno (BFGS) formula (MBFGS) for the solution of unconstrained optimization problems, but instead of the more standard Wolfe-type line-search a “GLL” line search is used. This on the other hand has been studied with the standard BFGS formula in the primer reference. The steps to prove global convergence are taken from this paper nearly unchanged, so are the lemmas from Wei et al. [loc. cit.] for proving superlinear convergence.
The paper ends with numerical comparisons on a test-set where one can see that the difference between the “nonmonotone” MBFGS, the Wolfe-MBFGS and also the “nonmonotone” standard BFGS is negligible.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C53 Methods of quasi-Newton type

Software:

minpack; ve08
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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-1190 (1987) · Zbl 0657.65083
[2] Dennis, J. E.; Moré, J. J., Quasi-Newton methods, motivation and theory, SIAM Rev., 19, 46-89 (1977) · Zbl 0356.65041
[3] Griewank, A.; Toint, P. L., Local convergence analysis for partitioned quasi-Newton updates, Numer. Math., 39, 429-448 (1982) · Zbl 0505.65018
[4] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone linesearch technique for Newton’s methods, SIAM J. Numer. Anal., 23, 707-716 (1986) · Zbl 0616.65067
[5] Guanghui, L.; Jimen, P., The convergence properties of a sort of nonmonotonic algorithm, J. Comput. Math., 1, 65-71 (1992)
[6] Guanghui, L.; Jiye, H., Global convergence of the variable metric algorithms with a generalized Wolfe linesearch (1993), Technical Report: Technical Report No. 029, Institute of Applied Mathematics, Academia Sinica, Beijing, China
[7] Guanghui, L.; Jiye, H.; Defeng, S., Global convergence of BFGS algorithm with nonmonotone linesearch, Optimization, 34, 147-159 (1995)
[8] L. Guanghui, P. Jimen, A unified model of a variety of nonmonotonic linesearches, OR Decision Marking 1 616-618.; L. Guanghui, P. Jimen, A unified model of a variety of nonmonotonic linesearches, OR Decision Marking 1 616-618.
[9] H. Jiye, L. Guanghui, General form of stepsize selection rule of linesearch and relevant analysis of global convergence of BFGS algorithm, Acta Math. Sinica (1992), to appear.; H. Jiye, L. Guanghui, General form of stepsize selection rule of linesearch and relevant analysis of global convergence of BFGS algorithm, Acta Math. Sinica (1992), to appear. · Zbl 0858.90119
[10] Jiye, H.; Guanghui, L., Notes on the general form of stepsize selection, OR and Decision Marking, 1, 619-624 (1992)
[11] Jiye, H.; Guanghui, L., Global convergence analysis of a new nonmonotone BFGS algorithm on convex objective function, J. Comput. Optim. Appl., 7, 277-289 (1997) · Zbl 0876.90072
[12] More, J. J.; Garbow, B. S.; Hillstrome, K. E., Testing unconstrained optimization software, ACM Trans. Math. Software, 7, 17-41 (1981) · Zbl 0454.65049
[13] Powell, M. J.D., On the convergence of the variable metric algorithm, J. Inst. Math. Appl., 7, 21-36 (1971) · Zbl 0217.52804
[14] Powell, M. J.D., Some properties of the variable metric algorithm, (Lootsman, F. A., Numerical Methods for Nonlinear Optimization (1972), Academia Press: Academia Press London) · Zbl 0288.65036
[15] M.J.D. Powell, Some global convergence properties of a variable metric algorithm for minimization without exact line searches, in: R.W. Cottle, C.E. Lemke, (Eds.), Nonlinear Programming, SIAM-AMS Proceedings, Vol. IX, American Mathematical Society, Providence, RI 1976, pp. 53-72.; M.J.D. Powell, Some global convergence properties of a variable metric algorithm for minimization without exact line searches, in: R.W. Cottle, C.E. Lemke, (Eds.), Nonlinear Programming, SIAM-AMS Proceedings, Vol. IX, American Mathematical Society, Providence, RI 1976, pp. 53-72. · Zbl 0338.65038
[16] Wei, Z.; Yu, G.; Yuan, G.; Lian, Zh., The superlinear convergence of a modified BFGS-type method for unconstrained optimization, Comput. Optim. Appl., 29, 315-332 (2004) · Zbl 1070.90089
[17] Werner, J., Uber die globale konvergenze von variable-metric verfahren mit nichtexakter schrittweitenbestimmung, Numer. Math., 31, 321-334 (1978) · Zbl 0427.65047
[18] Zhang, Y.; Tewarson, P. R., Quasi-Newton algorithm with updates from the preconvex part of Broyden’s family, SIAM J. Numer. Anal, 8, 487-509 (1988) · Zbl 0661.65061
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.