Lipschitz-like mapping and its application to convergence analysis of a variant of Newton's method

M. H. Rashid

Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 24 (2021) no. 2, pp. 193-212.

Résumé

Let $X$ and $Y$ be Banach spaces. Let $f: \Omega\to Y$ be a Fréchet differentiable function on an open subset $\Omega$ of $X$ and $F$ be a set-valued mapping with closed graph. Consider the following generalized equation problem: $0 \in f(x)+F(x)$. In the present paper, we study a variant of Newton's method for solving generalized equation (1) and analyze semilocal and local convergence of this method under weaker conditions than those considered by Jean-Alexis and Piétrus [13]. In fact, we show that the variant of Newton's method is superlinearly convergent when the Frechet derivative of f is $(L,p)$-Hölder continuous and $(f+F)^{-1}$ is Lipzchitz-like at a reference point. Moreover, applications of this method to a nonlinear programming problem and a variational inequality are given. Numerical experiments are provided which illustrate the theoretical results.

Bibliographie

[1] Dontchev A. L., “Local convergence of the Newton method for generalized equations”, C. R. Acad. Sci. Ser. I Math. Paris, 322:4 (1996), 327–331 | MR | Zbl

[2] Dontchev A. L., Hager W. W., “An inverse mapping theorem for set-valued maps”, Proc. Amer. Math. Soc., 121:2 (1994), 481–489 | DOI | MR | Zbl

[3] Dontchev A. L., “Uniform convergence of the Newton method for Aubin continuous maps”, Serdica Math. J., 22 (1996), 385–398 | MR | Zbl

[4] Dontchev A. L., “Local analysis of a Newton-type method based on partial linearization”, Lectures in Applied Mathematics, 32, 1996, 295–306 | MR | Zbl

[5] Dontchev A. L., Rockafellar R. T., Implicit Functions and Solution Mappings: A View from Variational Analysis, Second edition, Springer-Verlag, New-York, 2014 | MR | Zbl

[6] Dontchev A. L., Rockafellar R. T., “Convergence of inexact Newton methods for generalized equations”, Math. Program. Ser. B, 139:1–2 (2013), 115–137 | DOI | MR | Zbl

[7] Aragon Artacho F. J., Belyakov A., Dontchev A. L., Lopez M., “Local convergence of quasi-Newton methods under metric regularity”, Comput. Optim. Appl., 58:1 (2014), 225–247 | DOI | MR | Zbl

[8] Ostrowski A. M., Solution of Equations in Euclidian and Banach Spaces, Academic Press, New-York–London, 1970 | MR

[9] Pietrus A., Does Newton's method for set-valued maps converges uniformly in mild differentiability context?, Rev. Colombiana Mat., 34 (2000), 49–56 | MR | Zbl

[10] Pietrus A., “Generalized equations under mild differentiability conditions”, Rev. R. Acad. Cienc. Exact. Fis. Nat., 94:1 (2000), 15–18 | MR | Zbl

[11] Mordukhovich B. S., “Sensitivity analysis in nonsmooth optimization”, Theoretical Aspects of Industrial Design, SIAM Proc. Appl. Math., 58, eds. D.A. Field, V. Komkov, 1992, 32–46 | MR

[12] Mordukhovich B. S., Variational Analysis and Generalized Differentiation, v. I, Basic Theory, Springer, Berlin–Heidelberg–New York, 2006 | MR

[13] Jean-Alexis C., Pietrus A., “A variant of Newton's method for generalized equations”, Rev. Colombiana Mat., 39 (2005), 97–112 | MR | Zbl

[14] Ortega J. M., Rheinboldt W. C., Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New-York–London, 1970 | MR | Zbl

[15] Aubin J. P., “Lipschitz behavior of solutions to convex minimization problems”, Math. Oper. Res., 9:1 (1984), 87–111 | DOI | MR | Zbl

[16] Aragon Artacho F. J., Dontchev A. L., Gaydu M., Geoffroy M. H., Veliov V. M., “Metric regularity of Newton's iteration”, SIAM J. Control Optim., 49:2 (2011), 339–362 | DOI | MR | Zbl

[17] Izmailov A. F., Solodov M. V., Newton-type Methods for Ooptimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Springer-Verlag, Cham, 2014 | DOI | MR

[18] Izmailov A. F., Solodov M. V., “Inexact Josephy-Newton framework for generalized equations and its applications to local analysis of Newtonian methods for constrained optimization”, Comput. Optim. Appl., 46:2 (2010), 347–368 | DOI | MR | Zbl

