On the relation between two local convergence theories of least-change secant update methods

Author:
José Mario Martínez

Journal:
Math. Comp. **59** (1992), 457-481

MSC:
Primary 65K10; Secondary 65H10

DOI:
https://doi.org/10.1090/S0025-5718-1992-1136223-X

MathSciNet review:
1136223

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we show that the main results of the local convergence theory for least-change secant update methods of Dennis and Walker (SIAM J. Numer. Anal. **18** (1981), 949-987) can be proved using the theory introduced recently by Martinez (Math. Comp. **55** (1990), 143-167). In addition, we exhibit two generalizations of well-known methods whose local convergence can be easily proved using Martínez's theory.

**[1]**C. G. Broyden,*A class of methods for solving nonlinear simultaneous equations*, Math. Comp.**19**(1965), 577-593. MR**0198670 (33:6825)****[2]**-,*A new double-rank minimization algorithm*, Notices Amer. Math. Soc.**16**(1969), 670.**[3]**-,*The convergence of an algorithm for solving sparse nonlinear systems*, Math. Comp.**25**(1971), 285-294. MR**0297122 (45:6180)****[4]**C. G. Broyden, J. E. Dennis, and J. J. Moré,*On the local and superlinear convergence of quasi-Newton methods*, J. Inst. Math. Appl.**12**(1973), 223-245. MR**0341853 (49:6599)****[5]**F. F. Chadee,*Sparse quasi-Newton methods and the continuation problem*, TR SOL No. 85-8, Dept. of Operations Research, Stanford University, 1985.**[6]**T. F. Coleman and J. J. Moré,*Estimation of sparse Jacobian matrices and graph coloring problems*, SIAM J. Numer. Anal.**8**(1983), 639-655. MR**687376 (84f:05043)****[7]**A. M. Curtis, M. J. D. Powell, and J. K. Reid,*On the estimation of sparse Jacobian matrices*, J. Inst. Math. Appl.**13**(1974), 117-120.**[8]**W. C. Davidon,*Variable metric methods for minimization*, Argonne National Laboratory Report ANL-5990, 1959.**[9]**J. E. Dennis, Jr.,*Toward a unified convergence theory for Newton-like methods*, Nonlinear Functional Analysis and Applications (L. B. Rall, ed.), Academic Press, New York, 1971, pp. 425-472. MR**0278556 (43:4286)****[10]**J. E. Dennis, Jr., D. M. Gay, and R. E. Welsch,*An adaptive nonlinear least-squares algorithm*, ACM Trans. Math. Software**7**(1981), 348-368.**[11]**J. E. Dennis, Jr. and G. Li,*A hybrid algorithm for solving sparse nonlinear systems of equations*, Math. Comp.**50**(1988), 155-166. MR**917823 (88m:65080)****[12]**J. E. Dennis, Jr. and J. J. Moré,*A characterization of superlinear convergence and its application to quasi-Newton methods*. Math. Comp.**28**(1974), 549-560. MR**0343581 (49:8322)****[13]**J. E. Dennis, Jr. and R. B. Schnabel,*Least change secant updates for quasi-Newton methods*, SIAM Rev.**21**(1979), 443-459. MR**545880 (80j:65021)****[14]**-,*Numerical methods for unconstrained optimization and nonlinear equations*, Prentice-Hall, Englewood Cliffs, NJ, 1983. MR**702023 (85j:65001)****[15]**J. E. Dennis, Jr. and H. F. Walker,*Convergence theorems for least-change secant update methods*, SIAM J. Numer. Anal.**18**(1981), 949-987. MR**638993 (83a:65052a)****[16]**R. Fletcher,*A new approach to variable metric algorithms*, Comput. J.**13**(1970), 317-322.**[17]**R. Fletcher and M. J. D. Powell,*A rapidly convergent descent method for minimization*, Comput. J.**6**(1963), 163-168. MR**0152116 (27:2096)****[18]**D. Goldfarb,*A family of variable metric methods derived by variational means*, Math. Comp.**24**(1970), 23-26. MR**0258249 (41:2896)****[19]**J. L. Greenstadt,*Variations on variable metric methods*, Math. Comp.**24**(1970), 1-22. MR**0258248 (41:2895)****[20]**A. Griewank and Ph. L. Toint,*On the unconstrained optimization of partially separable functions*, Nonlinear Optimization 1981 (M. J. D. Powell, ed.), Academic Press, New York, 1982. MR**775354****[21]**-,*Partitioned variable metric for large structured optimization problems*, Numer. Math.**39**(1982), 119-137. MR**664541 (83k:65054)****[22]**-,*Local convergence analysis for partitioned quasi-Newton updates*, Numer. Math.**39**(1982), 429-448. MR**678746 (84b:65062)****[23]**-,*Numerical experiments with partially separable optimization problems*, Numerical Analysis Proceedings, Dundee 1983 (D. F. Griffiths, ed.), Lecture Notes in Math., vol. 1066, Springer-Verlag, Berlin, 1984, pp. 203-220. MR**760465 (85h:90102)****[24]**W. E. Hart and S. O. W. Soul,*Quasi-Newton methods for discretized nonlinear boundary problems*, J. Inst. Math. Appl.**11**(1973), 351-359.**[25]**G. W. Johnson and N. H. Austria,*A quasi-Newton method employing direct secant updates of matrix factorizations*, SIAM J. Numer. Anal.**20**(1983), 315-325. MR**694521 (84g:65069)****[26]**C. T. Kelley and E. W. Sachs,*A quasi-Newton method for elliptic boundary value problems*, SIAM J. Numer. Anal.**24**(1987), 516-531. MR**888748 (88h:65121)****[27]**J. M. Martinez,*A family of quasi-Newton methods for nonlinear equations with direct secant updates of matrix factorizations*, SIAM J. Numer. Anal.**27**(1990), 1034-1049. MR**1051122 (91h:65084)****[28]**-,*Local convergence theory of inexact Newton methods based on structured least change updates*, Math. Comp.**55**(1990), 143-167. MR**1023050 (90m:65108)****[29]**E. S. Marwil,*Exploiting sparsity in Newton-type methods*, Cornell Applied Mathematics Ph.D. Thesis, Cornell University, Ithaca, NY, 1978.**[30]**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York, 1970. MR**0273810 (42:8686)****[31]**M. J. D. Powell,*A new algorithm for unconstrained optimization*, Nonlinear Programming (J. B. Rosen, O. L. Mangasarian, and K. Ritter, eds.), Academic Press, New York, 1970, pp. 31-65. MR**0272162 (42:7043)****[32]**L. K. Schubert,*Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian*, Math. Comp.**24**(1970), 27-30. MR**0258276 (41:2923)****[33]**D. F. Shanno,*Conditioning of quasi-Newton methods for function minimization*, Math. Comp.**24**(1970), 647-657. MR**0274029 (42:8905)****[34]**Ph. L. Toint,*On sparse and symmetric matrix updating subject to a linear equation*, Math. Comp.**31**(1977), 954-961. MR**0455338 (56:13577)****[35]**-,*Numerical solution of large sets of algebraic nonlinear equations*, Math. Comp.**46**(1986), 175-189. MR**815839 (87d:65064)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65K10,
65H10

Retrieve articles in all journals with MSC: 65K10, 65H10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1992-1136223-X

Keywords:
Nonlinear systems,
quasi-Newton methods,
secant methods,
least-change secant update methods

Article copyright:
© Copyright 1992
American Mathematical Society