Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

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.

References [Enhancements On Off] (What's this?)

  • 1. C.G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comput., 19 (1965), 577-593. MR 0198670 (33:6825)
  • 2. C.G. Broyden, J.E. Dennis and Jr. J.J. Moré, On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl., 12 (1973), 223-246. MR 0341853 (49:6599)
  • 3. R. Byrd and J. Nocedal, A tool for analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. Numer. Anal., 26 (1989), 727-739. MR 997665 (90f:90116)
  • 4. R. Byrd, J. Nocedal and Y.X. Yuan, Global convergence of a class of quasi-Newton methods on convex problems, SIAM J. Numer. Anal., 24 (1987), 1171-1190. MR 909072 (88m:65100)
  • 5. Y. Dai, Convergence properties of the BFGS algorithm, SIAM J. Optim., 13 (2002), 693-701. MR 1972211 (2004b:90164)
  • 6. J.E. Dennis and Jr. J.J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comput., 28 (1974), 549-560. MR 0343581 (49:8322)
  • 7. J.E. Dennis and Jr. J.J. Moré, Quasi-Newton method, motivation and theory, SIAM Rev., 19 (1977), 46-89. MR 0445812 (56:4146)
  • 8. J.E. Dennis and R.B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice-Hall, Englewood Cliffs, N.F., 1983. MR 702023 (85j:65001)
  • 9. L.C.W. Dixon, Variable metric algorithms: necessary and sufficient conditions for identical behavior on nonquadratic functions, J. Optim. Theory Appl., 10 (1972) 34-40. MR 0309305 (46:8415)
  • 10. A. Griewank, The ``global'' convergence of Broyden-like methods with a suitable line search, J. Austral. Math. Soc., Ser. B, 28 (1986), 75-92. MR 846784 (87k:65064)
  • 11. A. Griewank, The global convergence of partitioned BFGS on problems with convex decompositions and Lipschitzian gradients, Math. Program., 50 (1991), 141-175. MR 1103931 (92d:90079)
  • 12. G.Z. Gu, D.H. Li, L. Qi and S.Z. Zhou, Descent directions of quasi-Newton method for symmetric nonlinear equations, SIAM J. Numer. Anal., 40 (2002), 1763-1774. MR 1950621 (2003m:65082)
  • 13. A.N. Iusem and M.V. Solodov, Newton-type methods with generalized distances for constrained optimization, Optimization, 41 (1997), 257-278. MR 1473401 (98h:90078)
  • 14. T.G. Kolda, D.P. O'Leary and L. Nazareth, BFGS with update skipping and varying memory, SIAM J. Optim., 8 (1998), 1060-1083. MR 1646119 (99e:90092)
  • 15. D.H. Li and M. Fukushima, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods and Softw., 13 (2000), 181-201. MR 1785195 (2001e:90146)
  • 16. D.H. Li and M. Fukushima, A globally and superlinearly convergent Gauss-Newton-based BFGS method for symmetric nonlinear equations, SIAM J. Numer. Anal., 37 (1999), 152-172. MR 1742754 (2000k:65100)
  • 17. D.H. Li and M. Fukushima, On the global convergence of the BFGS method for nonconvex unconstrained optimization problems, SIAM J. Optim., 11 (2001), 1054-1064. MR 1855221 (2002f:90168)
  • 18. D.H. Li and M. Fukushima, A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math., 129 (2001), 15-35. MR 1823208 (2002b:90130)
  • 19. J. Nocedal, Updating quasi-Newton matrices with limited storage, Math. Comput., 35 (1980), 773-782. MR 572855 (81g:65077)
  • 20. J.M. Ortega and W.C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, 1970. MR 0273810 (42:8686)
  • 21. M.J.D. Powell, On the convergence of the variable metric algorithm, J. Inst. Math. Appl., 7 (1971), 21-36. MR 0279977 (43:5698)
  • 22. 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, SIAM, Philadelphia, PA, (1976) 53-72. MR 0426428 (54:14371)
  • 23. M.V. Solodov and B.F. Svaiter, A globally convergent inexact Newton method for systems of monotone equations, in: M. Fukushima, L. Qi (Eds.), Reformulation: Nonsmooth, Piecewise smooth, Semismooth and Smoothing Methods, Kluwer Academic Publishers, (1998) 355-369. MR 1682755 (2000d:65089)
  • 24. Ph.L. Toint, Global convergence of the partitioned BFGS algorithm for convex partially separable optimization, Math. Program., 36 (1986), 290-306. MR 866412 (88a:90160)
  • 25. E. Zeidler, Nonlinear functional analysis and its applications, II/B: Nonlinear monotone operators, Springer-Verlag, 1990. MR 1033498 (91b:47002)
  • 26. Y. Zhang and R.P. Tewarson, Quasi-Newton algorithm with updates from the preconvex part of Broyden's family, IMA J. Numer. Anal., 8 (1988), 487-509. MR 975609 (90f:65098)
  • 27. Y.B. Zhao and D. Li, Monotonicity of fixed point and normal mapping associated with variational inequality and its application, SIAM J. Optim., 4 (2001), 962-973. MR 1855216 (2003a:90070)

Similar Articles

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

Dong-Hui Li
Affiliation: College of Mathematics and Econometrics, Hunan University, Changsha 410082, China

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.

American Mathematical Society