American Institute of Mathematical Sciences

Advanced
January  2021, 17(1): 169-184. doi: 10.3934/jimo.2019105

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

Received  August 2018 Revised  April 2019 Published  September 2019

Fund Project: 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)

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: Generalized equation, inexact Newton method, quasi-Newton method, Hölder strong metric subregularity, Hölder isolated calmness.
Mathematics Subject Classification: Primary: 49J53, 49M37; Secondary: 65J15, 90C31.
Citation: Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

A. L. Dontchev, Generalizations of the Dennis-Moré theorem, SIAM J. Optim., 22 (2012), 821-830.  doi: 10.1137/110833567.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

A. L. Dontchev, Generalizations of the Dennis-Moré theorem, SIAM J. Optim., 22 (2012), 821-830.  doi: 10.1137/110833567.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237
[2]

Basim A. Hassan. A new type of quasi-newton updating formulas based on the new quasi-newton equation. Numerical Algebra, Control & Optimization, 2020, 10 (2) : 227-235. doi: 10.3934/naco.2019049
[3]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[4]

Charles Pugh, Michael Shub, Amie Wilkinson. Hölder foliations, revisited. Journal of Modern Dynamics, 2012, 6 (1) : 79-120. doi: 10.3934/jmd.2012.6.79
[5]

Jinpeng An. Hölder stability of diffeomorphisms. Discrete & Continuous Dynamical Systems, 2009, 24 (2) : 315-329. doi: 10.3934/dcds.2009.24.315
[6]

Hong-Yi Miao, Li Wang. Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021012
[7]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733
[8]

Samia Challal, Abdeslem Lyaghfouri. Hölder continuity of solutions to the $A$-Laplace equation involving measures. Communications on Pure & Applied Analysis, 2009, 8 (5) : 1577-1583. doi: 10.3934/cpaa.2009.8.1577
[9]

Luciano Abadías, Carlos Lizama, Marina Murillo-Arcila. Hölder regularity for the Moore-Gibson-Thompson equation with infinite delay. Communications on Pure & Applied Analysis, 2018, 17 (1) : 243-265. doi: 10.3934/cpaa.2018015
[10]

Luis Barreira, Claudia Valls. Hölder Grobman-Hartman linearization. Discrete & Continuous Dynamical Systems, 2007, 18 (1) : 187-197. doi: 10.3934/dcds.2007.18.187
[11]

Rafael De La Llave, R. Obaya. Regularity of the composition operator in spaces of Hölder functions. Discrete & Continuous Dynamical Systems, 1999, 5 (1) : 157-184. doi: 10.3934/dcds.1999.5.157
[12]

Luca Lorenzi. Optimal Hölder regularity for nonautonomous Kolmogorov equations. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 169-191. doi: 10.3934/dcdss.2011.4.169
[13]

Vincent Lynch. Decay of correlations for non-Hölder observables. Discrete & Continuous Dynamical Systems, 2006, 16 (1) : 19-46. doi: 10.3934/dcds.2006.16.19
[14]

Andrey Kochergin. A Besicovitch cylindrical transformation with Hölder function. Electronic Research Announcements, 2015, 22: 87-91. doi: 10.3934/era.2015.22.87
[15]

Walter Allegretto, Yanping Lin, Shuqing Ma. Hölder continuous solutions of an obstacle thermistor problem. Discrete & Continuous Dynamical Systems - B, 2004, 4 (4) : 983-997. doi: 10.3934/dcdsb.2004.4.983
[16]

Pedro Duarte, Silvius Klein, Manuel Santos. A random cocycle with non Hölder Lyapunov exponent. Discrete & Continuous Dynamical Systems, 2019, 39 (8) : 4841-4861. doi: 10.3934/dcds.2019197
[17]

Slobodan N. Simić. Hölder forms and integrability of invariant distributions. Discrete & Continuous Dynamical Systems, 2009, 25 (2) : 669-685. doi: 10.3934/dcds.2009.25.669
[18]

Chunrong Chen, Shengji Li. Upper Hölder estimates of solutions to parametric primal and dual vector quasi-equilibria. Journal of Industrial & Management Optimization, 2012, 8 (3) : 691-703. doi: 10.3934/jimo.2012.8.691
[19]

Saeed Ketabchi, Hossein Moosaei, M. Parandegan, Hamidreza Navidi. Computing minimum norm solution of linear systems of equations by the generalized Newton method. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008
[20]

Zaiyun Peng, Xinmin Yang, Kok Lay Teo. On the Hölder continuity of approximate solution mappings to parametric weak generalized Ky Fan Inequality. Journal of Industrial & Management Optimization, 2015, 11 (2) : 549-562. doi: 10.3934/jimo.2015.11.549

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (169)
  • HTML views (536)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences