×

A perfect example for the BFGS method. (English) Zbl 1262.49040

Summary: Consider the BFGS quasi-Newton method applied to a general non-convex function that has continuous second derivatives. This paper aims to construct a four-dimensional example such that the BFGS method need not converge. The example is perfect in the following sense: (a) All the stepsizes are exactly equal to one; the unit stepsize can also be accepted by various line searches including the Wolfe line search and the Arjimo line search; (b) The objective function is strongly convex along each search direction although it is not in itself. The unit stepsize is the unique minimizer of each line search function. Hence the example also applies to the global line search and the line search that always picks the first local minimizer; (c) The objective function is polynomial and hence is infinitely continuously differentiable. If relaxing the convexity requirement of the line search function, namely (b), we are able to construct a relatively simple polynomial example.

MSC:

49M37 Numerical methods based on nonlinear programming
49M15 Newton-type methods
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Byrd R.H., Nocedal J., Yuan Y.X.: Global convergence of a class of quasi-Newton methods on convex problems. SIAM J. Numer. Anal. 24, 1171-1190 (1987) · Zbl 0657.65083 · doi:10.1137/0724077
[2] Broyden, C.G.: The convergence of a class of double rank minimization algorithms: 2. The new algorithm. J. Inst. Math. Appl. 6, 222-231 (1970) · Zbl 0207.17401 · doi:10.1093/imamat/6.3.222
[3] Dai Y.H.: Convergence properties of the BFGS algorithm. SIAM J. Optim. 13(3), 693-701 (2002) · Zbl 1036.65052 · doi:10.1137/S1052623401383455
[4] Davidon W.C.: Variable metric methods for minimization. SIAM J. Optim. 1, 1-17 (1991) · Zbl 0752.90062 · doi:10.1137/0801001
[5] Dennis J.E., Moré J.J.: Quasi-Newton method, motivation and theory. SIAM Rev. 19, 46-89 (1977) · Zbl 0356.65041 · doi:10.1137/1019005
[6] Fletcher R.: A new approach to variable metric algorithms. Comput. J. 13, 317-322 (1970) · Zbl 0207.17402 · doi:10.1093/comjnl/13.3.317
[7] Fletcher, R.; Spedicato, E. (ed.), An Overview of Unconstrained Optimization, 109-143 (1994), Dordrecht · Zbl 0828.90123 · doi:10.1007/978-94-009-0369-2_5
[8] Fletcher R., Powell M.J.D.: A rapidly convergent descent method for minimization. Comput. J. 6, 163-168 (1963) · Zbl 0132.11603 · doi:10.1093/comjnl/6.2.163
[9] Goldfarb D.: A family of variable metric methods derived by variational means. Math. Comp. 24, 23-26 (1970) · Zbl 0196.18002 · doi:10.1090/S0025-5718-1970-0258249-6
[10] Lasserre J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796-817 (2001) · Zbl 1010.90061 · doi:10.1137/S1052623400366802
[11] Li D.H., Fukushima M.: On the global convergence of the BFGS method for nonconvex unconstrained optimization problems. SIAM J. Optim. 11, 1054-1064 (2001) · Zbl 1010.90079 · doi:10.1137/S1052623499354242
[12] Mascarenhas W.F.: The BFGS algorithm with exact line searches fails for nonconvex functions. Math. Program. 99(1), 49-61 (2004) · Zbl 1082.90108 · doi:10.1007/s10107-003-0421-7
[13] Nocedal J.: Theory of algorithms for unconstrained optimization. Acta Numer. 1, 199-242 (1992) · Zbl 0766.65051 · doi:10.1017/S0962492900002270
[14] Powell M.J.D.: On the convergence of the variable metric algorithm. J. Inst. Math. Appl. 7, 21-36 (1971) · Zbl 0217.52804 · doi:10.1093/imamat/7.1.21
[15] Powell, M. J.D.; Cottle, R. W. (ed.); Lemke, C. E. (ed.), Some global convergence properties of a variable metric algorithm for minimization without exact line searches, 53-72 (1976), Philadelphia
[16] Powell, M. J.D.; Griffiths, D. F. (ed.), Nonconvex minimization calculations and the conjugate gradient method, 122-141 (1984), Berlin
[17] Powell M.J.D.: On the convergence of the DFP algorithm for unconstrained optimization when there are only two variables. Math. Program. Ser. B 87, 281-301 (2000) · Zbl 0964.65068 · doi:10.1007/s101070050115
[18] Shanno D.F.: Conditioning of quasi-Newton methods for function minimization. Math. Comp. 24, 647-650 (1970) · Zbl 0225.65073 · doi:10.1090/S0025-5718-1970-0274029-X
[19] Shor N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1-11 (1987) · Zbl 0655.90055
[20] Sun W.Y., Yuan Y.X.: Optimization Theory and Methods: Nonlinear Programming. Springer, New York (2006) · Zbl 1129.90002
[21] Yuan, Y.X.: Numerical Methods for Nonlinear Programming. Shanghai Scientific and Technical Publishers, Shanghai (1993); (in Chinese)
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.