Geodesic
Globalizing convergence of piecewise Newton methods
Vestnik rossijskih universitetov. Matematika, Tome 29 (2024) no. 146, pp. 149-163 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider versions of the Newton method for piecewise smooth nonlinear equations, as well as of the Gauss–Newton method for the case when additional constraints are imposed, supplied with linesearch procedures for the residual of the equation, aiming at globalization of convergence. (Constrained) piecewise smooth nonlinear equations arise naturally as reformulations of systems of equations and inequalities involving complementarity conditions. In cases when the direction of the Newton method cannot be computed, or appears too long, the algorithm switches to a safeguarding step of the gradient descent method for the squared residual of of the equation with smooth selection mapping active at the current iterate. For the Gauss–Newton method, safeguarding steps of the gradient projection method are employed. We obtain results characterizing properties of possible accumulation points of sequences generated by these methods, namely, stationarity of any such point for at least one smooth selection mapping active at it, and conditions assuring asymptotic superlinear convergence rate of such sequences. Special attention is paid to the majorization condition for the norm of the mapping by the norms of smooth selection mappings, playing a crucial role in the analysis for the piecewise smooth case. Examples are provided demonstrating that in cases of violation of this condition, the algorithms in question may produce sequences converging to points that are not stationary for any active smooth selection mapping.
Keywords: constrained nonlinear equation, piecewise smooth mapping, piecewise Newton method, piecewise Gauss–Newton method, linesearch, superlinear convergence rate
Mots-clés : global convergence 
@article{VTAMU_2024_29_146_a2,
     author = {D. I. Dorovskikh and A. F. Izmailov and E. I. Uskov},
     title = {Globalizing convergence of piecewise {Newton} methods},
     journal = {Vestnik rossijskih universitetov. Matematika},
     pages = {149--163},
     year = {2024},
     volume = {29},
     number = {146},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTAMU_2024_29_146_a2/}
}
TY  - JOUR
AU  - D. I. Dorovskikh
AU  - A. F. Izmailov
AU  - E. I. Uskov
TI  - Globalizing convergence of piecewise Newton methods
JO  - Vestnik rossijskih universitetov. Matematika
PY  - 2024
SP  - 149
EP  - 163
VL  - 29
IS  - 146
UR  - http://geodesic.mathdoc.fr/item/VTAMU_2024_29_146_a2/
LA  - ru
ID  - VTAMU_2024_29_146_a2
ER  - 
%0 Journal Article
%A D. I. Dorovskikh
%A A. F. Izmailov
%A E. I. Uskov
%T Globalizing convergence of piecewise Newton methods
%J Vestnik rossijskih universitetov. Matematika
%D 2024
%P 149-163
%V 29
%N 146
%U http://geodesic.mathdoc.fr/item/VTAMU_2024_29_146_a2/
%G ru
%F VTAMU_2024_29_146_a2
D. I. Dorovskikh; A. F. Izmailov; E. I. Uskov. Globalizing convergence of piecewise Newton methods. Vestnik rossijskih universitetov. Matematika, Tome 29 (2024) no. 146, pp. 149-163. http://geodesic.mathdoc.fr/item/VTAMU_2024_29_146_a2/

[1] W. W. Hager, “Lipschitz continuity for constrained processes”, SIAM J. on Control and Optimization, 17 (1979), 321–338 | DOI | MR | Zbl

[2] A. F. Izmailov, E. I. Uskov, Yan Zhibai, “The piecewise Levenberg–Marquardt method”, Advances in System Sciences and Applications, 2024 (to appear)

[3] 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

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

[5] 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 | DOI | MR | Zbl

[6] A. F. Izmailov, M. V. Solodov, Numerical Optimization Methods, 2nd ed., revised. and additional, Fizmatlit, Moscow, 2008 (In Russian) | MR

[7] 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 (2021), 273–286 | DOI | MR | Zbl

[8] D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Athena, Belmont, 1996 | MR

[9] A. N. Daryina, A. F. Izmailov, M. V. Solodov, “A class of active-set newton methods for mixed complementarity problems”, SIAM J. on Optimization, 15 (2004), 409–429 | DOI | MR | Zbl

[10] M. Frank, P. Wolfe, “An algorithm for quadratic programming”, Naval Research Logistics Quarterly, 3 (1956), 95–110 | DOI | MR

[11] C. Kanzow, N. Yamashita, M. Fukushima, “Levenberg–Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints”, J. of Computational and Applied Mathematics, 172 (2004), 375–397 | DOI | MR | Zbl

[12] D. P. Bertsekas, Nonlinear Programming, 2nd ed., Athena, Belmont, 1999 | MR | Zbl

[13] R. Behling, The Method and the Trajectory of Levenberg–Marquardt, PhD Thesis, IMPA — Instituto Nacional de Matemática Pura e Aplicada, Rio de Janeiro, Brazil , 2011 https://impa.br/wp-content/uploads/2017/08/tese_dout_roger_behling.pdf