×
Zhou, Wei-Jun; Li, Dong-Hui

A globally convergent BFGS method for nonlinear monotone equations without any merit functions. (English) Zbl 1203.90180

Math. Comput. 77, No. 264, 2231-2240 (2008).
Summary: Since 1965, there has been significant progress in the theoretical study on quasi-Newton methods for solving nonlinear equations, especially in the local convergence analysis. However, the study on global convergence of quasi-Newton methods is relatively fewer, especially for the BFGS method. To ensure global convergence, some merit function such as the squared norm merit function is typically used.
We propose an algorithm for solving nonlinear monotone equations, which combines the BFGS method and the hyperplane projection method. We also prove that the proposed BFGS method converges globally if the equation is monotone and Lipschitz continuous without differentiability requirement on the equation, which makes it possible to solve some nonsmooth equations. An attractive property of the proposed method is that its global convergence is independent of any merit function.We also report some numerical results to show efficiency of the proposed method.

Cited in 56 Documents

MSC:

90C53 Methods of quasi-Newton type

Keywords:

BFGS method; monotone equation; hyperplane projection method; global convergence

Software:

L-BFGS
PDF BibTeX XML Cite
\textit{W.-J. Zhou} and \textit{D.-H. Li}, Math. Comput. 77, No. 264, 2231--2240 (2008; Zbl 1203.90180)
Full Text: DOI

References:

[1] C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comp. 19 (1965), 577 – 593. · Zbl 0131.13905
[2] C. G. Broyden, J. E. Dennis Jr., and Jorge J. Moré, On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl. 12 (1973), 223 – 245. · Zbl 0282.65041
[3] Richard H. Byrd and Jorge Nocedal, A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. Numer. Anal. 26 (1989), no. 3, 727 – 739. · Zbl 0676.65061
[4] Richard H. Byrd, Jorge Nocedal, and Ya Xiang Yuan, Global convergence of a class of quasi-Newton methods on convex problems, SIAM J. Numer. Anal. 24 (1987), no. 5, 1171 – 1190. · Zbl 0657.65083
[5] Yu-Hong Dai, Convergence properties of the BFGS algorithm, SIAM J. Optim. 13 (2002), no. 3, 693 – 701 (2003). · Zbl 1036.65052
[6] J. E. Dennis Jr. and Jorge J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549 – 560. · Zbl 0282.65042
[7] J. E. Dennis Jr. and Jorge J. Moré, Quasi-Newton methods, motivation and theory, SIAM Rev. 19 (1977), no. 1, 46 – 89. · Zbl 0356.65041
[8] John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. · Zbl 0579.65058
[9] L. C. W. Dixon, Variable metric algorithms: necessary and sufficient conditions for identical behavior of nonquadratic functions, J. Optimization Theory Appl. 10 (1972), 34 – 40. · Zbl 0226.49014
[10] Andreas Griewank, The ”global” convergence of Broyden-like methods with a suitable line search, J. Austral. Math. Soc. Ser. B 28 (1986), no. 1, 75 – 92. · Zbl 0596.65034
[11] Andreas Griewank, The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients, Math. Programming 50 (1991), no. 2, (Ser. A), 141 – 175. · Zbl 0736.90068
[12] Guang-Ze Gu, Dong-Hui Li, Liqun Qi, and Shu-Zi Zhou, Descent directions of quasi-Newton methods for symmetric nonlinear equations, SIAM J. Numer. Anal. 40 (2002), no. 5, 1763 – 1774. · Zbl 1047.65032
[13] Alfredo N. Iusem and Michael V. Solodov, Newton-type methods with generalized distances for constrained optimization, Optimization 41 (1997), no. 3, 257 – 278. · Zbl 0905.49015
[14] Tamara G. Kolda, Dianne P. O’Leary, and Larry Nazareth, BFGS with update skipping and varying memory, SIAM J. Optim. 8 (1998), no. 4, 1060 – 1083. · Zbl 0918.65044
[15] Dong-Hui Li and Masao Fukushima, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods Softw. 13 (2000), no. 3, 181 – 201. · Zbl 0960.65076
[16] Donghui Li and Masao Fukushima, A globally and superlinearly convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations, SIAM J. Numer. Anal. 37 (1999), no. 1, 152 – 172. · Zbl 0946.65031
[17] Dong-Hui Li and Masao Fukushima, On the global convergence of the BFGS method for nonconvex unconstrained optimization problems, SIAM J. Optim. 11 (2001), no. 4, 1054 – 1064. · Zbl 1010.90079
[18] Dong-Hui Li and Masao Fukushima, A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math. 129 (2001), no. 1-2, 15 – 35. Nonlinear programming and variational inequalities (Kowloon, 1998). · Zbl 0984.65055
[19] Jorge Nocedal, Updating quasi-Newton matrices with limited storage, Math. Comp. 35 (1980), no. 151, 773 – 782. · Zbl 0464.65037
[20] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. · Zbl 0241.65046
[21] M. J. D. Powell, On the convergence of the variable metric algorithm, J. Inst. Math. Appl. 7 (1971), 21 – 36. · Zbl 0217.52804
[22] M. J. D. Powell, Some global convergence properties of a variable metric algorithm for minimization without exact line searches, Nonlinear programming (Proc. Sympos., New York, 1975) Amer. Math. Soc., Providence, R. I., 1976, pp. 53 – 72. SIAM-AMS Proc., Vol. IX.
[23] Michael V. Solodov and Benav F. Svaiter, A globally convergent inexact Newton method for systems of monotone equations, Reformulation: nonsmooth, piecewise smooth, semismooth and smoothing methods (Lausanne, 1997) Appl. Optim., vol. 22, Kluwer Acad. Publ., Dordrecht, 1999, pp. 355 – 369. · Zbl 0928.65059
[24] Ph. L. Toint, Global convergence of the partitioned BFGS algorithm for convex partially separable optimization, Math. Programming 36 (1986), no. 3, 290 – 306. · Zbl 0626.90076
[25] Eberhard Zeidler, Nonlinear functional analysis and its applications. II/B, Springer-Verlag, New York, 1990. Nonlinear monotone operators; Translated from the German by the author and Leo F. Boron. · Zbl 0684.47029
[26] Yin Zhang and R. P. Tewarson, Quasi-Newton algorithms with updates from the preconvex part of Broyden’s family, IMA J. Numer. Anal. 8 (1988), no. 4, 487 – 509. · Zbl 0661.65061
[27] Yun-Bin Zhao and Duan Li, Monotonicity of fixed point and normal mappings associated with variational inequality and its application, SIAM J. Optim. 11 (2001), no. 4, 962 – 973. · Zbl 1010.90084
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.