I am wondering whether their is any general proof of the convergence of the Broyden's update matrix. Broyden (1965) discovered a new method for solving nonlinear systems of equations by replacing the Jacobian matrix in Newton's method with an approximate matrix (Broyden's matrix) that can be updated in each iteration.
Dennis and More (1974) gives the characterization of the superlinear convergence of quasi-Newton's method based on the convergences of the sequence generated by quasi-Newton's iterates. There is an assumption for the convergence of the approximate matrix, but to the best of my ability I can't find any attempt in showing that the Broyden's matrix converges to the true jacobian at the solution.
Please I need expert suggestions/answer to my question.
This is a good question with more than one answer.
A good place to start is
D.G. Mohr, Hybrid Runga-Kutta and Quasi-Newton Methods for Unconstrained Nonlinear Optimization, Abstract for a Ph.D. thesis, University of Iowa, 2011:
http://homepage.math.uiowa.edu/~ljay/publications.dir/DarinMohrPhDthesis.pdf
See Section 1.1.3, starting on page 19 for definitions. See, also, Section 2.2.4, starting on page 61, for convergence of the one order method.
A local quasi-Newton framework is given in
M. Wagner, M.J. Todd, Least-change quasi-Newton updates for equality-constrained optimization, Math. Programming, 2000:
http://ecommons.cornell.edu/bitstream/1813/9121/1/TR001238.pdf
See Algorithm 1, p. 5 for the framework. Then see super linear convergence, starting on page 7.
you obviously mean the general case for a system F(x)=0 , F with F smooth from R^n
to R^n. Yes, there is a proof of convergence, but it is purely local: x_0 must be near to
a solution x* with a nonsingular Jacobian and A_0 must be near to to J_F(x*).
I remeber to have read it in the book of Ortega and Rheinboldt on solving systems of nonlinear equations (Acad. Press 1970) but I am not completely sure about this .
I know of no global proof, but there is a proof of convergence for a linear (yes!) F
of global type, however 2n steps requiring.
In the symmetric case (optimization) there is much more known.
Perhaps you may also want to have a look at these references
- R.H. Byrd and J. Nocedal, "A tool for the analysis of quasi-Newton methods with application to unconstrained minimization," SIAM Journal on Numerical Analysis 26 (1989) 727-739.
- R.H. Byrd, D.C. Liu and J. Nocedal, "On the behavior of Broyden's class of quasi-newton methods," Report No. NAM 01, Department of Electrical Engineering and Computer Science, Northwestern University (Evanston, IL, 1990).
- Badges
- Science topic
- Similar topics
- Mathematics