Unit stepsize for the Newton method close to critical solutions

被引:10
作者
Fischer, A. [1 ]
Izmailov, A. F. [2 ]
Solodov, M., V [3 ]
机构
[1] Tech Univ Dresden, Fac Math, D-01062 Dresden, Germany
[2] Lomonosov Moscow State Univ MSU, VMK Fac, OR Dept, Uchebniy Korpus 2, Moscow 119991, Russia
[3] IMPA, Estr Dona Castorina 110, BR-22460320 Rio De Janeiro, RJ, Brazil
基金
俄罗斯基础研究基金会;
关键词
Nonlinear equation; Newton method; Singular solution; Critical solution; 2-Regularity; Linear convergence; Superlinear convergence; Extrapolation; Linesearch; NONLINEAR EQUATIONS; CONVERGENCE;
D O I
10.1007/s10107-020-01496-z
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:697 / 721
页数:25
相关论文
共 18 条
[1]   An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions [J].
Facchinei, Francisco ;
Fischer, Andreas ;
Herrich, Markus .
MATHEMATICAL PROGRAMMING, 2014, 146 (1-2) :1-36
[2]   A family of Newton methods for nonsmooth constrained systems with nonisolated solutions [J].
Facchinei, Francisco ;
Fischer, Andreas ;
Herrich, Markus .
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2013, 77 (03) :433-443
[3]   On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption [J].
Fan, JY ;
Yuan, YX .
COMPUTING, 2005, 74 (01) :23-39
[4]   Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems [J].
Fernandez, Damian ;
Solodov, Mikhail .
MATHEMATICAL PROGRAMMING, 2010, 125 (01) :47-73
[5]   Local Attractors of Newton-Type Methods for Constrained Equations and Complementarity Problems with Nonisolated Solutions [J].
Fischer, Andreas ;
Izmailov, Alexey F. ;
Solodov, Mikhail V. .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2019, 180 (01) :140-169
[6]   ON SOLVING NONLINEAR EQUATIONS WITH SIMPLE SINGULARITIES OR NEARLY SINGULAR SOLUTIONS [J].
GRIEWANK, A .
SIAM REVIEW, 1985, 27 (04) :537-563
[7]  
Griewank A, 1980, THESIS
[8]   STARLIKE DOMAINS OF CONVERGENCE FOR NEWTON METHOD AT SINGULARITIES [J].
GRIEWANK, AO .
NUMERISCHE MATHEMATIK, 1980, 35 (01) :95-111
[9]  
Izmailov AF, 2014, SPRINGER SER OPER RE, P1, DOI 10.1007/978-3-319-04247-3
[10]   Critical solutions of nonlinear equations: stability issues [J].
Izmailov, A. F. ;
Kurennoy, A. S. ;
Solodov, M. V. .
MATHEMATICAL PROGRAMMING, 2018, 168 (1-2) :475-507