非扩张映射的广义修正两步惯性Mann Halpern算法

Generalized Modified Two-Step Inertial Mann Halpern Algorithm for Nonexpansive Mappings

摘要: 受广义Krasnoselskii-Mann算法和两步惯性项应用的启发，本文提出了一种求解非扩张映射不动点问题的广义修正两步惯性Mann Halpern算法。在一定合适的条件下，本文证明了算法的强收敛性。在数值实验中，本文将算法用于解决凸可行问题。数值结果表明，在某些情况下，该算法更具优势。

Abstract: Motivated by the application generalized Krasnoselskii-Mann algorithm and two-step inertial extrapolation, this paper proposes a generalized modified two-step inertial Mann Halpern algorithm for solving fixed point problems with nonexpansive mapping. Under mild assumptions, the strong convergence of the proposed method are established. In numerical experiment, a convex feasibility problem is solved. Numerical results demonstrate that our algorithm has advantages in some cases.

1. 引言

设$\mathscr{H}$ 是一个实Hilbert空间，$\langle \cdot ,\cdot \rangle$ 和$\Vert \cdot \Vert$ 分别为其内积及诱导的范数。设$C$ 是$\mathscr{H}$ 的一个非空闭凸子集。映射$T:C\to C$ 称为非扩张的，即

$\Vert T\left(x\right)-T\left(y\right)\Vert \le \Vert x-y\Vert ,\forall x,y\in C$ .

集合$\mathrm{Fix}\left(T\right):=\left\{x\in C|T\left(x\right)=x\right\}$ 代表映射$T$ 的不动点集。

本文我们主要考虑如下不动点问题：寻找$x^{*}\in C$ ，使得$T\left(x^{*}\right)=x^{*}$ ，其中$T$ 是不动点非空的非扩张映射。求解非扩张映射不动点问题是优化理论、非线性分析及其在信号处理、机器学习等领域应用中的一个核心课题。经典的求解不动点的方法有Picard迭代算法。但该算法仅适用于压缩映射，对于非扩张映射可能不收敛。

一种著名的求解非扩张映射不动点方法是Krasnoselskii-Mann迭代[1]-[3] (之后简称为KM迭代)。选定初始点$x_0\in C$ ，该迭代更新步骤为：

$x_{n+1}={\alpha }_n{x}_n+\left(1-{\alpha }_n\right)T\left(x_n\right)$ , (1)

其中，${\alpha }_n\in \left(0,1\right)$ ，由(1)所定义的序列$\left\{x_n\right\}$ 在${\displaystyle \sum _{n=0}^{\infty }{\alpha }_n}\left(1-{\alpha }_n\right)=+\infty$ 的条件下弱收敛于$T$ 的不动点。

基于上述KM迭代，Kanzow [4]等人于2017年进一步提出了广义KM迭代，给定初始点$x_0\in C$ ，迭代步骤为：

$x_{n+1}={\alpha }_n{x}_n+{\beta }_{n}T\left(x_n\right)+e_n$ , (2)

其中，${\alpha }_n,{\beta }_n\in \left[0,1\right]$ ，${\alpha }_n+{\beta }_n\le 1$ ，$\left\{e_n\right\}$ 被称为残差向量。由(2)定义的序列$\left\{x_n\right\}$ 弱收敛于$T$ 的不动点的充分条件为：${\displaystyle \sum _{n=0}^{\infty }{\alpha }_n}{\beta }_n=+\infty$ ，${\displaystyle \sum _{n=0}^{\infty }\Vert e_n\Vert }<+\infty$ 及${\displaystyle \sum _{n=0}^{\infty }\left(1-{\alpha }_n-{\beta }_n\right)}<+\infty$ 。

Halpern迭代是另一种求解非扩张映射不动点的有效方法。它最早于1967年由Halpern [5]提出。关于Halpern迭代进一步的研究见文献[6]-[9]。基于KM迭代和Halpern迭代，Kim和Xu [10]提出了一种修正Mann迭代并证明了该算法的强收敛性。其主要步骤如下：

