|
A globally convergent BFGS method for nonlinear monotone equations without any merit functions
Author(s):
Wei-Jun
Zhou;
Dong-Hui
Li.
Journal:
Math. Comp.
77
(2008),
2231-2240.
MSC (2000):
Primary 90C53
Posted:
May 19, 2008
Retrieve article in:
PDF DVI PostScript
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:
-
- 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
Email:
weijunzhou@126.com
Dong-Hui
Li
Affiliation:
College of Mathematics and Econometrics, Hunan University, Changsha 410082, China
Email:
dhli@hnu.cn
DOI:
10.1090/S0025-5718-08-02121-2
PII:
S 0025-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
Posted:
May 19, 2008
Additional Notes:
This work was supported by the NSF (10771057 and 10701018) of China.
Copyright of article:
Copyright
2008,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
Comments: webmaster@ams.org