A globally convergent BFGS method for nonlinear monotone equations without any merit functions

Authors:
Wei-Jun Zhou and Dong-Hui Li

Journal:
Math. Comp. **77** (2008), 2231-2240

MSC (2000):
Primary 90C53

Published electronically:
May 19, 2008

MathSciNet review:
2429882

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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. In this paper, 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.

**1.**C. G. Broyden,*A class of methods for solving nonlinear simultaneous equations*, Math. Comp.**19**(1965), 577–593. MR**0198670**, 10.1090/S0025-5718-1965-0198670-6**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. MR**0341853****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. MR**997665**, 10.1137/0726042**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. MR**909072**, 10.1137/0724077**5.**Yu-Hong Dai,*Convergence properties of the BFGS algorithm*, SIAM J. Optim.**13**(2002), no. 3, 693–701 (2003). MR**1972211**, 10.1137/S1052623401383455**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. MR**0343581**, 10.1090/S0025-5718-1974-0343581-1**7.**J. E. Dennis Jr. and Jorge J. Moré,*Quasi-Newton methods, motivation and theory*, SIAM Rev.**19**(1977), no. 1, 46–89. MR**0445812****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. MR**702023****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. MR**0309305****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. MR**846784**, 10.1017/S0334270000005208**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. MR**1103931**, 10.1007/BF01594933**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. MR**1950621**, 10.1137/S0036142901397423**13.**Alfredo N. Iusem and Michael V. Solodov,*Newton-type methods with generalized distances for constrained optimization*, Optimization**41**(1997), no. 3, 257–278. MR**1473401**, 10.1080/02331939708844339**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 (electronic). MR**1646119**, 10.1137/S1052623496306450**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. MR**1785195**, 10.1080/10556780008805782**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 (electronic). MR**1742754**, 10.1137/S0036142998335704**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 (electronic). MR**1855221**, 10.1137/S1052623499354242**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). MR**1823208**, 10.1016/S0377-0427(00)00540-9**19.**Jorge Nocedal,*Updating quasi-Newton matrices with limited storage*, Math. Comp.**35**(1980), no. 151, 773–782. MR**572855**, 10.1090/S0025-5718-1980-0572855-7**20.**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810****21.**M. J. D. Powell,*On the convergence of the variable metric algorithm*, J. Inst. Math. Appl.**7**(1971), 21–36. MR**0279977****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. MR**0426428****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. MR**1682755**, 10.1007/978-1-4757-6388-1_18**24.**Ph. L. Toint,*Global convergence of the partitioned BFGS algorithm for convex partially separable optimization*, Math. Programming**36**(1986), no. 3, 290–306. MR**866412**, 10.1007/BF02592063**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. MR**1033498****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. MR**975609**, 10.1093/imanum/8.4.487**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 (electronic). MR**1855216**, 10.1137/S1052623499357957

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
90C53

Retrieve articles in all journals with MSC (2000): 90C53

Additional Information

**Wei-Jun Zhou**

Affiliation:
College of Mathematics and Computational Science, Changsha University of Science and Technology, Changsha 410076, China

Email:
weijunzhou@126.com

**Dong-Hui Li**

Affiliation:
College of Mathematics and Econometrics, Hunan University, Changsha 410082, China

Email:
dhli@hnu.cn

DOI:
https://doi.org/10.1090/S0025-5718-08-02121-2

Keywords:
BFGS method,
monotone equation,
hyperplane projection method,
global convergence.

Received by editor(s):
March 14, 2006

Received by editor(s) in revised form:
March 30, 2007

Published electronically:
May 19, 2008

Additional Notes:
This work was supported by the NSF (10771057 and 10701018) of China.

Article copyright:
© Copyright 2008
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.