Accelerating convergence of Newton-type methods to singular solutions of nonlinear equations

A. F. Izmailov   ; E. I. Uskov

Vestnik rossijskih universitetov. Matematika, Tome 29 (2024) no. 148, pp. 401-424

Résumé

We consider the simplest extrapolation procedure, specifically doubling the step, intended for acceleration of convergence of Newton-type methods to singular solutions of smooth nonlinear equations. We demonstrate that the acceleration effect of this procedure can be different for different Newton-type methods. For linear-quadratic equations we provide theoretical results yielding quantitative estimates of the potential effect of extrapolation for the Newton method, for the Levenberg–Marquardt method, and for the recently proposed LPNewton method, in some sense explaining the observed difference. Theoretical analysis relies on interpretation of these methods as a perturbed Newton method with the appropriate estimates of perturbations, as well as on sharp results yielding a quantitative characterization of a step of such perturbed method, and its local convergence at a linear rate to singular solutions satisfying the 2-regularity condition in a direction from the null space of the first derivative. Furthermore, we perform numerical experiments with globalized versions of the algorithms in question, equipped with choosing the stepsize parameter, on two sets of test problems. Experimental observations confirm the theoretical results, and also demonstrate that in cases when the equation contains nonlinear and nonquadratic terms, the effect of extrapolation is evened out.

Détail

Keywords: nonlinear equation, Newton method, LP-Newton method
Mots-clés : singular solution, Levenberg–Marquardt method, extrapolation

Bibliographie

[1] A. Griewank, Analysis and Modification of Newton's Method at Singularities, PhD Thesis, Australian National University, Canberra, 1980 | MR

[2] A. Griewank, “On solving nonlinear equations with simple singularities or nearly singular solutions”, SIAM Review, 27 (1985), 537–563 | DOI | MR | Zbl

[3] A. F. Izmailov, M. V. Solodov, Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Springer, Cham, 2014, 573 pp. | DOI | MR | Zbl

[4] K. Levenberg, “A method for the solution of certain non-linear problems in least squares”, Quarterly of Applied Mathematics, 2 (1944), 164–168 | DOI | MR | Zbl

[5] D. W. Marquardt, “An algorithm for least squares estimation of non-linear parameters”, SIAM J., 11 (1963), 431–441 | MR | Zbl

[6] J. E. Dennis, Jr., R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, Inc., Englewood Cliffs, 1983 | MR | MR | Zbl

[7] A. Fischer, A. F. Izmailov, M. V. Solodov, “The Levenberg–Marquardt method: an overview of modern convergence theories and more”, Computational Optimization and Applications, 89:1 (2024), 33–67 | DOI | MR | Zbl

[8] F. Facchinei, A. Fischer, M. Herrich, “An LP-Newton method: Nonsmooth equations, KKT systems, and nonisolated solutions”, Mathematical Programming, 146 (2014), 1–36 | DOI | MR | Zbl

[9] A. F. Izmailov, A. A. Tret'yakov, 2-Regular Solutions of Nonlinear Problems. Theorey and Numerical Methods, Fizmatlit Publ., Moscow, 1999 (In Russian)

[10] A. F. Izmailov, A. S. Kurennoy, M. V. Solodov, “Critical solutions of nonlinear equations: local attraction for Newton-type methods”, Mathematical Programming, 167:2 (2018), 355–379 | DOI | MR | Zbl

[11] A. Fischer, A. F. Izmailov, M. Jelitte, “Behavior of Newton-type methods near critical solutions of nonlinear equations with semismooth derivatives”, Journal of Optimization Theory and Applications, 2023, New Trends in Optimization, Control, and Their Applications: A Special Issue Dedicated to Boris Sh. Mordukhovich | MR

[12] A. Fischer, A. F. Izmailov, M. V. Solodov, “Accelerating convergence of the globalized Newton method to critical solutions of nonlinear equations”, Computational Optimization and Applications, 78:1 (2021), 273–286 | DOI | MR | Zbl

[13] A. Fischer, A. F. Izmailov, M. V. Solodov, “Unit stepsize for the Newton method close to critical solutions”, Mathematical Programming, 187:1–2 (2021), 697–721 | DOI | MR | Zbl

[14] A. Fischer, A. F. Izmailov, M. Jelitte, “Newton-type methods near critical solutions of piecewise smooth nonlinear equations”, Computational Optimization and Applications, 80:2 (2021), 587–615 | DOI | MR | Zbl

[15] A. Griewank, “Starlike domains of convergence for Newton's method at singularities”, Numerische Mathematik, 35 (1980), 95–111 | DOI | MR | Zbl

[16] A. Fischer, P. K. Shukla, “A Levenberg–Marquardt algorithm for unconstrained multicriteria optimization”, Operations Research Letters, 36 (2008), 643–646 | DOI | MR | Zbl

[17] A. Fischer, M. Herrich, A. F. Izmailov, M. V. Solodov, “A globally convergent LP-Newton method”, SIAM J. on Optimization, 26 (2016), 2012–2033 | DOI | MR | Zbl

[18] J. J. Moré, B. S. Garbow, K. E. Hillstrom, “Testing unconstrained optimization software”, ACM Transactions of Mathematical Software, 7 (1981), 17–41 | DOI | MR | Zbl

[19] R. B. Schnabel, P. D. Frank, “Tensor methods for nonlinear equations”, SIAM J. on Numerical Analysis, 21 (1984), 815–843 | DOI | MR | Zbl

[20] E. D. Dolan, J. J. More, “Benchmarking optimization software with performance profiles”, Mathematical Programming, 91 (2002), 201–213 | DOI | MR | Zbl

[21] A. F. Izmailov, M. V. Solodov, E. I. Uskov, “Combining stabilized SQP with the augmented Lagrangian algorithm”, Computational Optimization and Applications, 62 (2015), 405–429 | DOI | MR | Zbl

[22] A. F. Izmailov, “New implementations of the 2-factor method”, Computational Mathematics and Mathematical Physics, 55:6 (2015), 922–934 | DOI | DOI | MR | Zbl