Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods

Wei Ouyang; Li Li

doi:10.3934/jimo.2019105

Article Contents

2021, Volume 17, Issue 1: 169-184. Doi: 10.3934/jimo.2019105

This issue Previous Article A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem Next Article An approximate mean queue length formula for queueing systems with varying service rate

Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods

Wei Ouyang^1, , and
Li Li^2,

1.
School of Mathematics, Yunnan Normal University, Kunming, Yunnan 650500, China
2.
Pan-Asia Business School, Yunnan Normal University, Kunming, Yunnan 650092, China

^* Corresponding author: Wei Ouyang
^* Corresponding author: Wei Ouyang

Received: July 31, 2018

Revised: March 31, 2019

Early access: September 2019

Published: January 2021

The first author is supported by the National Natural Science Foundation of the People's Republic of China (grant 11801500, 61663049) and the Yunnan Provincial Science and Technology Research Program (grant 2017FD070). The second author is supported by the Yunnan Provincial Science and Technology Research Program (grant 2017FB103), Yunnan Provincial Philosophy and Social Science Project (grant YB2016016) and Scientific Research Foundation of Yunnan Provincial Education Department(grant 2016ZZX080)

Abstract Full Text(HTML) Related Papers Cited by

Abstract

In this paper we conduct local convergence analysis of the inexact Newton methods for solving the generalized equation $ 0\in f(x)+F(x) $ under the assumption of Hölder strong metric subregularity, where $ f : X \rightarrow Y $ is a single-valued mapping while $ F : X \rightrightarrows Y $ is a set-valued mapping between arbitrary Banach spaces. Our work are proceeded as twofold: we first explore fully the property of Hölder strong metric subregularity by establishing a verifiable necessary and sufficient condition as well as discussing its stability under small perturbations, and secondly, with the help of aforementioned theoretical analysis, we conclude that every sequence generated by the inexact (quasi) Newton method and staying in a neighborhood of the solution $ \bar x $ is convergent (superlinearly) of order $ p(1+q) $ where $ p $ is the order of Hölder strong metric subregularity imposed on the mapping $ f+F $ and $ q $ is the order of Hölder calmness property for the derivative $ Df $ while $ p $ and $ q $ complement each other as long as $ p(1+q)\geq 1 $.

Keywords:

Mathematics Subject Classification: Primary: 49J53, 49M37; Secondary: 65J15, 90C31.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	S. Adly, R. Cibulka and H. V. Ngai, Newton's method for solving inclusions using set-valued approximations, SIAM J. Optim., 25 (2015), 159-184. doi: 10.1137/130926730.
[2]	S. Adly, H. V. Ngai and V. V. Nguyen, Stability of metric regularity with set-valued perturbations and application to Newton's method for solving generalized equations, Set-Valued Var. Anal., 25 (2017), 543-567. doi: 10.1007/s11228-017-0438-3.
[3]	R. Cibulka, A. L. Dontchev and M. H. Geoffroy, Inexact Newton methods and Dennis-Moré theorems for nonsmooth generalized equations, SIAM J. Control Optim., 53 (2015), 1003-1019. doi: 10.1137/140969476.
[4]	R. Cibulka, A. L. Dontchev and A. Y. Kruger, Strong metric subregularity of mappings in variational analysis and optimization, J. Math. Anal. Appl., 457 (2018), 1247-1282. doi: 10.1016/j.jmaa.2016.11.045.
[5]	R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal., 19 (1982), 400-408. doi: 10.1137/0719025.
[6]	J. E. Dennis Jr. and J. J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 28 (1974), 549-560. doi: 10.1090/S0025-5718-1974-0343581-1.
[7]	A. L. Dontchev and R. T. Rockafellar, Implicit Functions and Solution Mappings, Springer Monographs in Mathematics, Springer, Berlin, 2009. doi: 10.1007/978-0-387-87821-8.
[8]	A. L. Dontchev and R. T. Rockafellar, Newton's method for generalized equations: A sequential implicit function theorem, Math. Program. Series B, 123 (2010), 139-159. doi: 10.1007/s10107-009-0322-5.
[9]	A. L. Dontchev, Generalizations of the Dennis-Moré theorem, SIAM J. Optim., 22 (2012), 821-830. doi: 10.1137/110833567.
[10]	A. L. Dontchev and R. T. Rockafellar, Convergence of inexact Newton methods for generalized equations, Math. Program. Series B, 139 (2013), 115-137. doi: 10.1007/s10107-013-0664-x.
[11]	A. F. Izmailov and M. V. Solodov, Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2014. doi: 10.1007/978-3-319-04247-3.
[12]	A. Y. Kruger, Error bounds and Hölder metric subregularity, Set-Valued Var. Anal., 23 (2015), 705-736. doi: 10.1007/s11228-015-0330-y.
[13]	G. Y. Li and B. S. Mordukhovich, Hölder metric subregularity with applications to proximal point method, SIAM J. Optim., 22 (2012), 1655-1684. doi: 10.1137/120864660.
[14]	B. S. Mordukhovich and W. Ouyang, Higher-order metric subregularity and its applications, J. Global Optim., 63 (2015), 777-795. doi: 10.1007/s10898-015-0271-x.
[15]	A. Uderzo, A strong metric subregularity analysis of nonsmooth mappings via steepest displacement rate, J. Optim. Theory Appl., 171 (2016), 573-599. doi: 10.1007/s10957-016-0952-8.
[16]	B. Zhang and X. Y. Zheng, Well-posedness and generalized metric subregularity with respect to an admissible function, Sci. China Math., 62 (2019), 809-822. doi: 10.1007/s11425-017-9204-5.
[17]	X. Y. Zheng and K. F. Ng, Hölder stable minimizers, tilt stability, and Hölder metric regularity of subdifferentials, SIAM J. Optim., 25 (2015), 416-438. doi: 10.1137/140959845.
[18]	X. Y. Zheng and J. X. Zhu, Generalized metric subregularity and regularity with respect to an admissible function, SIAM J. Optim., 26 (2016), 535-563. doi: 10.1137/15M1016345.