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

Martínez, José Mario

doi:10.1090/S0025-5718-1992-1136223-X

On the relation between two local convergence theories of least-change secant update methods
HTML articles powered by AMS MathViewer

by José Mario Martínez PDF

Math. Comp. 59 (1992), 457-481 Request permission

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.

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

A new double-rank minimization algorithm

16

C. G. Broyden, The convergence of an algorithm for solving sparse nonlinear systems, Math. Comp. 25 (1971), 285–294. MR 297122, DOI 10.1090/S0025-5718-1971-0297122-5
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

Sparse quasi-Newton methods and the continuation problem

Thomas F. Coleman and Jorge J. Moré, Estimation of sparse Jacobian matrices and graph coloring problems, SIAM J. Numer. Anal. 20 (1983), no. 1, 187–209. MR 687376, DOI 10.1137/0720013

On the estimation of sparse Jacobian matrices

13

Variable metric methods for minimization

J. E. Dennis Jr., Toward a unified convergence theory for Newton-like methods, Nonlinear Functional Anal. and Appl. (Proc. Advanced Sem., Math. Res. Center, Univ. of Wisconsin, Madison, Wis., 1970) Academic Press, New York, 1971, pp. 425–472. MR 0278556

An adaptive nonlinear least-squares algorithm

7

J. E. Dennis Jr. and Guang Ye Li, A hybrid algorithm for solving sparse nonlinear systems of equations, Math. Comp. 50 (1988), no. 181, 155–166. MR 917823, DOI 10.1090/S0025-5718-1988-0917823-5
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
J. E. Dennis Jr. and R. B. Schnabel, Least change secant updates for quasi-Newton methods, SIAM Rev. 21 (1979), no. 4, 443–459. MR 545880, DOI 10.1137/1021091
John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
J. E. Dennis Jr. and Homer F. Walker, Convergence theorems for least-change secant update methods, SIAM J. Numer. Anal. 18 (1981), no. 6, 949–987. MR 638993, DOI 10.1137/0718067

A new approach to variable metric algorithms

13

R. Fletcher and M. J. D. Powell, A rapidly convergent descent method for minimization, Comput. J. 6 (1963/64), 163–168. MR 152116, DOI 10.1093/comjnl/6.2.163
Donald Goldfarb, A family of variable-metric methods derived by variational means, Math. Comp. 24 (1970), 23–26. MR 258249, DOI 10.1090/S0025-5718-1970-0258249-6
J. Greenstadt, Variations on variable-metric methods. (With discussion), Math. Comp. 24 (1970), 1–22. MR 258248, DOI 10.1090/S0025-5718-1970-0258248-4
A. Griewank and Ph. L. Toint, On the unconstrained optimization of partially separable functions, Nonlinear optimization, 1981 (Cambridge, 1981) NATO Conf. Ser. II: Systems Sci., Academic Press, London, 1982, pp. 301–312. MR 775354
A. Griewank and Ph. L. Toint, Partitioned variable metric updates for large structured optimization problems, Numer. Math. 39 (1982), no. 1, 119–137. MR 664541, DOI 10.1007/BF01399316
A. Griewank and Ph. L. Toint, Local convergence analysis for partitioned quasi-Newton updates, Numer. Math. 39 (1982), no. 3, 429–448. MR 678746, DOI 10.1007/BF01407874
A. Griewank and Ph. L. Toint, Numerical experiments with partially separable optimization problems, Numerical analysis (Dundee, 1983) Lecture Notes in Math., vol. 1066, Springer, Berlin, 1984, pp. 203–220. MR 760465, DOI 10.1007/BFb0099526

Quasi-Newton methods for discretized nonlinear boundary problems

11

George W. Johnson and Nieves H. Austria, A quasi-Newton method employing direct secant updates of matrix factorizations, SIAM J. Numer. Anal. 20 (1983), no. 2, 315–325. MR 694521, DOI 10.1137/0720021
C. T. Kelley and E. W. Sachs, A quasi-Newton method for elliptic boundary value problems, SIAM J. Numer. Anal. 24 (1987), no. 3, 516–531. MR 888748, DOI 10.1137/0724037
José Mario Martínez, A family of quasi-Newton methods for nonlinear equations with direct secant updates of matrix factorizations, SIAM J. Numer. Anal. 27 (1990), no. 4, 1034–1049. MR 1051122, DOI 10.1137/0727061
José Mario Martínez, Local convergence theory of inexact Newton methods based on structured least change updates, Math. Comp. 55 (1990), no. 191, 143–167. MR 1023050, DOI 10.1090/S0025-5718-1990-1023050-5

Exploiting sparsity in Newton-type methods

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 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
L. K. Schubert, Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 258276, DOI 10.1090/S0025-5718-1970-0258276-9
D. F. Shanno, Conditioning of quasi-Newton methods for function minimization, Math. Comp. 24 (1970), 647–656. MR 274029, DOI 10.1090/S0025-5718-1970-0274029-X
Ph. L. Toint, On sparse and symmetric matrix updating subject to a linear equation, Math. Comp. 31 (1977), no. 140, 954–961. MR 455338, DOI 10.1090/S0025-5718-1977-0455338-4
Ph. L. Toint, Numerical solution of large sets of algebraic nonlinear equations, Math. Comp. 46 (1986), no. 173, 175–189. MR 815839, DOI 10.1090/S0025-5718-1986-0815839-9