Processing math: 0%

数学物理学报, 2022, 42(5): 1537-1550 doi:

论文

非光滑牛顿算法的收敛性

许文丁,, 钟婷,

四川旅游学院大数据与统计学院 成都 610100

The Convergence of Nonsmooth Newton's Method

Xu Wending,, Zhong Ting,

College of Big Data and Statistics, Sichuan Tourism University, Chengdu 610100

通讯作者: 钟婷, E-mail: zhongting89@sina.cn

收稿日期: 2021-10-14  

基金资助: 国家自然科学基金.  11901414
四川旅游学院旅游统计与应用数学科研创新团队.  20SCTUTY01

Received: 2021-10-14  

Fund supported: the NSFC.  11901414
the Foundation of Sichuan Tourism University.  20SCTUTY01

作者简介 About authors

许文丁,E-mail:wd-xu@hotmail.com , E-mail:wd-xu@hotmail.com

Abstract

This paper studies the convergence of nonsmooth Newton's method for generalized inclusions. By applying metric regularity, a local convergence result of nonsmooth Newton's method is proved. The compactness in a known result is weakened through the measure of non-compactness. A convergence result in global version is established in which the conditions are assumed at the initial point while not the solution of the generalized inclusions.

Keywords: Nonsmooth Newton's method ; Metric regularity ; Convergence ; Measure of non-compactness

