Practical quasi-Newton methods for solving nonlinear systems. (English) Zbl 0967.65065
This is a survey of quasi-Newton methods for solving nonlinear systems. Special emphasis is given to methods that satisfy the secant equation at each iteration. The least-change secant update (LCSU) theory is revisited and convergence results for methods that do not belong to the LCSU family are discussed. The methods reviewed include Broyden’s methods, structured quasi-Newton methods, methods with direct updates of factorization, row-scaling methods and column-updating methods. At the end some implementation and practical aspects are discussed.
Reviewer: Plamen Yordanov Yalamov (Russe)
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
Keywords:
quasi-Newton method; nonlinear system; secant equation; Broyden’s method; convergence; row-scaling methods; column-updating methodsReferences:
| [1] | Aluffi-Pentini, F.; Parisi, V.; Zirilli, F., A differential equations algorithm for nonlinear equations, ACM Trans. Math. Software, 10, 299-316 (1984) · Zbl 0546.65034 |
| [2] | Aluffi-Pentini, F.; Parisi, V.; Zirilli, F., DAFNE: differential-equations algorithm for nonlinear equations, ACM Trans. Math. Software, 10, 317-324 (1984) |
| [3] | Ávila, J. H.; Concus, P., Update methods for highly structured systems of nonlinear equations, SIAM J. Numer. Anal., 16, 260-269 (1979) · Zbl 0405.65027 |
| [4] | Barnes, J. G.P., An algorithm for solving nonlinear equations based on the secant method, Comput. J., 8, 66-72 (1965) · Zbl 0254.65036 |
| [5] | Bittner, L., Eine Verallgemeinerung des Sekantenverfahrens zur näherungsweisen Berechnung der Nullstellen eines nichtlinearen Gleichngssystems, Will. Z. Tech. Univ. Dresden, 9, 325-329 (1959) |
| [6] | Bogle, I. D.L.; Perkins, J. D., A new sparsity preserving quasi-Newton update for solving nonlinear equations, SIAM J. Sci. Statist. Comput., 11, 621-630 (1990) · Zbl 0749.65033 |
| [7] | Brown, P. N.; Saad, Y., Convergence theory of nonlinear Newton-Krylov algorithms, SIAM J. Optim., 4, 297-330 (1994) · Zbl 0814.65048 |
| [8] | Broyden, C. G., A class of methods for solving nonlinear simultaneous equations, Math. Comput., 19, 577-593 (1965) · Zbl 0131.13905 |
| [9] | Broyden, C. G., Quasi-Newton methods and their applications to function minimization, Math. Comput., 21, 368-381 (1967) · Zbl 0155.46704 |
| [10] | Broyden, C. G., The convergence of an algorithm for solving sparse nonlinear systems, Math. Comp., 19, 577-593 (1971) · Zbl 0131.13905 |
| [11] | Broyden, C. G.; Dennis, J. E.; Moré, J. J., On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl., 12, 223-245 (1973) · Zbl 0282.65041 |
| [12] | Burdakov, O., Stable versions of the secant method for solving systems of equations, U.S.S.R. Comput. Math. Math. Phys., 23, 1-10 (1983) · Zbl 0561.65038 |
| [13] | Burdakov, O., On superlinear convergence of some stable variants of the secant method, Z. Angew. Math. Mech., 66, 615-622 (1986) · Zbl 0616.65055 |
| [14] | O. Burdakov, private communication, 1998.; O. Burdakov, private communication, 1998. |
| [15] | Calamai, P. H.; Moré, J. J., Quasi-Newton updates with bounds, SIAM J. Numer. Anal., 24, 1434-1441 (1987) · Zbl 0644.65033 |
| [16] | F.F. Chadee, Sparse quasi-Newton methods and the continuation problem, T.R.S.O.L.85-8, Department of Operations Research, Stanford University, 1985.; F.F. Chadee, Sparse quasi-Newton methods and the continuation problem, T.R.S.O.L.85-8, Department of Operations Research, Stanford University, 1985. |
| [17] | Coleman, T. F.; Garbow, B. S.; Moré, J. J., Software for estimating sparse Jacobian matrices, ACM Trans. Math. Software, 11, 363-378 (1984) · Zbl 0548.65006 |
| [18] | Coleman, T. F.; Moré, J. J., Estimation of sparse Jacobian matrices and graph coloring problems, SIAM J. Numer. Anal., 20, 187-209 (1983) · Zbl 0527.65033 |
| [19] | Conn, A. R.; Scheinberg, K.; Toint, Ph. L., Recent progress in unconstrained nonlinear optimization without derivatives, Math. Programming, 79, 397-414 (1997) · Zbl 0887.90154 |
| [20] | Curtis, A. R.; Powell, M. J.D.; Reid, J. K., On the estimation of sparse Jacobian matrices, J. Inst. Math. Appl., 13, 117-120 (1974) · Zbl 0273.65036 |
| [21] | Decker, D. W.; Kelley, C. T., Broyden’s method for a class of problems having singular Jacobian at the root, SIAM J. Numer. Anal., 22, 563-574 (1985) · Zbl 0583.65022 |
| [22] | Dembo, R. S.; Eisenstat, S. C.; Steihaug, T., Inexact Newton methods, SIAM J. Numer. Anal., 19, 400-408 (1982) · Zbl 0478.65030 |
| [23] | Dennis, J. E.; Marwil, E. S., Direct secant updates of matrix factorizations, Math. Comp., 38, 459-476 (1982) · Zbl 0482.65028 |
| [24] | Dennis, J. E.; Moré, J. J., A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28, 549-560 (1974) · Zbl 0282.65042 |
| [25] | Dennis, J. E.; Moré, J. J., Quasi-Newton methods, motivation and theory, SIAM Rev., 19, 46-89 (1977) · Zbl 0356.65041 |
| [26] | Dennis, J. E.; Schnabel, R. B., Least change secant updates for quasi-Newton methods, SIAM Rev., 21, 443-459 (1979) · Zbl 0424.65020 |
| [27] | Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0579.65058 |
| [28] | Dennis, J. E.; Morshedi, M.; Turner, K., A variable metric variant of the Karmarkar algorithm for linear programming, Math. Programming, 39, 1-20 (1987) · Zbl 0635.90058 |
| [29] | Dennis, J. E.; Walker, H. F., Convergence theorems for least-change secant update methods, SIAM J. Numer. Anal., 18, 949-987 (1981) · Zbl 0527.65032 |
| [30] | Deuflhard, P.; Freund, R.; Walter, A., Fast secant methods for the iterative solution of large nonsymmetric linear systems, Impact Comput. Sci. Eng., 2, 244-276 (1990) · Zbl 0729.65027 |
| [31] | L.C.W. Dixon, Automatic differentiation and parallel processing in optimisation, TR No. 180, The Hatfield Polytechnique, Hatfield, UK, 1987.; L.C.W. Dixon, Automatic differentiation and parallel processing in optimisation, TR No. 180, The Hatfield Polytechnique, Hatfield, UK, 1987. |
| [32] | Duff, I. S.; Erisman, A. M.; Reid, J. K., Direct Methods for Sparse Matrices (1989), Oxford Scientific Publications: Oxford Scientific Publications Oxford · Zbl 0666.65024 |
| [33] | Eisenstat, S. C.; Walker, H. F., Globally convergent inexact Newton methods, SIAM J. Optim., 4, 393-422 (1994) · Zbl 0814.65049 |
| [34] | Friedlander, A.; Gomes-Ruggiero, M. A.; Kozakevich, D. N.; Martı́nez, J. M.; Santos, S. A., Solving nonlinear systems of equations by means of quasi-Newton methods with a nonmonotone strategy, Optim. Methods Software, 8, 25-51 (1997) · Zbl 0893.65032 |
| [35] | Gay, D. M., Some convergence properties of Broyden’s method, SIAM J. Numer. Anal., 16, 623-630 (1979) · Zbl 0453.65034 |
| [36] | Gay, D. M.; Schnabel, R. B., Solving systems of nonlinear equations by Broyden’s method with projected updates, (Mangasarian, O.; Meyer, R.; Robinson, S., Nonlinear Programming 3 (pp. 245 281), Academic Press: Academic Press New York) · Zbl 0464.65024 |
| [37] | George, A.; Ng, E., Symbolic factorization for sparse Gaussian elimination with partial pivoting, SIAM J. Sci. Statist. Comput., 8, 877-898 (1987) · Zbl 0632.65021 |
| [38] | Golub, G. H.; Van Loan, Ch. F., Matrix Computations (1989), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore · Zbl 0733.65016 |
| [39] | Gomes-Ruggiero, M. A.; Martı́nez, J. M., The column-updating method for solving nonlinear equations in Hilbert space, Math. Modelling Numer. Anal., 26, 309-330 (1992) · Zbl 0752.65047 |
| [40] | Gomes-Ruggiero, M. A.; Kozakevich, D. N.; Martı́nez, J. M., A numerical study on large-scale nonlinear solvers, Comput. Math. Appl., 32, 1-13 (1996) · Zbl 0857.65059 |
| [41] | Gomes-Ruggiero, M. A.; Martı́nez, J. M.; Moretti, A. C., Comparing algorithms for solving sparse nonlinear systems of equations, SIAM J. Sci. Statist. Comput., 13, 459-483 (1992) · Zbl 0752.65039 |
| [42] | Gragg, W. B.; Stewart, G. W., A stable variant of the secant method for solving nonlinear equations, SIAM J. Numer. Anal., 13, 127-140 (1976) · Zbl 0359.65045 |
| [43] | Griewank, A., The solution of boundary value problems by Broyden based secant methods, (Noye, J.; May, R., Proceedings of the Computational Techniques and Applications Conference, CTAC-85 (1986), North-Holland: North-Holland Amsterdam) · Zbl 0622.65061 |
| [44] | Griewank, A., The ‘global’ convergence of Broyden-like methods with a suitable line search, J. Austral. Math. Soc. Ser. B, 28, 75-92 (1986) · Zbl 0596.65034 |
| [45] | Griewank, A., Achieving logarithmic growth of temporal and spacial complexity in reverse automatic differentiation, Optim. Methods Software, 1, 35-54 (1992) |
| [46] | Hart, W. E.; Soesianto, F., On the solution of highly structured nonlinear equations, J. Comput. Appl. Math., 40, 285-296 (1992) · Zbl 0755.65049 |
| [47] | Hart, W. E.; Soul, S. O.W., Quasi-Newton methods for discretized nonlinear boundary value problems, J. Inst. Math. Appl., 11, 351-359 (1973) · Zbl 0259.65074 |
| [48] | Z. Huang, E. Spedicato, Numerical testing of quasi-Newton and some other related methods for nonlinear systems, Quaderni del Dipartimento di Matematica, Statistica, Informatica e Applicazioni 4, Universitá degli Studi di Bergamo, Bergamo, Italy, 1994.; Z. Huang, E. Spedicato, Numerical testing of quasi-Newton and some other related methods for nonlinear systems, Quaderni del Dipartimento di Matematica, Statistica, Informatica e Applicazioni 4, Universitá degli Studi di Bergamo, Bergamo, Italy, 1994. |
| [49] | Ip, C. M.; Todd, M. J., Optimal conditioning and convergence in rank one quasi-Newton updates, SIAM J. Numer. Anal., 25, 206-221 (1988) · Zbl 0638.65041 |
| [50] | Iri, M., Simultaneous computations of functions, partial derivatives and estimates of rounding errors, Complexity and Practicality, Japan J. Appl. Math., 1, 223-252 (1984) · Zbl 0634.65009 |
| [51] | Jankowska, J., Theory of multivariate secant methods, SIAM J. Numer. Anal., 16, 547-562 (1979) · Zbl 0438.65049 |
| [52] | Johnson, G. W.; Austria, N. H., A quasi-Newton method employing direct secant updates of matrix factorizations, SIAM J. Numer. Anal., 20, 315-325 (1983) · Zbl 0533.65028 |
| [53] | Kaporin, I. E.; Axelsson, O., On a class of nonlinear equation solvers based on the residual norm over a sequence of affine subspaces, SIAM J. Sci. Comput., 16, 228-249 (1995) · Zbl 0826.65048 |
| [54] | Kedem, G., Automatic differentiation of computer programs, ACM Trans. Math. Software, 6, 150-165 (1980) · Zbl 0441.68041 |
| [55] | Kelley, C. T., Iterative Methods for Linear and Nonlinear Equations (1995), SIAM: SIAM Philadelphia, PA · Zbl 0832.65046 |
| [56] | Kelley, C. T.; Sachs, E. W., A quasi-Newton method for elliptic boundary value problems, SIAM J. Numer. Anal., 24, 516-531 (1987) · Zbl 0625.65104 |
| [57] | Li, D. H.; Fukushima, M., A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods Software, 13, 181-201 (2000) · Zbl 0960.65076 |
| [58] | Li, G., Successive column correction algorithms for solving sparse nonlinear systems of equations, Math. Programming, 43, 187-207 (1989) · Zbl 0675.65045 |
| [59] | Lopes, T. L.; Martı́nez, J. M., Combination of the sequential secant method and Broyden’s method with projected updates, Computing, 25, 379-386 (1980) · Zbl 0426.65017 |
| [60] | Lopes, V. L.R.; Martı́nez, J. M., Convergence properties of the inverse Column-Updating method, Optim. Methods Software, 6, 127-144 (1995) |
| [61] | Lucia, A., Partial molar excess properties, null spaces and a new update for the hybrid method of chemical process design, AICHE J., 31, 558-566 (1995) |
| [62] | Lucia, A.; Miller, D. C.; Kumar, A., Thermodynamically consistent quasi-Newton formulas, A.I.C.H.E. J., 31, 1381-1388 (1985) |
| [63] | Lukšan, L., Inexact trust region method for large sparse systems of nonlinear equations, J. Optim. Theory Appl., 81, 569-590 (1994) · Zbl 0803.65071 |
| [64] | Lukšan, L.; Vlček, J., Computational experience with globally convergent descent methods for large sparse systems of nonlinear equations, Optim. Methods Software, 8, 185-199 (1998) · Zbl 0927.65068 |
| [65] | Lužanin, Z.; Krejić, N.; Herceg, D., Parameter selection for Inexact Newton method, Nonlinear Anal. Theory Methods Appl., 30, 17-24 (1997) · Zbl 0890.65046 |
| [66] | Martı́nez, J. M., Three new algorithms based on the sequential secant method, BIT, 19, 236-243 (1979) · Zbl 0412.65027 |
| [67] | Martı́nez, J. M., On the order of convergence of Broyden-Gay-Schnabel’s method, Comment. Math. Univ. Carolin., 19, 107-118 (1979) · Zbl 0383.65029 |
| [68] | Martı́nez, J. M., A quasi-Newton method with a new updating for the LDU factorization of the approximate Jacobian, Mat. Apl. Comput., 2, 131-142 (1983) · Zbl 0521.65030 |
| [69] | Martı́nez, J. M., A quasi-Newton method with modification of one column per iteration, Computing, 33, 353-362 (1984) · Zbl 0546.90102 |
| [70] | Martı́nez, J. M., Quasi-Newton methods with factorization scaling for solving sparse nonlinear systems of equations, Computing, 38, 133-141 (1987) · Zbl 0592.65029 |
| [71] | Martı́nez, J. M., A family of quasi-Newton methods for nonlinear equations with direct secant updates of matrix factorizations, SIAM J. Numer. Anal., 27, 1034-1049 (1990) · Zbl 0702.65053 |
| [72] | Martı́nez, J. M., Local convergence theory of inexact Newton methods based on structured least change updates, Math. Comp., 55, 143-168 (1990) · Zbl 0707.65031 |
| [73] | Martı́nez, J. M., On the relation between two local convergence theories of least change secant update methods, Math. Comp., 59, 457-481 (1992) · Zbl 0767.65043 |
| [74] | Martı́nez, J. M., On the convergence of the Column-updating method, Comput. Appl. Math., 12, 83-94 (1992) · Zbl 0814.65051 |
| [75] | Martı́nez, J. M., Fixed-point quasi-Newton methods, SIAM J. Numer. Anal., 29, 1413-1434 (1992) · Zbl 0758.65043 |
| [76] | Martı́nez, J. M.; Ochi, L. S., Sobre dois métodos de Broyden, Mat. Apl. Comput., 1, 135-141 (1982) · Zbl 0502.65032 |
| [77] | Martı́nez, J. M.; Qi, L., Inexact Newton methods for solving nonsmooth equations, J. Comput. Appl. Math., 60, 127-145 (1995) · Zbl 0833.65045 |
| [78] | Martı́nez, J. M.; Zambaldi, M. C., An inverse Column-updating method for solving large-scale nonlinear systems of equations, Optim. Methods Software, 1, 129-140 (1992) |
| [79] | Matthies, H.; Strang, G., The solution of nonlinear finite element equations, Internat. J. Numer. Methods Eng., 14, 1613-1626 (1979) · Zbl 0419.65070 |
| [80] | Moré, J. J.; Trangenstein, J. A., On the global convergence of Broyden’s method, Math. Comp., 30, 523-540 (1976) · Zbl 0353.65036 |
| [81] | Ortega, J. M.; Rheinboldt, W. G., Iterative Solution of Nonlinear Equations in Several Variables (1970), Academic Press: Academic Press New York · Zbl 0241.65046 |
| [82] | Ostrowski, A. M., Solution of Equations in Euclidean and Banach Spaces (1973), Academic Press: Academic Press New York · Zbl 0304.65002 |
| [83] | Paloschi, J. R.; Perkins, J. D., The updating of LU-factors in quasi-Newton methods, Comput. Chem. Eng., 10, 241-247 (1986) |
| [84] | Polak, E., A globally converging secant method with applications to boundary value problems, SIAM J. Numer. Anal., 11, 529-537 (1974) · Zbl 0286.65028 |
| [85] | Powell, M. J.D., A hybrid method for nonlinear equations, (Rabinowitz, P., Numerical Methods for Nonlinear Algebraic Equations (1970), Gordon and Breach: Gordon and Breach London), 87-114 · Zbl 0277.65028 |
| [86] | Powell, M. J.D., Direct search algorithms for optimization calculations, Acta Numer., 287-336 (1998) · Zbl 0911.65050 |
| [87] | Rall, L. B., Automatic Differentiation - Techniques and Applications. Automatic Differentiation - Techniques and Applications, Springer Lecture Notes in Computer Science, Vol 120 (1981), Springer: Springer Berlin · Zbl 0473.68025 |
| [88] | Rall, L. B., Differentiation in PASCAL-SC: type gradient, ACM Trans. Math. Software, 10, 161-184 (1984) · Zbl 0564.65010 |
| [89] | Rall, L. B., Optimal implementation of differentiation arithmetic, (Külisch, U., Computer Arithmetic, Scientific Computation and Programming Languages (1987), Teubner: Teubner Stuttgart) · Zbl 0618.65010 |
| [90] | Rheinboldt, W. C., Numerical Analysis of Parametrized Nonlinear Equations (1986), Wiley: Wiley New York · Zbl 0572.65034 |
| [91] | Rheinboldt, W. C.; Vandergraft, J. S., On the local convergence of update methods, SIAM J. Numer. Anal., 11, 1069-1085 (1974) · Zbl 0288.65029 |
| [92] | R.B. Schnabel, Quasi-Newton methods using multiple secant equations, TR CU-CS-247-83, Department of Computer Science, University of Colorado at Boulder, 1983.; R.B. Schnabel, Quasi-Newton methods using multiple secant equations, TR CU-CS-247-83, Department of Computer Science, University of Colorado at Boulder, 1983. |
| [93] | Schubert, L. K., Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comp., 24, 27-30 (1970) · Zbl 0198.49402 |
| [94] | Schwetlick, H., Numerische Lösung Nichtlinearer Gleichungen (1978), Deutscher Verlag der Wissenschaften: Deutscher Verlag der Wissenschaften Berlin |
| [95] | Shamanskii, V. E., A modification of Newton’s method, Ukrain Mat. Z., 19, 133-138 (1967) · Zbl 0176.13802 |
| [96] | Shi, Y. X., Solving nonlinear systems using a global-local procedure, Z. Angew. Math. Mech., 76, 539-540 (1996) · Zbl 0900.65157 |
| [97] | Shi, Y. X., A globalization procedure for solving nonlinear systems of equations, Numer. Algorithms, 12, 273-286 (1996) · Zbl 0861.65048 |
| [98] | Spedicato, E.; Greenstadt, J., On some classes of variationally derived quasi-Newton algorithms for systems of nonlinear algebraic equations, Numer. Math., 29, 363-380 (1978) · Zbl 0365.65033 |
| [99] | Tewarson, R. P.; Zhang, Y., Sparse quasi-Newton LDU update, Internat. J. Numer. Methods Eng., 24, 1093-1100 (1987) · Zbl 0622.65038 |
| [100] | S.W. Thomas, Sequential estimation techniques for quasi-Newton algorithms, Technical Report TR 75-227, Cornell University, 1975.; S.W. Thomas, Sequential estimation techniques for quasi-Newton algorithms, Technical Report TR 75-227, Cornell University, 1975. |
| [101] | Watson, L. T., A globally convergent algorithm for computing points of \(C^2\) maps, Appl. Math. Comput., 5, 297-311 (1979) · Zbl 0445.65032 |
| [102] | Watson, L. T.; Billups, S. C.; Morgan, A. P., Algorithm 652: HOMPACK: A suite of codes for globally convergent homotopy algorithms, ACM Trans. Math. Software, 13, 281-310 (1987) · Zbl 0626.65049 |
| [103] | Wolfe, P., The secant method for solving nonlinear equations, Comm. ACM, 12, 12-13 (1959) · Zbl 0093.13202 |
| [104] | Z. Zlatev, J. Wasniewski, K. Schaumburg, Y12M, Solution of Large and Sparse Systems of Linear Algebraic Equations, Lecture Notes in Computer Science, Vol. 121, Springer, New York, 1981.; Z. Zlatev, J. Wasniewski, K. Schaumburg, Y12M, Solution of Large and Sparse Systems of Linear Algebraic Equations, Lecture Notes in Computer Science, Vol. 121, Springer, New York, 1981. · Zbl 0461.65023 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