[19] Aubin J. P., Frankowska H., Set-valued Analysis, Birkhäuser, Boston, 1990 | MR | Zbl

[20] Penot J. P., “Metric regularity, openness and Lipschitzian behavior of multifunctions”, Nonlinear Anal., 13 (1989), 629–643 | DOI | MR | Zbl

[21] Geoffroy M. H., Hilout S., Pietrus A., “Acceleration of convergence in Dontchev's iterative method for solving variational inclusions”, Serdica Math. J., 29:1 (2003), 45–54 | MR | Zbl

[22] Geoffroy M. H., Pietrus A., “A superquadratic method for solving generalized equations in the Holder case”, Ricerche di Matematica LII, 2 (2003), 231–240 | MR | Zbl

[23] Rashid M. H., “A convergence analysis of Gauss-Newton-type method for Holder continuous maps”, Indian J. of Mathematics, 57:2 (2015), 181–198 | MR | Zbl

[24] Rashid M. H., “Convergence analysis of a variant of Newton-type method for generalized equations”, Inter. J. of Computer Mathematics, 95:3 (2018), 584–600 | DOI | MR | Zbl

[25] Rashid M. H., “Convergence analysis of extended Hummel-seebeck-type method for solving variational inclusions”, Vietnam J. Math., 44 (2016), 709–726 | DOI | MR | Zbl

[26] Rashid M. H., “Extended Newton-type method and its convergence analysis for nonsmooth generalized equations”, J. Fixed Point Theory Appl., 19 (2017), 1295–1313 | DOI | MR | Zbl

[27] Rashid M. H., Yuan Y. X., “Convergence properties of a restricted Newton-type method for generalized equations with metrically regular mappings”, Applicable Analysis, 2017 | DOI | MR

[28] Rashid M. H., Yu S.H., Li C., Wu S.Y., “Convergence analysis of the Gauss-Newton-type method for Lipschitz-like mappings”, J. Optim. Theory Appl., 158:1 (2013), 216–233 | DOI | MR | Zbl

[29] Klatte D., Kummer B., “Approximations and generalized Newton methods”, Mathematical Programming, 68:1–2 (2018), 673–716 | DOI | MR

[30] Klatte D., Kummer B., Nonsmooth Equations in Optimization: Reqularity, Calculus, Methods and Applications, Nonconvex Optimization and Its Applications, 60, Kluwer Academic Publ., Dordrecht–Boston–London; Springer, 2002 | MR

[31] Cibulka R., Dontchev A. L., Geoffroy M. H., “Inexact Newton methods and Dennis-More theorems for nonsmooth generalized equations”, SIAM J. Control Optim., 53:2 (2015), 1003–1019 | DOI | MR | Zbl

[32] Cibulka R., Dontchev A. L., Preininger J., Roubal T., Veliov V. M., “Kantorovich-type theorems for generalized equations”, J. Convex Anal., 2:2 (2018), 459–486 | MR | Zbl

[33] Adly S., Cibulka R., Ngai H. V., “Newton's method for solving inclusions using set-valued approximations”, SIAM J. Optim., 25:1 (2015), 159–184 | DOI | MR | Zbl

[34] Adly S., Ngai H. V., Nguyen V. V., “Newton's method for solving generalized equations: Kantorovich's and Smale's approaches”, J. Math. Anal. Appl., 439:1 (2016), 396–418 | DOI | MR | Zbl

[35] Dembo R. S., Eisenstat S. C., Steihaug T., “Inexact Newton methods”, SIAM J. Numer. Anal., 9 (1982), 400–408 | DOI | MR

[36] Silva G. N., “Kantorovich's theorem on Newton's method for solving generalized equations under the majorant condition”, Appl. Math. Comput., 286 (2016), 178–188 | MR | Zbl

[37] Robinson S. M., “Generalized equations and their solutions. Part I: basic theory”, Math. Programming Stud., 10 (1979), 128–141 | DOI | MR | Zbl

[38] Robinson S. M., “Generalized equations and their solutions. Part II: applications to nonlinear programming”, Math. Programming Stud., 19 (1982), 200–221 | DOI | MR | Zbl

[39] Ferris M. C., Pang J. S., “Engineering and economic applications of complementarity problems”, SIAM Rev., 39 (1997), 669–713 | DOI | MR | Zbl