Backward step control for global Newton-type methods. (English) Zbl 1382.65145
Summary: We present and analyze a new damping approach called backward step control for the globalization of the convergence of Newton-type methods for the numerical solution of nonlinear root-finding problems. We provide and discuss reasonable assumptions that imply convergence of backward step control on the basis of generalized Newton paths in conjunction with a backward analysis argument. In particular, convergence to a specific solution and a priori estimates on the residual reduction can be shown. Furthermore, we can guarantee a transition to full steps in the vicinity of a solution, which implies fast local convergence. We present two algorithmic realizations of backward step control and apply the method to more than one hundred examples, including comparisons with different globalization approaches for the minimization of the Rosenbrock function, and to large-scale unconstrained optimization problems from the CUTEst benchmark library using backward step control for an inexact Newton method based on MINRES.
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
| 65H20 | Global methods, including homotopy approaches to the numerical solution of nonlinear equations |
| 58C15 | Implicit function theorems; global Newton methods on manifolds |
| 90C53 | Methods of quasi-Newton type |
References:
| [1] | H. Amann, {\it Ordinary Differential Equations}, de Gruyter Stud. Math. 13, Walter de Gruyter, Berlin, 1990. · Zbl 0708.34002 |
| [2] | U. Ascher and M. R. Osborne, {\it A note on solving nonlinear equations and the natural criterion function}, J. Optim. Theory Appl., 55 (1987), pp. 147-152. · Zbl 0622.90074 |
| [3] | P. Blanchard, {\it Complex analytic dynamics on the Riemann sphere}, Bull. Amer. Math. Soc. (N.S.), 11 (1984), pp. 85-141. · Zbl 0558.58017 |
| [4] | H. G. Bock, {\it Randwertproblemmethoden zur Parameteridentifizierung in Systemen nichtlinearer Differentialgleichungen}, Bonner Math. Schriften 183, Universität Bonn, Bonn, Germany, 1987. · Zbl 0622.65064 |
| [5] | H. G. Bock, E. A. Kostina, and J. P. Schlöder, {\it On the role of natural level functions to achieve global convergence for damped Newton methods}, in System Modelling and Optimization. Methods, Theory and Applications, M. J. D. Powell and S. Scholtes, eds., Kluwer Academic Publishers, Dordrecht, The Netherlands, 2000, pp. 51-74. · Zbl 0982.65068 |
| [6] | P. T. Boggs, {\it The solution of nonlinear systems of equations by \(A\)-stable integration techniques}, SIAM J. Numer. Anal., 8 (1971), pp. 767-785. · Zbl 0209.47002 |
| [7] | A. Cayley, {\it Desiderata and suggestions: No. 3. The Newton-Fourier imaginary problem}, Amer. J. Math., 2 (1879), p. 97. · JFM 11.0260.02 |
| [8] | E. A. Coddington and N. Levinson, {\it Theory of Ordinary Differential Equations}, Tata McGraw-Hill Publishing, New Delhi, India, 1998. · Zbl 0064.33002 |
| [9] | T. F. Coleman and Y. Li, {\it On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds}, Math. Program., 67 (1994), pp. 189-224. · Zbl 0842.90106 |
| [10] | T. F. Coleman and Y. Li, {\it An interior trust region approach for nonlinear minimization subject to bounds}, SIAM J. Optim., 6 (1996), pp. 418-445. · Zbl 0855.65063 |
| [11] | A. R. Conn, N. I. M. Gould, and Ph. L. Toint, eds., {\it Trust Region Methods}, MOS/SIAM Ser. Optim. 1, SIAM, Philadelphia, 2000. · Zbl 0958.65071 |
| [12] | D. F. Davidenko, {\it On a new method of numerical solution of systems of nonlinear equations}, Dokl. Akad. Nauk SSSR (N.S.), 88 (1953), pp. 601-602. · Zbl 0050.12103 |
| [13] | R. S. Dembo, S. C. Eisenstat, and T. Steihaug, {\it Inexact Newton methods}, SIAM J. Numer. Anal., 19 (1982), pp. 400-408. · Zbl 0478.65030 |
| [14] | P. Deuflhard, {\it Ein Newton-Verfahren bei fastsingulärer Funktionalmatrix zur Lösung von nichtlinearen Randwertaufgaben mit der Mehrzielmethode}, Ph.D. thesis, Math. Institute, Universität zu Köln, Cologne, Germany, 1972. |
| [15] | P. Deuflhard, {\it A modified Newton method for the solution of ill-conditioned systems of nonlinear equations with applications to multiple shooting}, Numer. Math., 22 (1974), pp. 289-311. · Zbl 0313.65070 |
| [16] | P. Deuflhard, {\it Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms}, Springer Ser. Comput. Math. 35, Springer, New York, 2006. · Zbl 1056.65051 |
| [17] | E. D. Dolan and J. J. Moré, {\it Benchmarking optimization software with performance profiles}, Math. Program., 91 (2002), pp. 201-213. · Zbl 1049.90004 |
| [18] | D. C.-L. Fong and M. A. Saunders, {\it CG versus MINRES: An empirical comparison}, SQU J. Sci., 17 (2012), pp. 44-62. |
| [19] | A. Galántai and J. Abaffy, {\it Always convergent iteration methods for nonlinear equations of Lipschitz functions}, Numer. Algorithms, 69 (2015), pp. 443-453. · Zbl 1319.65036 |
| [20] | N. I. M. Gould, D. Orban, and P. L. Toint, {\it CUTEst: A constrained and unconstrained testing environment with safe threads}, Comput. Optim. Appl., 60 (2015), pp. 545-557. · Zbl 1325.90004 |
| [21] | M. R. Hestenes and E. Stiefel, {\it Methods of conjugate gradients for solving linear systems}, J. Res. Nat. Bur. Standards, 49 (1952), pp. 409-436. · Zbl 0048.09901 |
| [22] | J. J. Moré, {\it The Levenberg-Marquardt algorithm: Implementation and theory}, in Numerical Analysis, Lecture Notes in Math. 630, Springer, New York, 1978, pp. 105-116. · Zbl 0372.65022 |
| [23] | K. Naono, K. Teranishi, J. Cavazos, and R. Suda, eds., {\it Software Automatic Tuning}, Springer, New York, 2010. |
| [24] | J. Nocedal and S. J. Wright, {\it Numerical Optimization}, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 2006. · Zbl 1104.65059 |
| [25] | J. M. Ortega and W. C. Rheinboldt, {\it Iterative Solution of Nonlinear Equations in Several Variables}, Academic Press, New York, 1970. · Zbl 0241.65046 |
| [26] | C. C. Paige and M. A. Saunders, {\it Solutions of sparse indefinite systems of linear equations}, SIAM J. Numer. Anal., 12 (1975), pp. 617-629. · Zbl 0319.65025 |
| [27] | A. Potschka, {\it A Direct Method for Parabolic PDE Constrained Optimization Problems}, Adv. Numer. Math., Springer, New York, 2013. · Zbl 1293.49002 |
| [28] | Y. Saad and M. H. Schultz, {\it GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems}, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856-869. · Zbl 0599.65018 |
| [29] | D. C. Sorensen, {\it Newton’s method with a model trust region modification}, SIAM J. Numer. Anal., 19 (1982), pp. 409-426. · Zbl 0483.65039 |
| [30] | J. Stoer and R. Bulirsch, {\it Introduction to Numerical Analysis}, Texts Appl. Math. 12, Springer, New York, 2008. · Zbl 0423.65002 |
| [31] | P. L. Toint, {\it Some numerical results using a sparse matrix updating formula in unconstrained optimization}, Math. Comput., 32 (1978), pp. 839-852. · Zbl 0381.65036 |
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.
