On the global convergence of Broyden’s method

Moré, J. J.; Trangenstein, J. A.

doi:10.1090/S0025-5718-1976-0418451-2

On the global convergence of Broyden’s method
HTML articles powered by AMS MathViewer

by J. J. Moré and J. A. Trangenstein PDF

Math. Comp. 30 (1976), 523-540 Request permission

Abstract:

We consider Broyden’s 1965 method for solving nonlinear equations. If the mapping is linear, then a simple modification of this method guarantees global and Q-superlinear convergence. For nonlinear mappings it is shown that the hybrid strategy for nonlinear equations due to Powell leads to R-superlinear convergence provided the search directions form a uniformly linearly independent sequence. We then explore this last concept and its connection with Broyden’s method. Finally, we point out how the above results extend to Powell’s symmetric version of Broyden’s method.

References

C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comp. 19 (1965), 577–593. MR 198670, DOI 10.1090/S0025-5718-1965-0198670-6
C. G. Broyden, The convergence of single-rank quasi-Newton methods, Math. Comp. 24 (1970), 365–382. MR 279993, DOI 10.1090/S0025-5718-1970-0279993-0
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 341853, DOI 10.1093/imamat/12.3.223
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 343581, DOI 10.1090/S0025-5718-1974-0343581-1

Quasi-Newton Methods, Motivation and Theory

P. E. Gill and W. Murray, Quasi-Newton methods for unconstrained optimization, J. Inst. Math. Appl. 9 (1972), 91–108. MR 300410, DOI 10.1093/imamat/9.1.91
J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
M. J. D. Powell, A hybrid method for nonlinear equations, Numerical methods for nonlinear algebraic equations (Proc. Conf., Univ. Essex, Colchester, 1969) Gordon and Breach, London, 1970, pp. 87–114. MR 0343589
M. J. D. Powell, A hybrid method for nonlinear equations, Numerical methods for nonlinear algebraic equations (Proc. Conf., Univ. Essex, Colchester, 1969) Gordon and Breach, London, 1970, pp. 87–114. MR 0343589
M. J. D. Powell, A new algorithm for unconstrained optimization, Nonlinear Programming (Proc. Sympos., Univ. of Wisconsin, Madison, Wis., 1970) Academic Press, New York, 1970, pp. 31–65. MR 0272162

A FORTRAN Subroutine for Unconstrained Minimization, Requiring First Derivatives of the Objective Function

M. J. D. Powell, Convergence properties of a class of minimization algorithms, Nonlinear programming, 2 (Proc. Special Interest Group on Math. Programming Sympos., Univ. Wisconsin, Madison, Wis., 1974) Academic Press, New York, 1974, pp. 1–27. MR 0386270
H. Schwetlick, Über die Realisierung und Konvergenz von Mehrschrittverfahren zur iterativen Lösung nichtlinearer Gleichungen, Z. Angew. Math. Mech. 54 (1974), 479–493 (German, with English and Russian summaries). MR 378397, DOI 10.1002/zamm.19740540704

Sequential Estimation Techniques for Quasi-Newton Algorithms