$\{\begin{array}{l}{y}_n={\lambda }_n{x}_n+\left(1-{\lambda }_n\right)T\left(x_n\right)\hfill \\ x_{n+1}={\alpha }_{n}u+\left(1-{\alpha }_n\right)T\left(y_n\right),\hfill \end{array}$ (3)

其中，$u,x_0\in C$ ，${\alpha }_n,{\lambda }_n\in \left(0,1\right)$ 。该迭代的收敛性条件见文献[10]。

一般而言，Mann迭代的收敛速率是比较慢的。惯性加速是一种著名的加快收敛速率的方法，它最早由Polyak [11]提出。Mainge [12]首次提出了惯性Mann算法，该算法由KM迭代和惯性加速结合。惯性加速也被用于分裂算法中，例如惯性Douglas-Rachford分裂算法[13]和惯性前向后向分裂算法[14]。Tan [15]等人通过引入惯性项改进了算法(3)，提出了一种修正惯性Mann Halpern算法，其迭代形式为：

$\{\begin{array}{l}{w}_n=x_n+{\alpha }_n\left(x_n-x_{n-1}\right)\hfill \\ y_n={\lambda }_n{w}_n+\left(1-{\lambda }_n\right)T\left(w_n\right)\hfill \\ x_{n+1}={\theta }_{n}u+\left(1-{\theta }_n\right)y_n\hfill \end{array}$ (4)

其中，$x_0,x_1,u\in C$ ，${\lambda }_n,{\theta }_n\in \left(0,1\right)$ 。由算法(4)定义的序列$\left\{x_n\right\}$ 在一定条件下是强收敛的，具体细节见文献[15]。

除了一步惯性以外，多步惯性加速也被一些研究者讨论。Iyiola [16]等曾指出一步惯性在某些可行性问题下可能存在加速失败的情况。在文献[16]中，他们提出了两步惯性临近点算法并证明了算法的弱收敛性。在[16]的数值实验中，两步惯性临近点算法比一步惯性临近点算法收敛更快。这表明两步惯性的应用是有意义的。两步惯性可表示为：

$x_{n+1}=x_n+{\alpha }_n\left(x_n-x_{n-1}\right)+{\beta }_n\left(x_{n-1}-x_{n-2}\right)$ ,

其中${\alpha }_n>0$ ，${\beta }_n<0$ 。

受Kanzow [4]和Iyiola [16]启发，本文推广了Tan [15]提出的算法，提出了广义修正两步惯性Mann Halpern算法：

$\{\begin{array}{l}{w}_n=x_n+{\alpha }_n\left(x_n-x_{n-1}\right)+{\beta }_n\left(x_{n-1}-x_{n-2}\right)\hfill \\ y_n=u_n{w}_n+v_{n}T\left(w_n\right)+e_n\hfill \\ x_{n+1}={\theta }_{n}u+\left(1-{\theta }_n\right)y_n\hfill \end{array}$ (5)

其中，$x_0,x_1,x_2,u\in C$ ，${\alpha }_n,u_n,v_n,e_n,{\theta }_n\in \left(0,1\right)$ ，${\beta }_n\in \left(-1,0\right]$ 且$u_n+v_n\le \text{1}$ 。算法(5)在算法(4)的基础上添加了两步惯性项并推广了Mann迭代步的系数，在取值上更为灵活。

本文的结构如下：在第二节，我们会给出一些证明定理所用到的引理。在第三节，我们将证明在一定条件下广义修正两步惯性Mann Halpern算法的强收敛性。在第四节，我们将用算法(4)和算法(5)去求解凸可行问题并比较它们的表现。

本文中，序列$\left\{x_n\right\}$ 强收敛于$x^{*}$ 记为$x_n\to x^{*}$ ，序列$\left\{x_n\right\}$ 弱收敛于$x^{*}$ 记为$x_n\rightharpoonup x^{*}$ 。本文中，均假设$T$ 是非扩张的且$\mathrm{Fix}\left(T\right)\ne \varnothing$ 。符号${\Pi }_C\left(x\right)$ 表示实Hilbert空间中$x$ 在集合$C$ 上的投影，即${\Pi }_C\left(x\right):=\underset{y\in C}{\arg \min }\Vert x-y\Vert$ 。

2. 预备知识

本节将给出一些后续证明所需要的引理。

引理1. $\forall x,y\in \mathscr{H}$ ，有以下事实：

1) ${\Vert x+y\Vert }^2\le {\Vert x\Vert }^2+2\langle y,x+y\rangle$ ；

2) ${\Vert sx+ty\Vert }^2=s\left(s+t\right){\Vert x\Vert }^2+t\left(s+t\right){\Vert y\Vert }^2-st{\Vert x-y\Vert }^2$ ，$\forall s,t\in ℝ$ ；

3) ${\Vert x+y\Vert }^2\le 2\left({\Vert x\Vert }^2+{\Vert y\Vert }^2\right)$ 。

引理2. [17]设$C$ 是实Hilbert空间$\mathscr{H}$ 中的一个非空闭凸集，$T$ ：$C\to C$ 是一个非扩张映射，$x^{*}\in \mathscr{H}$ 。$C$ 中的序列$\left\{x_n\right\}$ 满足$n\to +\infty$ 时，$x_n\rightharpoonup x^{*}$ 且$T\left(x_n\right)-x_n\to 0$ ，则$x^{*}\in \mathrm{Fix}\left(T\right)$ 。

引理3. [14]设$\left\{b_n\right\}$ 是非负实序列且满足：

$b_{n+1}\le \left(1-{\gamma }_n\right)b_n+{\gamma }_n{\delta }_n$ 及$b_{n+1}\le b_n-t_n+q_n$ ，

