-
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] |
Joel Kübler, Tobias Weth. Spectral asymptotics of radial solutions and nonradial bifurcation for the Hénon equation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3629-3656. doi: 10.3934/dcds.2020032 |
[2] |
Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020319 |
[3] |
Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135 |
[4] |
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 |
[5] |
Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104 |
[6] |
Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077 |
[7] |
Abdollah Borhanifar, Maria Alessandra Ragusa, Sohrab Valizadeh. High-order numerical method for two-dimensional Riesz space fractional advection-dispersion equation. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020355 |
[8] |
Maika Goto, Kazunori Kuwana, Yasuhide Uegata, Shigetoshi Yazaki. A method how to determine parameters arising in a smoldering evolution equation by image segmentation for experiment's movies. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 881-891. doi: 10.3934/dcdss.2020233 |
[9] |
Biyue Chen, Chunxiang Zhao, Chengkui Zhong. The global attractor for the wave equation with nonlocal strong damping. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021015 |
[10] |
Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013 |
[11] |
Xiaoxiao Li, Yingjing Shi, Rui Li, Shida Cao. Energy management method for an unpowered landing. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020180 |
[12] |
Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095 |
[13] |
Jingjing Wang, Zaiyun Peng, Zhi Lin, Daqiong Zhou. On the stability of solutions for the generalized vector quasi-equilibrium problems via free-disposal set. Journal of Industrial & Management Optimization, 2021, 17 (2) : 869-887. doi: 10.3934/jimo.2020002 |
[14] |
Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019 |
[15] |
Qing-Hu Hou, Yarong Wei. Telescoping method, summation formulas, and inversion pairs. Electronic Research Archive, , () : -. doi: 10.3934/era.2021007 |
[16] |
Alex H. Ardila, Mykael Cardoso. Blow-up solutions and strong instability of ground states for the inhomogeneous nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2021, 20 (1) : 101-119. doi: 10.3934/cpaa.2020259 |
[17] |
Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076 |
[18] |
Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078 |
[19] |
Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020462 |
[20] |
Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250 |
2019 Impact Factor: 1.366
Tools
Article outline
[Back to Top]