×

Unit stepsize for the Newton method close to critical solutions. (English) Zbl 1470.65102

Summary: As is well known, when initialized close to a nonsingular solution of a smooth nonlinear equation, the Newton method converges to this solution superlinearly. Moreover, the common Armijo linesearch procedure used to globalize the process for convergence from arbitrary starting points, accepts the unit stepsize asymptotically and ensures fast local convergence. In the case of a singular and possibly even nonisolated solution, the situation is much more complicated. Local linear convergence (with asymptotic ratio of 1/2) of the Newton method can still be guaranteed under reasonable assumptions, from a starlike, asymptotically dense set around the solution. Moreover, convergence can be accelerated by extrapolation and overrelaxation techniques. However, nothing was previously known on how the Newton method can be coupled in these circumstances with a linesearch technique for globalization that locally accepts unit stepsize and guarantees linear convergence. It turns out that this is a rather nontrivial issue, requiring a delicate combination of the analyses on acceptance of the unit stepsize and on the iterates staying within the relevant starlike domain of convergence. In addition to these analyses, numerical illustrations and comparisons are presented for the Newton method and the use of extrapolation to accelerate convergence speed.

MSC:

65H10 Numerical computation of solutions to systems of equations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Facchinei, F.; Fischer, A.; Herrich, M., A family of Newton methods for nonsmooth constrained systems with nonisolated solutions, Math. Methods Oper. Res., 77, 433-443 (2013) · Zbl 1269.49046 · doi:10.1007/s00186-012-0419-0
[2] Facchinei, F.; Fischer, A.; Herrich, M., An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions, Math. Program., 146, 1-36 (2014) · Zbl 1317.90276 · doi:10.1007/s10107-013-0676-6
[3] Fernández, D.; Solodov, M., Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems, Math. Program., 125, 47-73 (2010) · Zbl 1203.90144 · doi:10.1007/s10107-008-0255-4
[4] Fischer, A.; Izmailov, AF; Solodov, MV, Local attractors of Newton-type methods for constrained equations and complementarity problems with nonisolated solutions, J. Optim. Theory Appl., 180, 140-169 (2019) · Zbl 1476.65116 · doi:10.1007/s10957-018-1297-2
[5] Fan, J-Y; Yuan, Y-X, On the quadratic convergence of the Levenberg-Marquardt method, Computing, 74, 23-39 (2005) · Zbl 1076.65047 · doi:10.1007/s00607-004-0083-1
[6] Griewank, A.: Analysis and modification of Newton’s method at singularities. Ph.D. thesis. Australian National University, Canberra (1980) · Zbl 0419.65034
[7] Griewank, A., Starlike domains of convergence for Newton’s method at singularities, Numer. Math., 35, 95-111 (1980) · Zbl 0419.65034 · doi:10.1007/BF01396373
[8] Griewank, A., On solving nonlinear equations with simple singularities or nearly singular solutions, SIAM Rev., 27, 537-563 (1985) · Zbl 0598.65026 · doi:10.1137/1027141
[9] Izmailov, AF; Kurennoy, AS; Solodov, MV, Critical solutions of nonlinear equations: local attraction for Newton-type methods, Math. Program., 167, 355-379 (2018) · Zbl 1404.90128 · doi:10.1007/s10107-017-1128-5
[10] Izmailov, AF; Kurennoy, AS; Solodov, MV, Critical solutions of nonlinear equations: stability issues, Math. Program., 168, 475-507 (2018) · Zbl 1396.90086 · doi:10.1007/s10107-016-1047-x
[11] Izmailov, AF; Solodov, MV, Stabilized SQP revisited, Math. Program., 122, 93-120 (2012) · Zbl 1245.90145 · doi:10.1007/s10107-010-0413-3
[12] Izmailov, AF; Solodov, MV, Newton-Type Methods for Optimization and Variational Problems (2014), Cham: Springer, Cham · Zbl 1304.49001 · doi:10.1007/978-3-319-04247-3
[13] Izmailov, AF; Tretyakov, AA, \(2\)-Regular Solutions of Nonlinear Problems. Theory and Numerical Methods (1999), Moscow: Fizmatlit, Moscow · Zbl 0965.47050
[14] Levenberg, K., A method for the solution of certain non-linear problems in least squares, Q. Appl. Math., 2, 164-168 (1944) · Zbl 0063.03501 · doi:10.1090/qam/10666
[15] Marquardt, DW, An algorithm for least squares estimation of non-linear parameters, SIAM J., 11, 431-441 (1963) · Zbl 0112.10505
[16] Oberlin, C.; Wright, SJ, An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems, Math. Program., 117, 355-386 (2009) · Zbl 1166.65341 · doi:10.1007/s10107-007-0173-x
[17] Wright, SJ, Superlinear convergence of a stabilized SQP method to a degenerate solution, Comput. Optim. Appl., 11, 253-275 (1998) · Zbl 0917.90279 · doi:10.1023/A:1018665102534
[18] Yamashita, N.; Fukushima, M., On the rate of convergence of the Levenberg-Marquardt method, Comput. Suppl., 15, 237-249 (2001) · Zbl 1001.65047
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.