PDF (347KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

许文丁, 钟婷. 非光滑牛顿算法的收敛性. 数学物理学报[J], 2022, 42(5): 1537-1550 doi:

Xu Wending, Zhong Ting. The Convergence of Nonsmooth Newton's Method. Acta Mathematica Scientia[J], 2022, 42(5): 1537-1550 doi:

1 引言

众所周知, 最优化理论中有不少问题可转化为如下包含问题

0f(x)+F(x),
(1.1)

其中f:XY为函数(即单值映射), F:X为集值映射, X, Y 为\ Banach空间. 例如, 对于函数 f:X\rightarrow Y 以及闭凸集 C\subset X , 变分不等式问题: 求 x\in C 使得

\begin{equation} \langle{f(x)}, {y-x}\rangle\geq 0, \ \forall y\in C, \end{equation}
(1.2)

即等价于包含问题

0\in f(x)+N_C(x),

其中 N_C(x) 表示集合 C x 处的法锥.

牛顿算法是求解包含问题(1.1) 的重要算法, 在过去几十年受到学者们的广泛研究.

对于光滑函数, 经典的牛顿算法的收敛性通常依赖于其导数的非奇异性, 而导数的非奇异性则是与函数的度量正则性等价的性质. 因此, 对于非光滑的函数, 其度量正则性在不少优化算法的收敛性研究中有重要的应用, 文献[110] 等在研究算法的收敛性时都利用了度量正则性.

本文同样是利用集值映射的度量正则性研究非光滑牛顿算法的收敛性. 下面介绍度量正则性的概念, 关于此概念的理论研究与应用, 可参见文献[1114] 等文献.

X, Y 为Banach空间, F:X\rightrightarrows Y 为集值映射, (\bar{x}, \bar{y}) F 图像上一点, 即 \bar{y}\in F(\bar{x}) . 若存在常数 c>0 以及 (\bar{x}, \bar{y}) 的邻域 U\times V , 使得

\begin{equation} d(x, F^{-1}(y))\leq cd(y, F(x)), \ \forall (x, y)\in U\times V, \end{equation}
(1.3)

则称 F 在点 (\bar{x}, \bar{y}) 处关于常数 c 度量正则. 称度量正则常数 c 的下确界为 F (\bar{x}, \bar{y}) 处的度量正则模, 记为 {{{\rm{reg}}}}(F; \bar{x}|\bar{y}) , 即

\begin{eqnarray*} {{{\rm{reg}}}}(F;\bar{x}|\bar{y}):&=&\inf\Big\{c>0\ |\ \mbox{存在\ }(\bar{x}, \bar{y})\mbox{\ 的邻域\ }U\times V, \mbox{使得\ } \\ && d(x, F^{-1}(y))\leq cd(y, F(x)), \ \forall (x, y)\in U\times V\Big\}. \end{eqnarray*}

由度量正则模的定义可知, F (\bar{x}, \bar{y}) 处度量正则当且仅当

{{{\rm{reg}}}}(F; \bar{x}|\bar{y})<\infty.

对于求解问题(1.1) 的牛顿算法, 当 f 为可微函数时, 文献[11, 定理6C.1] 证明了算法

\begin{equation} 0\in f(x_n)+f'(x_n)(x_{n+1}-x_n)+F(x_{n+1}) \end{equation}
(1.4)

的局部(超线性)收敛性. 此结论对映射 f+F 假设了强度量正则性(关于强度量正则性的定义及相关介绍, 可参见[11]等文献), 该性质比度量正则性更强.

为了将上述收敛性结论中的强度量正则性这一条件削弱, 文献[6] 通过假设和映射 f+F 的“部分线性化”

x\mapsto f(\bar{x})+f'(\bar{x})(x-\bar{x})+F(x)

在问题(1.1) 解点 (\bar{x}, 0) 处的度量正则性, 证明了算法(1.4) 的局部(二次) 收敛性. 此结论是利用度量正则性研究包含问题的牛顿算法的一个经典结论, 关于此结论另一种等价形式的详细介绍, 可参见文献[11, 定理6D.1].

一个自然的问题即为: 如何将上述结论推广至 f 为不可微映射的情形? 众所周知, 可微函数 f 在一点 \bar{x} 的导数 f'(\bar{x}) 为一连续线性映射, 基于这一本质, 文献[11] 通过利用经典的Clarke广义Jacobian \bar{\partial}f(\bar{x}) , 并且假设对任意 A\in\bar{\partial}f(\bar{x}) , 映射

\begin{equation} x\mapsto f(\bar{x})+A(x-\bar{x})+F(x) \end{equation}
(1.5)

在问题(1.1) 解点 (\bar{x}, 0) 处的强度量正则性, 得到了“半光滑牛顿算法”

\begin{equation} 0\in f(x_n)+A_n(x_{n+1}-x_n)+F(x_{n+1}), \ \forall A_n\in\bar{\partial}f(x_n), n=0, 1, 2, \cdots \end{equation}
(1.6)

的局部收敛性. 相关结论还可参见文献[15].

2015年, 文献[1] 将算法(1.6) 进行进一步的推广. 通过定义集值映射 {\cal H}:X\rightrightarrows{\cal L}(X, Y) (其中 {\cal L}(X, Y) 为一族映 X Y 的连续线性映射), 并且假设对每一 A\in{\cal H}(\bar{x}) , 映射(1.5) 在解点 (\bar{x}, 0) 的度量正则性, 文献[1, 定理4.3] 证明了非光滑牛顿算法

\begin{equation} 0\in f(x_n)+{\cal H}(x_n)(x_{n+1}-x_n)+F(x_{n+1}) \end{equation}
(1.7)

的局部(超线性) 收敛性.

此外, 文献[7, 1517] 等通过利用某种"点基"近似的方法研究了各种形式的非光滑牛顿算法的局部收敛性; 文献[6, 1820]等研究了非精确牛顿算法的局部收敛性.

本文将文献[1] 关于非光滑牛顿算法的局部收敛性结果进行了改进. 文献[1, 定理4.3]的假设条件对集合 {\cal H}(\bar{x}) 施加了紧性条件. 在无穷维Banach空间中, 集合的紧性是不容易满足的. 本文第2节将利用非紧性测度条件削弱文献[1, 定理4.3] 中的紧性条件.

另一方面, 在局部收敛性的结果中, 算法的初始点需落入包含问题的解点的某邻域内, 换句话说, 初始点需充分靠近包含问题的解点. 因此, 当问题的解点位置不明确甚至解的存在性尚且未知时, 所得结论的假设条件便不易验证. 而如果假设条件均关于算法的初始点, 则在理论上可有效的避免这一方面的缺陷. 本文第3节将证明牛顿算法的一个全局情形的收敛性结果, 结论中的假设条件均施加于算法的初始点, 而非包含问题的解点.

本文中, 符号 \|{\cdot}\| 表示所考虑的赋范空间的范数. 对于点 x 以及常数 r>0 , 用 B(x, r) 表示以 x 为心, r 为半径的闭球. 对于集值映射 F:X\rightrightarrows Y , 以 {{{\rm{gph}}}} F 表示 F 的图像, 即 {{{\rm{gph}}}} F:=\{(x, y)\ |\ y\in F(x)\} . F^{-1} 表示 F 的逆映射, 即 F^{-1}(y):=\{x\ |\ y\in F(x)\}, \ \forall y .

本节最后, 介绍度量正则性的一个经典单值扰动稳定性结果, 该结果在不少最优化问题以及最优控制理论的研究中有广泛应用, 对于本文主要结论的证明也起到了关键的作用. 关于此结论的证明, 可参见文献[11, 2126].

引理1.1   X, Y 为Banach空间, F:X\rightrightarrows Y 为集值映射, (\bar{x}, \bar{y}) F 图像上一点, g:X\rightarrow Y 为函数. 若存在常数 a, b, c, k>0 满足

(i) ck<1 ;

(ii) d(x, F^{-1}(y))\leq cd(y, F(x)), \ \forall (x, y)\in B(\bar{x}, a)\times B(\bar{y}, b) ;

(iii) \|{g(x)-g(x')}\|\leq k\|{x-x'}\|, \ \forall x, x'\in B(\bar{x}, a) . \\ 则存在 \beta>0 , 使得

d(x, (F+g)^{-1}(y))\leq\frac{c}{1-ck}d(y, (F+g)(x)), \ \forall (x, y)\in B(\bar{x}, \beta)\times B(\bar{y}+g(\bar{x}), \beta).

注1.1  引理1.1的结论中邻域半径 \beta 的取值仅依赖于集值映射 F 的邻域半径 a, b , 度量正则常数 c 以及函数 g 的Lipschitz常数 k .

2 非光滑牛顿算法的局部收敛性

本节介绍算法(1.7) 的局部收敛性结果. 为了削弱文献[1, 定理4.3] 中的紧性条件, 将用到如下关于集合的非紧性测度的概念.

定义2.1[27]  对于度量空间 X 的子集 A , 定义其非紧性测度为

{\cal X}(A):=\inf\bigg\{r\ |\mbox{ 存在} A\mbox{ 的有限子集 } \{x_1, \cdots , x_k\}\subset A, \mbox{使得 } A\subset\bigcup\limits_{i=1}^kB(x_i, r)\bigg\}.

由集合紧性的定义可知, 若集合 A 为紧集, 则 {\cal X}(A)=0 ; 反之, 容易证明, 若 {\cal X}(A)=0 , 则集合 A 的闭包 \bar{A} 是紧集.

下面介绍本节的主要结论.

定理2.1  设 X, Y 为Banach空间, F:X\rightrightarrows Y 为闭集值映射, f:X\rightarrow Y 为连续函数. 设 \bar{x} 为包含问题(0.1) 的一个解, 集值映射 {\cal H}:X\rightrightarrows{\cal L}(X, Y) 满足

(i) {\cal H} \bar{x} 处上半连续;

(ii)

\begin{equation} \lim\limits_{x\rightarrow \bar{x}}\frac{d(f(x)-f(\bar{x}), {\cal H}(x)(x-\bar{x}))}{\|{x-\bar{x}}\|}=0; \end{equation}
(2.1)

(iii) 对每一 H\in{\cal H}(\bar{x}) , 映射

\begin{equation} \Phi_{H}(x):=f(\bar{x})+H(x-\bar{x})+F(x), \ x\in X \end{equation}
(2.2)

在点 (\bar{x}, 0) 处局部度量正则;

(iv)

\sup\limits_{H\in{\cal H}(\bar{x})}{{{\rm{reg}}}}(\Phi_H;\bar{x}|0)\cdot{\cal X}({\cal H}(\bar{x}))<1.

则存在 r>0 , 使得对任意初始点 x_0\in B(\bar{x}, r) , 存在由算法

\begin{equation} 0\in f(x_n)+{\cal H}(x_n)(x_{n+1}-x_n)+F(x_{n+1}) \end{equation}
(2.3)

产生的序列 \{x_n\} 超线性收敛于 \bar{x} .

  由条件(iv), 可取常数 \kappa, \varepsilon, \mu 满足

\begin{equation} \kappa>\sup\limits_{H\in{\cal H}(\bar{x})}{{{\rm{reg}}}}(\Phi_H;\bar{x}|0), \ \ \ \ \mu>\varepsilon>{\cal X}({\cal H}(\bar{x})), \ \ \ \ \kappa\mu<1. \end{equation}
(2.4)

由非紧性测度的定义可知, 存在 {\cal A}=\{H_1, \cdots , H_m\} (其中 m 为某一正整数), 使得

\begin{equation} {\cal A}\subset{\cal H}(\bar{x})\subset{\cal A}+\varepsilon B_{L(X, Y)}. \end{equation}
(2.5)

由条件(iii), 对任意 H_i\in{\cal A} , 存在 a_i, b_i>0 , 使得映射 \Phi_{H_i} 在集合 B(\bar{x}, a_i)\times B(0, b_i) 上关于常数 \kappa 度量正则. 取

\begin{equation} a=\min\limits_{1\leq i\leq m}\{a_i\}, \ b=\min\limits_{1\leq i\leq m}\{b_i\}, \end{equation}
(2.6)

则对任意 H\in{\cal A} , 映射 \Phi_{H} 在集合 B(\bar{x}, a)\times B(0, b) 上关于常数 \kappa 度量正则. 由于 \kappa\mu<1 , 于是, 由引理1.1可知对任一在 \bar{x} 处关于常数 \mu 局部Lipschitz连续的函数 g , 存在 \beta'>0 , 使得

\begin{equation} d(x, (\Phi_{H}+g)^{-1}(y))\leq\frac{c}{1-ck}d(y, (\Phi_{H}+g)(x)), \ \forall (x, y)\in B(\bar{x}, \beta')\times B(g(\bar{x}), \beta'). \end{equation}
(2.7)

{\cal H} \bar{x} 处的上半连续性可知存在 \delta>0 , 使得

\begin{equation} {\cal H}(x)\subset{\cal H}(\bar{x})+(\mu-\varepsilon)B_{L(X, Y)}, \ \forall x\in B(\bar{x}, \delta). \end{equation}
(2.8)

结合(2.5), (2.8) 两式可得

\begin{eqnarray} {\cal H}(x)&\subset&{\cal H}(\bar{x})+(\mu-\varepsilon)B_{L(X, Y)}\\ &\subset&{\cal A}+\varepsilon B_{L(X, Y)}+(\mu-\varepsilon)B_{L(X, Y)}\\ &\subset&{\cal A}+\mu B_{L(X, Y)}, \ \forall x\in B(\bar{x}, \delta). \end{eqnarray}
(2.9)

\begin{equation} \beta:=\min\left\{\beta', \frac{1-\kappa\mu}{\kappa}, 1\right\}, \end{equation}
(2.10)

由条件(2.1) 可知存在 r\in(0, \min\{a, \delta, 1\}) , 使得

\begin{equation} d(f(x)-f(\bar{x}), {\cal H}(x)(x-\bar{x}))<\beta\|{x-\bar{x}}\|, \ \forall x\in B(\bar{x}, r)\setminus\{\bar{x}\}. \end{equation}
(2.11)

任取 x_0\in B(\bar{x}, r) , 下面首先证明存在 x_1\in B(\bar{x}, r) , 使得

\begin{equation} 0\in f(x_0)+{\cal H}(x_0)(x_1-x_0)+F(x_1). \end{equation}
(2.12)

x_0=\bar{x} , 由 0\in f(\bar{x})+F(\bar{x}) 可知只需取 x_1=\bar{x} 即可使(2.12) 式成立.

x_0\neq\bar{x} , 则由(2.11) 式可知 d(f(x_0)-f(\bar{x}), {\cal H}(x_0)(x_0-\bar{x}))<\beta\|{x_0-\bar{x}}\|. \eta_0\in(0, \|{x_0-\bar{x}}\|) 使得

d(f(x_0)-f(\bar{x}), {\cal H}(x_0)(x_0-\bar{x}))+\eta_0<\beta\|{x_0-\bar{x}}\|,

则存在 A_0\in {\cal H}(x_0) , 使得

\begin{eqnarray} \|{f(x_0)-f(\bar{x})-A_0(x_0-\bar{x})}\|&<&d(f(x_0)-f(\bar{x}), {\cal H}(x_0)(x_0-\bar{x}))+\eta_0\\ &<&\beta\|{x_0-\bar{x}}\|. \end{eqnarray}
(2.13)

y_0:=f(x_0)-f(\bar{x})-A_0(x_0-\bar{x}). -y_0\in f(\bar{x})+F(\bar{x}) , 则有

\begin{eqnarray*} 0\in y_0+f(\bar{x})+F(\bar{x})&=&f(x_0)+A_0(\bar{x}-x_0)+F(\bar{x})\\ &\subset &f(x_0)+{\cal H}(x_0)(\bar{x}-x_0)+F(\bar{x}) \end{eqnarray*}

于是也只需取 x_1=\bar{x} 即可.

下面假设 -y_0\notin f(\bar{x})+F(\bar{x}). 由于 x_0\in B(\bar{x}, r)\subset B(\bar{x}, \delta) , 故由(2.9) 式可知

A_0\in{\cal H}(x_0)\subset{\cal A}+\mu B_{L(X, Y)}.

于是存在 H_0\in{\cal A}, T_0\in\mu B_{L(X, Y)} , 使得

\begin{equation} A_0=H_0+T_0. \end{equation}
(2.14)

H_0\in{\cal A} 可知映射 \Phi_{H_0} 在集合 B(\bar{x}, a)\times B(0, b) 上关于常数 \kappa 度量正则. 构造函数

G_0(x):=T_0(x-\bar{x})+y_0, \ x\in X,

G_0(\bar{x})=y_0 , 且由 T_0\in\mu B_{L(X, Y)} 易知 G_0 \bar{x} 处关于常数 \mu 局部Lipschitz连续. 故取(2.7) 式中 g G_0 , 同时注意到 \beta\leq\beta' , 于是可得

\begin{equation} d(x, (\Phi_{H}+g)^{-1}(y))\leq\frac{\kappa}{1-\kappa\mu}d(y, (\Phi_{H}+g)(x)), \ \forall (x, y)\in B(\bar{x}, \beta)\times B(y_0, \beta), \end{equation}
(2.15)

即映射 \Phi_{H_0}+G_0 在集合 B(\bar{x}, \beta)\times B(y_0, \beta) 上关于常数 \frac{\kappa}{1-\kappa\mu} 度量正则.

y_0 的构造, r<1 以及(2.13) 式可知

\|{y_0}\|=\|{f(x_0)-f(\bar{x})-A_0(x_0-\bar{x}))}\|<\beta\|{x_0-\bar{x}}\|\leq\beta r<\beta,

即得 0\in B(y_0, \beta) . 此外, 由 0\in f(\bar{x})+F(\bar{x})=\Phi_{H_0}(\bar{x}) 以及 G_0(\bar{x})=y_0 可知 y_0\in (\Phi_{H_0}+G_0)(\bar{x}) . 注意到 \beta\leq\frac{1-\kappa\mu}{\kappa} , 故由 \Phi_{H_0}+G_0 的度量正则性可知

\begin{eqnarray} d(\bar{x}, (\Phi_{H_0}+G_0)^{-1}(0))&\leq&\frac{\kappa}{1-\kappa\mu}d(0, (\Phi_{H_0}+G_0)(\bar{x})) \leq\frac{\kappa}{1-\kappa\mu}\|{y_0}\|{}\\ &<&\frac{\kappa\beta}{1-\kappa\mu}\|{x_0-\bar{x}}\| \leq \|{x_0-\bar{x}}\|\leq r. \end{eqnarray}
(2.16)

于是, 存在 x_1\in(\Phi_{H_0}+G_0)^{-1}(0) , 使得

\|{x_1-\bar{x}}\|<\frac{\kappa\beta}{1-\kappa\mu}\|{x_0-\bar{x}}\|\leq r,

x_1\in B(\bar{x}, r) , 且由(2.14) 式可知

\begin{eqnarray*} 0\in(\Phi_{H_0}+G_0)(x_1)&=&f(\bar{x})+H_0(x_1-\bar{x})+F(x_1)+T_0(x_1-\bar{x})+y_0\\ &=&f(x_0)+A_0(x_1-\bar{x})+F(x_1)-A_0(x_0-\bar{x})\\ &=&f(x_0)+A_0(x_1-x_0)+F(x_1)\nonumber\\ &\subset& f(x_0)+{\cal H}(x_0)(x_1-x_0)+F(x_1), \end{eqnarray*}

x_1 满足(2.12) 式.

现证明, 若 x_n\in B(\bar{x}, r) (其中 n 为一正整数), 则存在 x_{n+1}\in B(\bar{x}, r) 满足

\begin{equation} 0\in f(x_n)+{\cal H}(x_n)(x_{n+1}-x_n)+F(x_{n+1}). \end{equation}
(2.17)

类似地, 若 x_n=\bar{x} , 则取 x_{n+1}=\bar{x} 即可完成证明.

x_n\neq\bar{x} , 则由(2.11) 式可知

d(f(x_n)-f(\bar{x}), {\cal H}(x_n)(x_n-\bar{x}))<\beta\|{x_n-\bar{x}}\|.

\eta_n\in(0, \frac{\|{x_n-\bar{x}}\|}{n}) 使得

d(f(x_n)-f(\bar{x}), {\cal H}(x_n)(x_n-\bar{x}))+\eta_n<\beta\|{x_n-\bar{x}}\|,

则存在 A_n\in {\cal H}(x_n) , 使得

\begin{eqnarray} \|{f(x_n)-f(\bar{x})-A_n(x_n-\bar{x})}\|&<&d(f(x_n)-f(\bar{x}), {\cal H}(x_n)(x_n-\bar{x}))+\eta_n\\ &<&\beta\|{x_n-\bar{x}}\|. \end{eqnarray}
(2.18)

y_n:=f(x_n)-f(\bar{x})-A_n(x_n-\bar{x}). -y_n\in f(\bar{x})+F(\bar{x}) , 同样易知只需取 x_{n+1}=\bar{x} 则(2.17) 式得证. 现设 x_n\neq\bar{x} -y_n\notin f(\bar{x})+F(\bar{x}) . x_n\in B(\bar{x}, r)\subset B(\bar{x}, \delta) 以及(2.9) 式可知 A_n\in{\cal H}(x_n)\subset{\cal A}+\mu B_{L(X, Y)}, 于是, 存在 H_n\in{\cal A}, T_n\in\mu B_{L(X, Y)} , 使得

\begin{equation} A_n=H_n+T_n. \end{equation}
(2.19)

H_n\in{\cal A} 可知映射 \Phi_{H_n} 在集合 B(\bar{x}, a)\times B(0, b) 上关于常数 \kappa 度量正则. 构造函数

G_n(x):=T_n(x-\bar{x})+y_n, \ x\in X,

G_n(\bar{x})=y_n , 且由 T_n\in\mu B_{L(X, Y)} 易知 G_n \bar{x} 处关于常数 \mu 局部Lipschitz连续. 类似地, 取(2.7) 式中 g G_n 并注意到 \beta\leq\beta' , 可知映射 \Phi_{H_n}+G_n 在集合 B(\bar{x}, \beta)\times B(y_n, \beta) 上关于常数 \frac{\kappa}{1-\kappa\mu} 度量正则. 由 y_n 的构造及(2.18) 式可知

\|{y_n}\|=\|{f(x_n)-f(\bar{x})-A_n(x_n-\bar{x}))}\|<\beta\|{x_n-\bar{x}}\|\leq\beta r<\beta,

0\in B(y_n, \beta). 注意到 y_n\in(\Phi_{H_n}+G_n)(\bar{x}) , 于是, 由 \Phi_{H_n}+G_n 的度量正则性可知

\begin{eqnarray} d(\bar{x}, (\Phi_{H_n}+G_n)^{-1}(0))&\leq&\frac{\kappa}{1-\kappa\mu}d(0, (\Phi_{H_n}+G_n)(\bar{x})) \leq\frac{\kappa}{1-\kappa\mu}\|{y_n}\|{}\\ &<&\frac{\kappa\beta}{1-\kappa\mu}\|{x_n-\bar{x}}\| \leq\|{x_n-\bar{x}}\|\leq r. \end{eqnarray}
(2.20)

于是, 存在 x_{n+1}\in(\Phi_{H_n}+G_n)^{-1}(0) , 使得

\begin{equation} \|{x_{n+1}-\bar{x}}\|<\frac{\kappa}{1-\kappa\mu}\|{y_n}\|<\frac{\kappa\beta}{1-\kappa\mu}\|{x_n-\bar{x}}\|\leq r, \end{equation}
(2.21)

x_{n+1}\in B(\bar{x}, r) , 且由(2.19) 式可知

\begin{eqnarray*} 0\in(\Phi_{H_n}+G_n)(x_{n+1})&=&f(\bar{x})+H_n(x_{n+1}-\bar{x})+F(x_{n+1})+T_n(x_{n+1}-\bar{x})+y_n\\ &=&f(x_n)+A_n(x_{n+1}-\bar{x})+F(x_{n+1})-A_n(x_n-\bar{x})\\ &=&f(x_n)+A_n(x_{n+1}-x_n)+F(x_{n+1})\nonumber\\ &\subset& f(x_n)+{\cal H}(x_n)(x_{n+1}-x_n)+F(x_{n+1}), \end{eqnarray*}

x_{n+1} 满足(2.17) 式.

由归纳法原理可知序列 \{x_n\}\subset B(\bar{x}, r) 由(2.3) 式产生. 注意到 \frac{\kappa\beta}{1-\kappa\mu}<1 , 故由(2.21) 式可知 \{x_n\} 线性收敛于 \bar{x} . 若存在正整数 n_0 , 使得对任意 n>n_0 , 有 x_n\neq\bar{x} , 则由条件(2.1), y_n 的构造, \eta_n 的取法以及(2.18) 式可知

\begin{eqnarray*} \lim\limits_{n\rightarrow \infty}\frac{\|{y_n}\|}{\|{x_n-\bar{x}}\|}&=&\lim\limits_{n\rightarrow \infty}\frac{\|{f(x_n)-f(\bar{x})-A_n(x_n-\bar{x})}\|}{\|{x_n-\bar{x}}\|}\\ &\leq&\lim\limits_{n\rightarrow \infty}\frac{d(f(x_n)-f(\bar{x}), {\cal H}(x_n)(x_n-\bar{x}))+\eta_n}{\|{x_n-\bar{x}}\|}\\ &\leq&\lim\limits_{n\rightarrow \infty}(\frac{d(f(x_n)-f(\bar{x}), {\cal H}(x_n)(x_n-\bar{x}))}{\|{x_n-\bar{x}}\|}+\frac{1}{n})=0. \end{eqnarray*}

\{x_n\} 超线性收敛于 \bar{x} .证毕.

注2.1  在定理2.1中, 若 {\cal H}(\bar{x}) 为紧集, 则 {\cal X}({\cal H}(\bar{x}))=0 , 且此时容易验证

\sup\limits_{H\in{\cal H}(\bar{x})}{{{\rm{reg}}}}(\Phi_H;\bar{x}|0)<\infty,

故条件(iv) 显然成立, 而此时定理2.1即退化为文献[1, 定理4.3], 换句话说, 本文定理2.1削弱了文献[1, 定理4.3]的条件.

3 非光滑牛顿算法的一个全局情形的收敛性结果

本节介绍本文关于非光滑牛顿算法的一个全局情形的收敛性结果, 该结果的假设条件均施加于算法的初始点, 而非所求解的包含问题的解点.

定理3.1  设 x_0\in X, z_0\in f(x_0)+F(x_0), {\cal H}:X\rightrightarrows L(X, Y) , 常数 a, b, \tau, L>0 满足

\begin{equation} \tau L<1, \ \ \ \ \frac{\tau}{1-\tau L}<\frac{1}{6}. \end{equation}
(3.1)

假设对任意 H\in{\cal H}(x_0) , 映射

\begin{equation} \Phi_H(x)=f(x_0)+H(x-x_0)+F(x), \ \forall x\in X \end{equation}
(3.2)

在集合 B(x_0, a)\times B(z_0, b) 上关于常数 \tau 度量正则. 又设 \beta>0 满足: 对任一 H\in{\cal H}(x_0) 以及任一在 x_0 处关于常数 L 局部Lipschitz连续的函数 g , 有

\begin{equation} d(x, (\Phi_H+g)^{-1}(y))\leq\frac{\tau}{1-\tau L}d(y, (\Phi_H+g)(x)), \ \forall (x, y)\in B(x_0, \beta)\times B(z_0+g(x_0), \beta). \end{equation}
(3.3)

若以下条件成立

(i) {\cal H}(x)\subset{\cal H}(x_0)+LB_{L(X, Y)}, \ \forall x\in B(x_0, a).

(ii) 存在 {\cal H} 的一个选择 \psi:X\rightarrow L(X, Y) 使得

\|{f(x')-f(x)-\psi(x)(x'-x)}\|\leq\|{x'-x}\|, \ \forall x, x'\in B(x_0, a).

(iii) \|{z_0}\|\leq\frac{\beta}{2} .

则存在由

\begin{equation} 0\in f(x_n)+{\cal H}(x_n)(x_{n+1}-x_n)+F(x_{n+1}) \end{equation}
(3.4)

产生的序列 \{x_n\} 线性收敛于包含问题(0.1) 的一个解 \bar{x}\in B(x_0, a).

  首先证明存在以 x_0 为初始点的序列 \{x_n\}\subset B(x_0, a) , 使得

(a) \|x_{n+1}-x_n\|\leq\frac{\beta}{3^{n+1}}, \ \forall n\geq 0 .

(b) 0\in f(x_n)+\psi(x_n)(x_{n+1}-x_n)+F(x_{n+1}), \ \forall n\geq 0 .

(c) \|x_{n+1}-x_n\|\leq\frac{2\tau}{1-\tau L}d(0, f(x_n)+F(x_n)) \leq\frac{2\tau}{1-\tau L}\|x_n-x_{n-1}\|, \ \forall n\geq 1 .

0\in f(x_0)+F(x_0) , 则对任意正整数 n , 只需取 x_n=x_0 即可完成证明.

下面假设 0\notin f(x_0)+F(x_0) . 由于 \psi(x_0)\in{\cal H}(x_0) , 且显然有

{\cal H}(x_0)\subset{\cal H}(x_0)+LB_{L(X, Y)},

故存在 H_0\in{\cal H}(x_0), T_0\in LB_{L(X, Y)} 使得

\begin{equation} \psi(x_0)=H_0+T_0. \end{equation}
(3.5)

由定理条件可知映射 \Phi_{H_0} 在集合 B(x_0, a)\times B(z_0, b) 上关于 \tau 度量正则. 构造函数

G_0(x):=T_0(x-x_0), \ \forall x\in X,

G_0(x_0)=0 , 且由 T_0\in LB_{L(X, Y)} 易知 G_0 x_0 处关于 L 局部Lipschitz连续, 且(由(3.1) 式) \tau L<1 , 故取(3.3) 式中 H=H_0, \ g=G_0 , 可知映射 \Phi_{H_0}+G_0 在集合 B(x_0, \beta)\times B(z_0, \beta) 上关于常数 \frac{\tau}{1-\tau L} 度量正则. 由条件(iii) 易知 0\in B(z_0, \frac{\beta}{2}) , 即此时有

(x_0, 0)\in \ B(x_0, \beta)\times B(z_0, \beta).

注意到(由(3.1) 式) \frac{2\tau}{1-\tau L}\leq\frac{1}{3} , 故由 \Phi_{H_0}+G_0 的度量正则性, 有

\begin{eqnarray} d(x_0, (\Phi_{H_0}+G_0)^{-1}(0))\leq\frac{\tau}{1-\tau L}d(0, f(x_0)+F(x_0))<\frac{2\tau}{1-\tau L}\|{z_0}\|\leq\frac{\beta}{3}, \end{eqnarray}
(3.6)

于是存在 x_1\in(\Phi_{H_0}+G_0)^{-1}(0) , 使得

\begin{equation} \|{x_1-x_0}\|<\frac{2\tau}{1-\tau L}d(0, f(x_0)+F(x_0))\leq\frac{\beta}{3}<\beta, \end{equation}
(3.7)

这蕴含(a) 当 n=0 时成立. 而由 x_1\in(\Phi_{H_0}+G_0)^{-1}(0) 结合(3.5) 式可知

\begin{eqnarray} 0\in(\Phi_{H_0}+G_0)(x_1)&=&f(x_0)+H_0(x_1-x_0)+F(x_1)+T_0(x_1-x_0)\\ &=&f(x_0)+\psi(x_0)(x_1-x_0)+F(x_1) \end{eqnarray}
(3.8)

即(b) 当 n=0 时成立.

类似地, 若 0\in f(x_1)+F(x_1) , 则对任意正整数 n>1 , 只需取 x_n=x_1 即可完成证明.

假设 0\notin f(x_1)+F(x_1) . 注意到 \beta<a , 故(3.7) 式蕴含 x_1\in B(x_0, a) , 因此由条件(i) 可知

\psi(x_1)\in{\cal H}(x_1)\subset{\cal H}(x_0)+LB_{L(X, Y)},

故存在 H_1\in{\cal H}(x_1), T_1\in LB_{L(X, Y)} 使得

\begin{equation} \psi(x_1)=H_1+T_1. \end{equation}
(3.9)

同样, 由定理条件可知映射 \Phi_{H_1} 在集合 B(x_0, a)\times B(z_0, b) 上关于 \tau 度量正则. 设

y_1:=f(x_1)-f(x_0)-\psi(x_1)(x_1-x_0),

并构造函数

G_1(x):=T_1(x-x_0)+y_1, \ \forall x\in X,

G_1(x_0)=y_1 , 且由 T_1\in LB_{L(X, Y)} 易知 G_1 x_0 处关于 L 局部Lipschitz连续. 类似地, 取(3.3) 式中 H=H_1, \ g=G_1 , 可知映射 \Phi_{H_1}+G_1 在集合 B(x_0, \beta)\times B(z_0+y_1, \beta) 上关于常数 \frac{\tau}{1-\tau L} 度量正则.

通过 \Phi_{H_1}, G_1 以及 y_1 的构造, 结合(3.9) 式可知

\begin{eqnarray} (\Phi_{H_1}+G_1)(x_1)&=&f(x_0)+H_1(x_1-x_0)+F(x_1)+T_1(x_1-x_0)+y_1\\ &=&f(x_1)+\psi(x_1)(x_1-x_0)+F(x_1)-\psi(x_1)(x_1-x_0)\\ &=&f(x_1)+F(x_1), \end{eqnarray}
(3.10)

于是, 由(3.8) 式以及条件(ii), 有

\begin{eqnarray} d(0, (\Phi_{H_1}+G_1)(x_1))&=&d(0, f(x_1)+F(x_1))=d(-f(x_1), F(x_1))\\ &\leq&\|{f(x_1)-f(x_0)-\psi(x_0)(x_1-x_0)}\|\\ &\leq&\|{x_1-x_0}\|. \end{eqnarray}
(3.11)

结合 x_1\in B(x_0, a), \ y_1 的构造, 条件(ii) 和(iii) 以及(3.7) 式可得

\begin{eqnarray} \label{N-z0+y1} \|{z_0+y_1}\|&\leq&\|{z_0}\|+\|{y_1}\|\\ &\leq&\frac{\beta}{2}+\|{f(x_1)-f(x_0)-\psi(x_1)(x_1-x_0)}\|\\ &\leq&\frac{\beta}{2}+\|{x_1-x_0}\|\leq\frac{\beta}{2}+\frac{\beta}{3}<\beta, \end{eqnarray}

结合(3.7) 式即得到 (x_1, 0)\in B(x_0, \beta)\times B(z_0+y_1, \beta) . 于是, 由 \Phi_{H_1}+G_1 的度量正则性以及(3.10), (3.11) 两式, 有

\begin{eqnarray*} d(x_1, (\Phi_{H_1}+G_1)^{-1}(0))&\leq&\frac{\tau}{1-\tau L}d(0, (\Phi_{H_1}+G_1)(x_1))\nonumber\\ &=&\frac{\tau}{1-\tau L}d(0, f(x_1)+F(x_1))\nonumber\\ &<&\frac{2\tau}{1-\tau L}d(0, f(x_1)+F(x_1))\nonumber\\ &\leq&\frac{2\tau}{1-\tau L}\|{x_1-x_0}\|, \end{eqnarray*}

故存在 x_2\in(\Phi_{H_1}+G_1)^{-1}(0) , 使得

\begin{equation} \|{x_2-x_1}\|<\frac{2\tau}{1-\tau L}d(0, f(x_1)+F(x_1))\leq\frac{2\tau}{1-\tau L}\|{x_1-x_0}\|, \end{equation}
(3.12)

即知(c) 当 n=1 时成立. 结合(3.7), (3.12) 两式以及 \frac{2\tau}{1-\tau L}<\frac{1}{3} , 得

\|{x_2-x_1}\|<\frac{2\tau}{1-\tau L}\|{x_1-x_0}\|<\frac{\beta}{3^2},

即(a) 当 n=1 时成立. 此外, 由 x_2\in(\Phi_{H_1}+G_1)^{-1}(0) , 有

\begin{eqnarray} 0\in(\Phi_{H_1}+G_1)(x_2)&=&f(x_0)+H_1(x_2-x_0)+F(x_2)+T_1(x_2-x_0)+y_1\\ &=&f(x_1)+\psi(x_1)(x_2-x_0)+F(x_2)-\psi(x_1)(x_1-x_0)\\ &=&f(x_1)+\psi(x_1)(x_2-x_1)+F(x_2), \end{eqnarray}
(3.13)

即(b) 当 n=1 时成立.

现假设存在 x_0, x_1, \cdots , x_k , 使得(a), (b) 当 n=0, 1, \cdots , k-1 时成立且(c) 当 n=1, 2, \cdots , k-1 时成立. 若 0\in f(x_k)+F(x_k) , 则对任意正整数 n>k , 只需取 x_n=x_k 则完成证明.

0\notin f(x_k)+F(x_k) , 由三角不等式, 有

\|{x_k-x_0}\|\leq\sum\limits_{n=0}^{k-1}\|{x_{n+1}-x_n}\|\leq\sum\limits_{i=0}^{n-1}\frac{\beta}{3^{n+1}}<\beta<a,

故由条件(i) 可知

\psi(x_k)\in{\cal H}(x_k)\subset{\cal H}(x_0)+LB_{L(X, Y)}.

故存在 H_k\in{\cal H}(x_0), T_k\in LB_{L(X, Y)} 使得

\begin{equation} \psi(x_k)=H_k+T_k. \end{equation}
(3.14)

同样, 由定理条件可知映射 \Phi_{H_k} 在集合 B(x_0, a)\times B(z_0, b) 上关于 \tau 度量正则. 设

y_k:=f(x_k)-f(x_0)-\psi(x_k)(x_k-x_0),

并构造函数

G_k(x):=T_k(x-x_0)+y_k, \ \forall x\in X,

G_k(x_0)=y_k , 且由 T_k\in LB_{L(X, Y)} 易知 G_k x_0 处关于 L 局部Lipschitz连续. 类似地, 取(3.3) 式中 H=H_k, \ g=G_k , 可知映射 \Phi_{H_k}+G_k 在集合 B(x_0, \beta)\times B(z_0+y_k, \beta) 上关于常数 \frac{\tau}{1-\tau L} 度量正则.

x_k\in B(x_0, \beta)\subset B(x_0, a) , 通过 \Phi_{H_k}, G_k, y_k 的构造以及(3.14) 式可知

\begin{eqnarray} (\Phi_{H_k}+G_k)(x_k)&=&f(x_0)+H_k(x_k-x_0)+F(x_k)+T_k(x_k-x_0)+y_k\\ &=&f(x_k)+\psi(x_k)(x_k-x_0)+F(x_k)-\psi(x_k)(x_k-x_0)\\ &=&f(x_k)+F(x_k), \end{eqnarray}
(3.15)

由假设(当 n=k-1 时(b) 成立) 可知

0\in f(x_{k-1})+\psi(x_{k-1})(x_k-x_{k-1})+F(x_k),

于是, 由条件(ii) 得

\begin{eqnarray} d(0, (\Phi_{H_k}+G_k)(x_k))&=&d(0, f(x_k)+F(x_k))=d(-f(x_k), F(x_k))\\ &\leq&\|{f(x_k)-f(x_{k-1})-\psi(x_{k-1})(x_k-x_{k-1})}\|\\ &\leq&\|{x_k-x_{k-1}}\|. \end{eqnarray}
(3.16)

又由假设\ (当 n=k-1 时(a) 成立) 可知当 k\geq 1 时有 \|{x_k-x_{k-1}}\|\leq\frac{\beta}{3^{k}}\leq\frac{\beta}{3} , 因此, 结合 x_k, x_{k-1}\in B(x_0, a), \ y_k 的构造以及条件(ii) 和(iii) 可得

\begin{eqnarray} \|{z_0+y_k}\|&\leq&\|{z_0}\|+\|{y_k}\|\\ &\leq&\frac{\beta}{2}+\|{f(x_k)-f(x_{k-1})-\psi(x_{k-1})(x_k-x_{k-1})}\|\\ &\leq&\frac{\beta}{2}+\|{x_k-x_{k-1}}\|\leq\frac{\beta}{2}+\frac{\beta}{3}<\beta, \end{eqnarray}
(3.17)

B(x_0, \beta)\times B(z_0+y_k, \beta). 于是, 又由 \Phi_{H_k}+G_k 的度量正则性以及(3.16) 式, 有

\begin{eqnarray*} d(x_k, (\Phi_{H_k}+G_k)^{-1}(0))&\leq&\frac{\tau}{1-\tau L}d(0, f(x_k)+F(x_k))\nonumber\\ &<&\frac{2\tau}{1-\tau L}d(0, f(x_k)+F(x_k))\nonumber\\ &<&\frac{2\tau}{1-\tau L}\|{x_k-x_{k-1}}\|, \end{eqnarray*}

故存在 x_{k+1}\in(\Phi_{H_k}+G_k)^{-1}(0) , 使得

\begin{equation} \|{x_{k+1}-x_k}\|<\frac{2\tau}{1-\tau L}d(0, f(x_k)+F(x_k))<\frac{2\tau}{1-\tau L}\|{x_k-x_{k-1}}\|, \end{equation}
(3.18)

即知(c) 当 n=1 时成立. 结合(3.7), (3.18) 两式以及 \frac{2\tau}{1-\tau L}<\frac{1}{3} , 得

\|{x_{k+1}-x_k}\|<\frac{2\tau}{1-\tau L}\|{x_k-x_{k-1}}\|<\frac{\beta}{3^{k+1}},

即(a) 当 n=k 时成立. 此外, 由 x_{k+1}\in(\Phi_{H_k}+G_k)^{-1}(0) , 有

\begin{eqnarray} 0\in(\Phi_{H_k}+G_k)(x_{k+1})&=&f(x_0)+H_k(x_{k+1}-x_0)+F(x_{k+1})+T_k(x_{k+1}-x_0)+y_k\\ &=&f(x_k)+\psi(x_k)(x_{k+1}-x_0)+F(x_{k+1})-\psi(x_k)(x_k-x_0)\\ &=&f(x_k)+\psi(x_k)(x_{k+1}-x_k)+F(x_{k+1}), \end{eqnarray}
(3.19)

即(b) 当 n=k 时成立. 由归纳法原理可知存在序列 \{x_n\}\subset B(x_0, a) 使得(a), (b) 对所有 n\geq 0 成立且(c) 对所有 n\geq 1 成立.

由(a)易知 \{x_n\} 为Cauchy序列, 故存在 \bar{x}\in B(x_0, a) , 使得 x_n\rightarrow \bar{x} . 现说明 \bar{x} 为问题(1.1) 的解. 事实上, 由(c) 以及下确界的性质可知对任意 n\geq 1 , 存在 u_n\in f(x_n)+F(x_n) ( (x_n, u_n)\in{{{\rm{gph}}}}(f+F) ) 使得

\|{u_n}\|<d(0, f(x_n)+F(x_n))+\frac{1}{n}\leq\|{x_n-x_{n-1}}\|+\frac{1}{n},

n\rightarrow \infty , 得 \|{u_n}\|\rightarrow0 , 即 u_n\rightarrow0 , 因此有 (x_n, u_n)\rightarrow (\bar{x}, 0) . f 的连续性以及 F 的闭性易知 f+F 为闭集值映射, 故 (\bar{x}, 0)\in{{{\rm{gph}}}}(f+F) , 即 0\in f(\bar{x})+F(\bar{x}) .

最后证明 \{x_n\} 的线性收敛性. 事实上, 记 \lambda=\frac{2\tau}{1-\tau L} , 则由(3.1) 式知 \lambda<\frac{1}{3} . x_n\rightarrow \bar{x} , 故由(c) 可知对任意正整数 n , 有

\begin{eqnarray*} \|{x_{n+1}-\bar{x}}\|&=&\lim\limits_{m\rightarrow \infty}\|{x_{n+1}-x_{n+m}}\|\leq\lim\limits_{m\rightarrow \infty}\sum\limits_{i=1}^{m-1}\|{x_{n+i}-x_{n+i+1}}\|\\ &\leq&\lim\limits_{m\rightarrow \infty}\sum\limits_{i=1}^{m-1}\lambda^i\|{x_{n+1}-x_n}\|=\frac{\lambda}{1-\lambda}\|{x_{n+1}-x_n}\|\\ &\leq&\frac{\lambda}{1-\lambda}(\|{x_{n+1}-\bar{x}}\|+\|{x_n-\bar{x}}\|), \end{eqnarray*}

\|{x_{n+1}-\bar{x}}\|\leq\frac{\lambda}{1-2\lambda}\|{x_n-\bar{x}}\|.

\lambda<\frac{1}{3} 可知 \frac{\lambda}{1-2\lambda}<1 , 故上式蕴含 \{x_n\} 的线性收敛性.证毕.

定理3.1的条件中假设了映射族 \{\Phi_H\ |\ H\in{\cal H}(x_0)\} 在集合 {\cal H}(x_0) 上不仅具有度量正则性, 且具有一致的(即不依赖于 H {\cal H}(x_0) 中的选取) 度量正则常数以及邻域半径. 下面给出使得这种一致性条件成立的一个充分条件.

命题3.1  设 x_0\in X, z_0\in f(x_0)+F(x_0), {\cal H}:X\rightrightarrows L(X, Y) , 若对任意 H\in {\cal H}(x_0) , 由(3.2) 式所定义的映射 \Phi_H (x_0, z_0) 处局部度量正则, 且

\begin{equation} {\cal X}({\cal H}(x_0))\cdot\sup\limits_{H\in{\cal H}(x_0)}{{{\rm{reg}}}}(\Phi_H;x_0|z_0)<1. \end{equation}
(3.20)

则存在 a, b>0 , 使得对任意 H\in {\cal H}(x_0) , 有

d(x, \Phi_H^{-1}(y))\leq\frac{c}{1-ck}d(y, \Phi_H(x)), \ \forall (x, y)\in B(x_0, a)\times B(z_0, b),

\Phi_H B(x_0, a)\times B(z_0, b) 上关于常数 \frac{c}{1-ck} 局部度量正则.

  由条件(3.20), 可取 { } c>\sup_{H\in{\cal H}(x_0)}{{{\rm{reg}}}}(\Phi_H;x_0|z_0), \ k>{\cal X}({\cal H}(x_0)), 使得 ck<1 . 故由非紧性测度的定义可知存在有限子集 {\cal A}:=\{H_1, \cdots , H_n\}\subset{\cal H}(x_0) , 使得

\begin{equation} {\cal H}(x_0)\subset{\cal A}+kB_{L(X, Y)}. \end{equation}
(3.21)

任取 H_i\in{\cal A}, 由命题条件可知存在 a_i, b_i>0, 使得

d(x, \Phi_{H_i}^{-1}(y))\leq cd(y, \Phi_{H_i}(x)), \ \forall (x, y)\in B(x_0, a_i)\times B(z_0, b_i).

{ } a':=\min_{1\leq i\leq n}\{a_i\}, \ b':=\min_{1\leq i\leq n}\{b_i\}, 则可知 \Phi_{H_i} 在集合在 B(x_0, a')\times B(z_0, b') 上关于常数 c 度量正则.

现任给 H\in{\cal H}(x_0) , 由(3.21) 式可知存在 H_i\in{\cal A} 使得 \|{H-H_i}\|\leq k . 构造函数 G:X\rightarrow Y G(x):=(H-H_i)(x-x_0), \ x\in X, 则易知 G(x_0)=0 G x_0 处关于 k 局部Lipschitz连续, 故由引理1.1可知存在 a, b>0 使得 \Phi_H=\Phi_{H_i}+G 在集合 B(x_0, a)\times B(z_0, b) 上关于常数 \frac{c}{1-ck} 度量正则.证毕.

4 结论

本文通过利用集值映射的度量正则性, 证明了非光滑牛顿算法的两个收敛性结果. 所得到的局部收敛性结果通过利用集合族的非紧性测度, 削弱了文献[1, 定理4.3] 的紧性条件. 同时, 通过将所有假设条件均施加于算法的初始点, 得到了非光滑牛顿算法的一个全局情形的收敛性结果.

参考文献

Adly S , Cibulka R , Ngai H V .

Newton's method for solving inclusions using set-valued approximations

SIAM J Optim, 2015, 25 (1): 159- 184

DOI:10.1137/130926730      [本文引用: 10]

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, 2016, 439 (1): 396- 418

DOI:10.1016/j.jmaa.2016.02.047     

Adly S , Ngai H V , Vu N V .

Stability of metric regularity with set-valued perturbations and application to Newton's method for solving generalized equations

Set-Valued Var Anal, 2017, 25 (3): 543- 567

DOI:10.1007/s11228-017-0438-3     

Dontchev A L , Rockafellar R T .

Newton's method for generalized equations: A sequential implicit function theorem

Math Program, 2010, 123 (1): 139- 159

DOI:10.1007/s10107-009-0322-5     

Geoffroy M H .

Stability of Mann's iterates under metric regularity

Appl Math Comput, 2009, 215 (2): 686- 694

Aragón Artacho F J , Dontchev A L , Gaydu M , Geoffroy M H , Veliov V M .

Metric regularity of Newton's iteration

SIAM J Control Optim, 2011, 49 (2): 339- 362

DOI:10.1137/100792585      [本文引用: 2]

Rashid M H , Yuan Y X .

Metrically regular mappings and its application to convergence analysis of a confined Newton-type method for nonsmooth generalized equations

SCI China Math, 2020, 63 (1): 39- 60

DOI:10.1007/s11425-019-9757-0      [本文引用: 1]

Aragón Artacho F J , Dontchev A L , Geoffroy M H .

Convergence of the proximal point method for metrically regular mappings

ESAIM Proc, 2007, 17, 1- 8

DOI:10.1051/proc:071701     

Aragón Artacho F J , Gaydu M .

A Lyusternik-Graves theorem for the proximal point method

Comput Optim Appl, 2012, 52 (3): 785- 803

DOI:10.1007/s10589-011-9439-6     

Aragón Artacho F J , Geoffroy M H .

Uniformity and inexact version of a proximal method for metrically regular mappings

J Math Anal Appl, 2007, 335 (1): 168- 183

DOI:10.1016/j.jmaa.2007.01.050      [本文引用: 1]

Dontchev A L , Rockafellar R T . Implicit Functions and Solution Mappings. New York: Springer, 2014

[本文引用: 6]

Ioffe A D .

Metric regularity and subdifferential calculus

Uspekhi Mat Nauk, 2000, 55 (3): 103- 162

DOI:10.4213/rm292     

Ioffe A D .

Metric regularity - a survey, Part 1 Theory

J Aust Math Soc, 2016, 101 (2): 188- 243

DOI:10.1017/S1446788715000701     

Ioffe A D .

Metric regularity - a survey, Part 2 Applications

J Aust Math Soc, 2016, 101 (3): 376- 417

DOI:10.1017/S1446788715000695      [本文引用: 1]

Cibulka R , Dontchev A L , Preininger J , Veliov V , Roubal T .

Kantorovich-type theorems forgeneralized equations

J Convex Anal, 2018, 25 (2): 459- 486

[本文引用: 2]

Dontchev A L .

Local analysis of a Newton-type method based on partial linearization

Lect Appl Math, 1996, 32, 295- 306

Geoffroy M H , Piétrus A .

A general iterative procedure for solving nonsmooth generalized equations

Comput Optim Appl, 2005, 31 (1): 57- 67

DOI:10.1007/s10589-005-1104-5      [本文引用: 1]

Cibulka R , Dontchev A L , Geoffroy M H .

Inexact Newton methods and Dennis-Mor'e theorems for nonsmooth generalized equations

SIAM J Control Optim, 2015, 53 (2): 1003- 1019

DOI:10.1137/140969476      [本文引用: 1]

Dontchev A L , Rockafellar R T .

Convergence of inexact Newton methods for generalized equations

Math Program Ser B, 2013, 139 (1): 115- 137

Cibulka R , Fabian M , Kruger A Y .

On semiregularity of mappings

J Math Anal Appl, 2019, 473 (2): 811- 836

DOI:10.1016/j.jmaa.2018.12.071      [本文引用: 1]

Dontchev A L , Lewis A S , Rockafellar R T .

The radius of metric regularity

Trans Amer Math Soc, 2003, 335 (2): 493- 517

[本文引用: 1]

Dontchev A L .

The Graves theorem revisited

J Convex Anal, 1996, 3 (1): 45- 53

Dontchev A L .

A proof of the Lyusternik-Graves theorem

Optimization, 2015, 64 (1): 41- 48

DOI:10.1080/02331934.2014.926359     

Dontchev A L , Frankowska H .

Lyusternik-Graves theorem and fixed points

Proc Amer Math Soc, 2010, 139 (2): 521- 534

Dontchev A L , Lewis A S .

Perturbations and metric regularity

Set-Valued Anal, 2005, 13 (4): 417- 438

DOI:10.1007/s11228-005-4404-0     

He Y R , Ng K F .

Stability of p-order metric regularity

Vietnam J Math, 2018, 46 (2): 285- 291

DOI:10.1007/s10013-018-0281-3      [本文引用: 1]

Páles Z .

Inverse and implicit function theorems for nonsmooth maps in Banach spaces

J Math Anal Appl, 1997, 209 (1): 202- 220

DOI:10.1006/jmaa.1997.5358      [本文引用: 1]

/