其中，$\left\{{\gamma }_n\right\}$ 是(0，1)的序列，$\left\{t_n\right\}$ 是非负实序列。若实序列$\left\{{\delta }_n\right\}$ ，$\left\{q_n\right\}$ 满足以下三个条件：

1) ${\displaystyle \sum _{n=0}^{\infty }{\gamma }_n}=+\infty$ ，

2) $\underset{n\to +\infty }{\lim }{q}_n=0$ ，

3) $\left\{t_n\right\}$ 的任意子序列$\left\{t_{n_k}\right\}$ 满足$\underset{k\to +\infty }{\lim }{t}_{n_k}=0$ 蕴含$\underset{k\to +\infty }{\lim \sup }{\delta }_{n_k}\le 0$ 。

则$\underset{n\to +\infty }{\lim }{b}_n=0$ 。

3. 算法及收敛性分析

本节将分析在一定条件下广义修正两步惯性Mann Halpern算法的强收敛性。我们再给出广义修正两步惯性Mann Halpern算法的迭代步骤：

$\{\begin{array}{l}{w}_n=x_n+{\alpha }_n\left(x_n-x_{n-1}\right)+{\beta }_n\left(x_{n-1}-x_{n-2}\right)\hfill \\ y_n=u_n{w}_n+v_{n}T\left(w_n\right)+e_n\hfill \\ x_{n+1}={\theta }_{n}u+\left(1-{\theta }_n\right)y_n\hfill \end{array}$ (6)

定理3.1：设$C$ 是实Hilbert空间$\mathscr{H}$ 中的一个非空闭凸集，$T:C\to C$ 是一个非扩张映射且$T$ 至少有一个不动点。取$u\in C$ ，序列${\alpha }_n,u_n,v_n,e_n,{\theta }_n\in \left(0,1\right),{\beta }_n\in \left(-1,0\right]$ 且$u_n+v_n\le \text{1}$ 。若下述条件成立：

(C₁) $\underset{n\to +\infty }{\lim }{\theta }_n=0,{\displaystyle \sum _{n=0}^{+\infty }{\theta }_n}=+\infty$ ，

(C₂) $\underset{n\to +\infty }{\lim }\frac{{\alpha }_n\Vert x_n-x_{n-1}\Vert }{{\theta }_n}=0,\underset{n\to +\infty }{\lim }\frac{{\beta }_n\Vert x_{n-1}-x_{n-2}\Vert }{{\theta }_n}=0$ ，

(C₃) $\underset{n\to +\infty }{\lim }\frac{1-u_n-v_n}{{\theta }_n}=0,{\displaystyle \sum _{n=0}^{\infty }\left(1-u_n-v_n\right)}<+\infty$ 且$\underset{n\ge 1}{\inf }{u}_n>0,\underset{n\ge 1}{\inf }{v}_n>0$ ，

(C₄) ${\displaystyle \sum _{n=0}^{\infty }\Vert e_n\Vert }<+\infty ,\underset{n\to +\infty }{\lim }\frac{\Vert e_n\Vert }{{\theta }_n}=0$ 。

对于$x_0,x_1,x_2\in C$ 。由算法(6)生成的序列$\left\{x_n\right\}$ 强收敛于$p={\Pi }_{\mathrm{Fix}\left(T\right)}\left(u\right)$ 。

证明：我们先证明$\left\{x_n\right\},\left\{y_n\right\},\left\{w_n\right\},\left\{T\left(w_n\right)\right\}$ 有界。取$p\in \mathrm{Fix}\left(T\right)$ ，则

$\Vert x_{n+1}-p\Vert =\Vert {\theta }_n\left(u-p\right)+\left(1-{\theta }_n\right)\left(y_n-p\right)\Vert \le {\theta }_n\Vert u-p\Vert +\left(1-{\theta }_n\right)\Vert y_n-p\Vert$ . (7)

由(7)得，

$\begin{array}{c}\Vert y_n-p\Vert =\Vert u_n\left(w_n-p\right)+v_n\left(T\left(w_n\right)-p\right)+e_n-\left(1-u_n-v_n\right)p\Vert \\ \le u_n\Vert w_n-p\Vert +v_n\Vert T\left(w_n\right)-p\Vert +\Vert e_n-\left(1-u_n-v_n\right)p\Vert \\ \le \Vert w_n-p\Vert +\left(1-u_n-v_n\right)\Vert e_n-p\Vert +\left(u_n+v_n\right)\Vert e_n\Vert \end{array}$ (8)

第二个不等式成立是因为$T$ 是非扩张的且$u_n+v_n\le 1$ 。除此之外，

$\begin{array}{c}\Vert w_n-p\Vert =\Vert x_n+{\alpha }_n\left(x_n-x_{n-1}\right)+{\beta }_n\left(x_{n-1}-x_{n-2}\right)-p\Vert \\ \le \Vert x_n-p\Vert +{\alpha }_n\Vert x_n-x_{n-1}\Vert +\left|{\beta }_n\right|\Vert x_{n-1}-x_{n-2}\Vert \end{array}$ (9)

将(8)和(9)代入(7)式得到，

$\begin{array}{c}\Vert x_{n+1}-p\Vert \le \left(1-{\theta }_n\right)\Vert x_n-p\Vert +{\theta }_n\left(\Vert u-p\Vert +\frac{{\alpha }_n}{{\theta }_n}\left(1-{\theta }_n\right)\Vert x_n-x_{n-1}\Vert +\frac{\left|{\beta }_n\right|}{{\theta }_n}\left(1-{\theta }_n\right)\Vert x_{n-1}-x_{n-2}\Vert \right)\\ +\left(1-{\theta }_n\right)\left(1-u_n-v_n\right)\Vert e_n-p\Vert +\left(1-{\theta }_n\right)\left(u_n+v_n\right)\Vert e_n\Vert \end{array}$

由条件(C₂)，我们可以推得$\underset{n\ge 0}{\text{sup}}\left\{\frac{{\alpha }_n}{{\theta }_n}\left(1-{\theta }_n\right)\Vert x_n-x_{n-1}\Vert +\frac{\left|{\beta }_n\right|}{{\theta }_n}\left(1-{\theta }_n\right)\Vert x_{n-1}-x_{n-2}\Vert \right\}$ 可以足够小，设

$M=2\text{max}\left\{\Vert u-p\Vert ,\underset{n\ge 0}{\text{sup}}\left\{\frac{{\alpha }_n}{{\theta }_n}\left(1-{\theta }_n\right)\Vert x_n-x_{n-1}\Vert +\frac{\left|{\beta }_n\right|}{{\theta }_n}\left(1-{\theta }_n\right)\Vert x_{n-1}-x_{n-2}\Vert \right\}\right\}$ ,

则$M<+\infty$ 。又由于$u_n+v_n\le \text{1}$ ，我们得到，

$\begin{array}{c}\Vert x_{n+1}-p\Vert \le \left(1-{\theta }_n\right)\Vert x_n-p\Vert +{\theta }_{n}M+\left(1-u_n-v_n\right)\Vert e_n-p\Vert +\Vert e_n\Vert \\ \le \text{max}\left\{\Vert x_n-p\Vert ,M\right\}+\left(1-u_n-v_n\right)\Vert e_n-p\Vert +\Vert e_n\Vert \end{array}$

进而，

$\Vert x_{n+1}-p\Vert \le \cdots \le \text{max}\left\{\Vert x_0-p\Vert ,M\right\}+{\displaystyle \sum _{i=0}^n\left(1-u_i-v_i\right)}\Vert e_i-p\Vert +{\displaystyle \sum _{i=0}^n\Vert e_i\Vert }$ .

结合条件(C₃)和条件(C₄)可得，

${\displaystyle \sum _{i=0}^n\left(1-u_i-v_i\right)}\Vert e_i-p\Vert \le {\displaystyle \sum _{i=0}^n\left(1-u_i-v_i\right)}\left(\Vert e_i\Vert +\Vert p\Vert \right)<+\infty$ .

则$\left\{x_n-p\right\},\left\{x_n\right\}$ 有界。又由于，

$\begin{array}{c}\Vert w_n\Vert =\Vert x_n+{\alpha }_n\left(x_n-x_{n-1}\right)+{\beta }_n\left(x_{n-1}-x_{n-2}\right)\Vert \\ \le \Vert x_n\Vert +{\alpha }_n\Vert x_n-x_{n-1}\Vert +\left|{\beta }_n\right|\Vert x_{n-1}-x_{n-2}\Vert \end{array}$

结合条件(C₁)和条件(C₂)，可以推得${\alpha }_n\Vert x_n-x_{n-1}\Vert$ 是有限的。类似地，${\beta }_n\Vert x_{n-1}-x_{n-2}\Vert$ 也是有限的，从而$\left\{w_n\right\},\left\{w_n-p\right\}$ 是有界的。$T$ 是非扩张的，则$\Vert T\left(w_n\right)-p\Vert \le \Vert w_n-p\Vert$ ，这说明$\left\{T\left(w_n\right)\right\},\left\{y_n\right\}$ 是有界的。

接下来，我们将证明$\left\{x_n\right\}$ 强收敛于$p={\Pi }_{\mathrm{Fix}\left(T\right)}\left(u\right)$ 。由$x_n$ 的定义及引理1(1)可得，

$\begin{array}{c}{\Vert x_{n+1}-p\Vert }^2={\Vert \left(1-{\theta }_n\right)\left(y_n-p\right)+{\theta }_n\left(u-p\right)\Vert }^2\\ \le {\left(1-{\theta }_n\right)}^2{\Vert y_n-p\Vert }^2+2\langle {\theta }_n\left(u-p\right),x_{n+1}-p\rangle \\ \le \left(1-{\theta }_n\right){\Vert y_n-p\Vert }^2+2{\theta }_n\langle \left(u-p\right),x_{n+1}-p\rangle \end{array}$ (10)

再由$y_n$ 的定义及引理1(1)，(2)可知，

$\begin{array}{c}{\Vert y_n-p\Vert }^2={\Vert u_n\left(w_n-p\right)+v_n\left(T\left(w_n\right)-p\right)+e_n-\left(1-u_n-v_n\right)p\Vert }^2\\ \le {\Vert u_n\left(w_n-p\right)+v_n\left(T\left(w_n\right)-p\right)\Vert }^2+2\langle \left(u_n+v_n-1\right)p+e_n,y_n-p\rangle \\ =u_n\left(u_n+v_n\right){\Vert w_n-p\Vert }^2+v_n\left(u_n+v_n\right){\Vert T\left(w_n\right)-p\Vert }^2-u_n{v}_n{\Vert w_n-T\left(w_n\right)\Vert }^2\\ +2\left(u_n+v_n-1\right)\langle p,y_n-p\rangle +2\langle e_n,y_n-p\rangle \\ \le {\Vert w_n-p\Vert }^2-u_n{v}_n{\Vert w_n-T\left(w_n\right)\Vert }^2+2\left(u_n+v_n-1\right)\langle p,y_n-p\rangle +2\langle e_n,y_n-p\rangle \end{array}$ (11)

(11)式中的第二个不等式是因为$T$ 是非扩张且$u_n+v_n\le \text{1}$ 。为方便讨论，我们记

${\varphi }_n:=2\left(u_n+v_n-1\right)\langle p,y_n-p\rangle +2\langle e_n,y_n-p\rangle$ .

由$w_n$ 的定义知，

$\begin{array}{c}{\Vert w_n-p\Vert }^2={\Vert x_n+{\alpha }_n\left(x_n-x_{n-1}\right)+{\beta }_n\left(x_{n-1}-x_{n-2}\right)-p\Vert }^2\\ ={\Vert x_n-p\Vert }^2+{\Vert {\alpha }_n\left(x_n-x_{n-1}\right)+{\beta }_n\left(x_{n-1}-x_{n-2}\right)\Vert }^2+2\langle {\alpha }_n\left(x_n-x_{n-1}\right)+{\beta }_n\left(x_{n-1}-x_{n-2}\right),x_n-p\rangle \\ \le {\Vert x_n-p\Vert }^2+2{\alpha }_n^2{\Vert x_n-x_{n-1}\Vert }^2+2{\beta }_n^2{\Vert x_{n-1}-x_{n-2}\Vert }^2+2\langle w_n-x_n,x_n-p\rangle \\ {\Vert x_n-p\Vert }^2+2{\Vert w_n-x_n\Vert }^2-4{\alpha }_n{\beta }_n\langle x_n-x_{n-1},x_{n-1}-x_{n-2}\rangle +2\langle w_n-x_n,x_n-p\rangle \\ \le {\Vert x_n-p\Vert }^2+2\langle w_n-x_n,w_n-p\rangle -4{\alpha }_n{\beta }_n\Vert x_n-x_{n-1}\Vert \cdot \Vert x_{n-1}-x_{n-2}\Vert \\ \le {\Vert x_n-p\Vert }^2+2\Vert w_n-p\Vert \left({\alpha }_n\Vert x_n-x_{n-1}\Vert +\left|{\beta }_n\right|\Vert x_{n-1}-x_{n-2}\Vert \right)-4{\alpha }_n{\beta }_n\Vert x_n-x_{n-1}\Vert \cdot \Vert x_{n-1}-x_{n-2}\Vert \end{array}$ (12)

第一个和第二个不等式分别由引理1 (3)和Cauchy-Schwarz不等式得到。注意到${\beta }_n<0$ ，将等式(11)和(12)代入(10)可得，

$\begin{array}{c}{\Vert x_{n+1}-p\Vert }^2\le \left(1-{\theta }_n\right){\Vert x_n-p\Vert }^2+2\left(1-{\theta }_n\right)\Vert w_n-p\Vert \left({\alpha }_n\Vert x_n-x_{n-1}\Vert +\left|{\beta }_n\right|\Vert x_{n-1}-x_{n-2}\Vert \right)\\ -4{\alpha }_n{\beta }_n\left(1-{\theta }_n\right)\Vert x_n-x_{n-1}\Vert \cdot \Vert x_{n-1}-x_{n-2}\Vert +2{\theta }_n\langle u-p,x_{n+1}-p\rangle \\ -\left(1-{\theta }_n\right)u_n{v}_n{\Vert w_n-T\left(w_n\right)\Vert }^2+\left(1-{\theta }_n\right){\varphi }_n\end{array}$ $$ (13)

又因为${\theta }_n,{\lambda }_n\subset \left(0,1\right)$ ，可以进一步得到

$\begin{array}{c}{\Vert x_{n+1}-p\Vert }^2\le \left(1-{\theta }_n\right){\Vert x_n-p\Vert }^2+2\Vert w_n-p\Vert \left({\alpha }_n\Vert x_n-x_{n-1}\Vert +\left|{\beta }_n\right|\Vert x_{n-1}-x_{n-2}\Vert \right)\\ -4{\alpha }_n{\beta }_n\Vert x_n-x_{n-1}\Vert \cdot \Vert x_{n-1}-x_{n-2}\Vert +2{\theta }_n\langle u-p,x_{n+1}-p\rangle +\left(1-{\theta }_n\right){\varphi }_n\end{array}$ (14)

以及

$\begin{array}{c}{\Vert x_{n+1}-p\Vert }^2\le {\Vert x_n-p\Vert }^2+2\Vert w_n-p\Vert \left({\alpha }_n\Vert x_n-x_{n-1}\Vert +\left|{\beta }_n\right|\Vert x_{n-1}-x_{n-2}\Vert \right)-4{\alpha }_n{\beta }_n\Vert x_n-x_{n-1}\Vert \cdot \Vert x_{n-1}-x_{n-2}\Vert \\ +2{\theta }_n\langle u-p,x_{n+1}-p\rangle -\left(1-{\theta }_n\right)u_n{v}_n{\Vert w_n-T\left(w_n\right)\Vert }^2+\left(1-{\theta }_n\right){\varphi }_n\end{array}$ (15)

令$b_n={\Vert x_n-p\Vert }^2,{\gamma }_n={\theta }_n,t_n=\left(1-{\theta }_n\right)u_n{v}_n{\Vert w_n-T\left(w_n\right)\Vert }^2$ ，

$\begin{array}{c}{q}_n=2\Vert w_n-p\Vert \left({\alpha }_n\Vert x_n-x_{n-1}\Vert +\left|{\beta }_n\right|\Vert x_{n-1}-x_{n-2}\Vert \right)-4{\alpha }_n{\beta }_n\Vert x_n-x_{n-1}\Vert \cdot \Vert x_{n-1}-x_{n-2}\Vert \\ +2{\theta }_n\langle u-p,x_{n+1}-p\rangle +\left(1-{\theta }_n\right){\varphi }_n\end{array}$

${\delta }_n={\theta }_n{q}_n$ ,

因为

$0\le \left|2{\theta }_n\langle u-p,x_{n+1}-p\rangle \right|\le 2{\theta }_n\Vert u-p\Vert \cdot \Vert x_{n+1}-p\Vert$ ,

$\Vert {\varphi }_n\Vert \le 2\left|u_n+v_n-1\right|\cdot \Vert p\Vert \cdot \Vert y_n-p\Vert +2\Vert e_n\Vert \cdot \Vert y_n-p\Vert$ ,

且$\left\{x_n-p\right\},\left\{y_n-p\right\},\left\{w_n-p\right\}$ 有界，结合条件(C₁)，(C₂)，(C₃)，(C₄)可以得到，

${\displaystyle \sum _{n=0}^{\infty }{\gamma }_n}=+\infty$ , $\underset{n\to +\infty }{\lim }{q}_n=0$ .

从而，引理3的前两个条件满足。只需证明$\underset{k\to +\infty }{\lim }{t}_{n_k}=0$ 蕴含$\underset{k\to +\infty }{\lim \sup }{\delta }_{n_k}\le 0$ ，$\left\{t_{n_k}\right\}$ 为$\left\{t_n\right\}$ 的任意子序列。

取$\left\{t_n\right\}$ 的一个子序列$\left\{t_{n_k}\right\}$ 满足$\underset{k\to +\infty }{\lim }{t}_{n_k}=0$ 。由条件(C₃)可知，

$\underset{k\to +\infty }{\lim }\Vert w_{n_k}-T\left(w_{n_k}\right)\Vert =0$ . (16)

由条件(C₂)，取$k\to +\infty$ ，有

$\begin{array}{c}\Vert w_{n_k}-x_{n_k}\Vert =\Vert x_{n_k}+{\alpha }_{n_k}\left(x_{n_k}-x_{n_k-1}\right)+{\beta }_{n_k}\left(x_{n_k-1}-x_{n_k-2}\right)-x_{n_k}\Vert \\ \le {\alpha }_{n_k}\Vert x_{n_k}-x_{n_k-1}\Vert +\left|{\beta }_{n_k}\right|\Vert x_{n_k-1}-x_{n_k-2}\Vert \to 0\end{array}$ (17)

因为$\left\{x_{n_k}\right\}$ 有界，则存在$\left\{x_{n_k}\right\}$ 的子序列$\left\{x_{n_{k_l}}\right\}$ 满足

$x_{n_{k_l}}\rightharpoonup x^{*}\left(l\to +\infty \right)$ 且$\underset{k\to +\infty }{\lim \sup }\langle u-p,x_{n_k}-p\rangle =\underset{l\to +\infty }{\lim }\langle u-p,x_{n_{k_l}}-p\rangle$ 。

由(17)可知$w_{n_{k_l}}\rightharpoonup x^{*}\left(l\to +\infty \right)$ 。结合(16)及引理2可推得$x^{*}\in \mathrm{Fix}\left(T\right)$ 。再由$p={\Pi }_{\mathrm{Fix}\left(T\right)}\left(u\right)$ 及投影的性质可得$\langle u-p,x^{*}-p\rangle \le 0$ ，这意味着

$\underset{k\to +\infty }{\lim \sup }\langle u-p,x_{n_k}-p\rangle =\underset{l\to +\infty }{\lim }\langle u-p,x_{n_{k_l}}-p\rangle =\langle u-p,x^{*}-p\rangle \le 0$ . (18)

除此以外，

$\begin{array}{c}\Vert y_{n_k}-w_{n_k}\Vert =\Vert v_{n_k}\left(T\left(w_{n_k}\right)-w_{n_k}\right)+\left(u_{n_k}+v_{n_k}-1\right)w_{n_k}+e_{n_k}\Vert \\ \le v_{n_k}\Vert T\left(w_{n_k}\right)-w_{n_k}\Vert +\left(1-u_{n_k}-v_{n_k}\right)\Vert w_{n_k}\Vert +\Vert e_{n_k}\Vert \end{array}$

由，条件(C₃)，(C₄)，可以推得$\underset{k\to +\infty }{\lim }\Vert y_{n_k}-w_{n_k}\Vert =0$ 。结合(18)可知，$\underset{k\to +\infty }{\lim }\Vert y_{n_k}-x_{n_k}\Vert =0$ 。因为，

$\Vert x_{n_k+1}-x_{n_k}\Vert \le {\theta }_{n_k}\Vert u-x_{n_k}\Vert +\left(1-{\theta }_{n_k}\right)\Vert y_{n_k}-x_{n_k}\Vert$ ,

于是$\underset{k\to +\infty }{\lim }\Vert x_{n_k+1}-x_{n_k}\Vert =0$ ，这说明

$\underset{k\to +\infty }{\lim \sup }\langle u-p,x_{n_k+1}-p\rangle \le 0$ .

再由条件(C₃)，(C₄)可得，

$\underset{k\to +\infty }{\lim }\Vert \frac{1-{\theta }_{n_k}}{{\theta }_{n_k}}{\varphi }_{n_k}\Vert \le \underset{k\to +\infty }{\lim }\frac{2\left(1-u_{n_k}-v_{n_k}\right)}{{\theta }_{n_k}}\Vert p\Vert \Vert y_{n_k}-p\Vert +2\frac{\Vert e_{n_k}\Vert }{{\theta }_{n_k}}\Vert y_{n_k}-p\Vert =0$ .

所以，$\underset{k\to +\infty }{\lim \sup }{\delta }_{n_k}\le 0$ 。由引理3可得$\underset{n\to +\infty }{\lim }{b}_n=0$ ，所以序列$\left\{x_n\right\}$ 强收敛于$x^{*}$ 。

4. 数值实验

本节我们将用算法(4)和算法(5)求解凸可行问题并比较它们的表现，所有实验均用Matlab2020a编写，程序运行环境为Lenovo笔记本电脑，CPU型号为Inter (R) Core(TM) i5-10200H CPU@2.40 GHz，运行内存为16.00GB RAM。

下面简述凸可行问题[18]。给定一组非空闭凸集$C_i\subset {ℝ}^n\left(i=0,1,\cdots ,m\right)$ ，凸可行问题是指：

寻找

$x^{*}\in C:={\displaystyle \underset{i=0}{\overset{m}{\cap }}{C}_i}$ (19)

其中$C\ne \varnothing$ ，定义映射$T:{ℝ}^n\to {ℝ}^n$ ，

$T:=P_0\left(\frac{1}{m}{\displaystyle \sum _{i=1}^m{P}_i}\right)$ (20)

其中，$P_i=P_{C_i}\left(i=0,1,\cdots ,m\right)$ 代表$C_i$ 上的度量投影。由于$P_i$ $\left(i=0,1,\cdots ,m\right)$ 是非扩张的，可以推得$T$ 是非扩张的且

$\mathrm{Fix}\left(T\right)=\mathrm{Fix}\left(P_0\right)\cap {\displaystyle \underset{i=1}{\overset{m}{\cap }}\mathrm{Fix}}\left(P_i\right)=C_0\cap {\displaystyle \underset{i=1}{\overset{m}{\cap }}{C}_i}=C.$

对于凸可行问题(19)而言，一种经典的解法就是求解由(20)定义的映射$T$ 的不动点[19]。

在这节实验中，我们设$C_i$ 是一个闭球，其球心为$c_i\left(c_i\in {ℝ}^n\right)$ ，半径为$r_i\left(r_i>0\right)$ 。于是，$C_i$ 的度量投影为：

$P_i\left(x\right):=\{\begin{array}{ll}{c}_i+\frac{r_i}{\Vert c_i-x\Vert }\left(x-c_i\right)\hfill & \text{if}\Vert c_i-x\Vert >r_i,\hfill \\ x\hfill & \text{if}\Vert c_i-x\Vert \le r_i.\hfill \end{array}$

令$v_0=\left[10,10,\cdots ,10\right]$ ，取$r_i=1\left(i=0,1,\cdots ,m\right)$ ，$c_0=v_0$ ，$c_1=v_0+\left[1,0,\cdots ,0\right]$ ，$c_2=v_0+\left[-1,0,\cdots ,0\right]$ ，剩余的$c_i=v_0+d_i\left(i=3,4,\cdots ,m\right)$ ，$d_i\in {\left(-1/\sqrt{n},1/\sqrt{n}\right)}^n$ ，即$d_i$ 的每个分量按均匀分布随机得取于$\left(-1/\sqrt{n},1/\sqrt{n}\right)$ 。从上述的选择，我们可以推得$\mathrm{Fix}\left(T\right)=\left\{v_0\right\}$ 。

下面给出算法(4) (记作MIMHA)和算法(5) (记作G2IMMH)实验参数的选择和停止准则的设置。

实验参数的选择：G2IMMH参数选取为，

$u_n=0.1-\frac{1}{{\left(n+3\right)}^2}$ , $v_n=0.9-\frac{1}{{\left(n+3\right)}^2}$ , ${\theta }_n=\frac{1}{10000n}$ , $e_n=0$ ,

${\alpha }_n=\{\begin{array}{ll}\frac{n-1}{n+2},\hfill & x_n=x_{n-1}\hfill \\ \frac{10}{\left(n^2+1\right)\Vert x_n-x_{n-1}\Vert },\hfill & x_n\ne x_{n-1}\hfill \end{array}$ , ${\beta }_n=\{\begin{array}{ll}0,\hfill & x_{n-1}=x_{n-2}\hfill \\ \frac{-0.2}{\left(n^2+1\right)\Vert x_{n-1}-x_{n-2}\Vert },\hfill & x_{n-1}\ne x_{n-2}\hfill \end{array}$ , $u=x_3$ .

MIMHA的参数选取为，${\lambda }_n=0.1$ 。${\theta }_n,{\alpha }_n,u$ 同G2IMMH。

输入和停止准则设置：初始值$x_1,x_2,x_3$ 是服从(0, 1)均匀分布的随机向量。MIMHA的初始值设为$x_2,x_3$ 。G2IMMH的初始值设为：$x_1,x_2,x_3$ 。定义$\text{Err}:={\Vert x_n-v_0\Vert }_{\infty }$ ，设$\tau =0.005$ 。停止准则设为：

$\text{Err}<\tau$ .

在实验中，我们记凸集个数和向量空间的维数为$\left(m;n\right)=\left(50k;50k\right)\left(k=1,2,\cdots ,10\right)$ ，一共进行十组实验，每组实验重复5次再取平均值。

表1为10组数据的结果。表1中，Iter表示迭代次数，CPU运行时间的单位为秒。图1是$n=100$ ，$m=100$ 情况下的误差图像，图中Proposed代表本文提出的算法G2IMMH。从表1和图1中，我们可以看出G2IMMH能有效求解凸可行问题且它的迭代次数和CPU运行时间比MIMHA更少，这说明G2IMMH在一定的情况下比MIMHA更有优势。

Table 1. Experimental results in different dimensions

表1. 不同维度下的实验数据

$\left(m;n\right)$	MIMHA		G2IMMH
	Iter	CPU Time	Iter	CPU Time
(50; 50)	111,948	4.45	37,337	1.49
(100; 100)	165,173	13.00	37,666	2.98
(150; 150)	183,481	22.61	38,362	4.75
(200; 200)	205,149	35.49	38,381	6.67
(250; 250)	198,346	45.26	38,858	8.86
(300; 300)	219,213	59.27	39,196	10.54
(350; 350)	253,986	84.40	39,067	12.82
(400; 400)	224,138	90.07	39,124	16.01
(450; 450)	199,758	97.63	39,175	19.17
(500; 500)	216,043	117.64	39,584	22.65

Figure 1. Graph of error under the condition that $n=100$ and $m=100$

图1. $n=100$ ，$m=100$ 时的误差图像

5. 总结

本文提出了一种广义修正两步惯性Mann Halpern算法并在合适的条件下证明了它的收敛性。在求解凸可行问题的数值实验中，和文献[15]中的算法进行了比较，实验结果表明本文提出的算法在解决该实验问题中更有优势。在未来的研究中，我们还会将该算法运用到Douglas-Rachford分裂算法中并用于求解一些实际问题，比如图像处理，矩阵优化及机器学习等。我们也将进一步研究该算法的收敛速率。