-
Previous Article
An approximate mean queue length formula for queueing systems with varying service rate
- JIMO Home
- This Issue
-
Next Article
A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem
Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods
1. | School of Mathematics, Yunnan Normal University, Kunming, Yunnan 650500, China |
2. | Pan-Asia Business School, Yunnan Normal University, Kunming, Yunnan 650092, China |
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 $.
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. |
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. |
[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. |
[1] |
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 |
[2] |
Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 |
[3] |
Haili Qiao, Aijie Cheng. A fast high order method for time fractional diffusion equation with non-smooth data. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021073 |
[4] |
Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 |
[5] |
Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25 |
[6] |
Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327 |
[7] |
Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 |
[8] |
Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 |
[9] |
Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018 |
[10] |
Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002 |
[11] |
Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263 |
[12] |
Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185 |
[13] |
Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021019 |
[14] |
Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83 |
[15] |
Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069 |
[16] |
Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 |
[17] |
Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196 |
[18] |
Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184 |
[19] |
Yueqiang Shang, Qihui Zhang. A subgrid stabilizing postprocessed mixed finite element method for the time-dependent Navier-Stokes equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3119-3142. doi: 10.3934/dcdsb.2020222 |
[20] |
Guo-Bao Zhang, Ruyun Ma, Xue-Shi Li. Traveling waves of a Lotka-Volterra strong competition system with nonlocal dispersal. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 587-608. doi: 10.3934/dcdsb.2018035 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]