设 $H$ 是具有内积 $\langle\cdot, \cdot\rangle$ 和范数 $\|\cdot\|$ 的实 Hilbert 空间, $C$ 是 $H$ 中的非空闭凸子集, 映射 $F: H\to H$, 映射 $T: H\to H$. 经典变分不等式问题 (VIP) 是指: 寻找 $x^*\in C$, 使得

记变分不等式问题 (1.1) 的解集为 $S$.

$T$ 的不动点问题 (FPP) 是: 寻找 $x^*\in H$, 使得

映射 $T$ 的不动点集记为 ${\rm Fix}(T)$.

变分不等式问题与不动点问题的公共解是指: 寻找 $x^*\in H$, 使得

这一问题在许多领域都有应用, 如信号处理、图像恢复和网络资源分配^[1⇓-3]. 近年来, 求解 Hilbert 空间中变分不等式问题与不动点问题的公共解的投影算法受到众多学者关注^{[4⇓⇓⇓⇓-9]}.

2003 年, Takahashi 和 Toyoda^[5] 基于求解变分不等式问题的投影梯度法^[10]和求解不动点问题的 Mann 迭代法^[11]提出了如下算法

其中 $\{\lambda_n\} \subset [a, b] \subset (0, 2\eta)$, $\{\beta_n\} \subset [c, d] \subset (0, 1)$. 在映射 $F$ 是 $\eta$- 余强制和映射 $T$ 是非扩张时, 文献[5] 证明了算法(1.3) 所产生的序列弱收敛到变分不等式问题与不动点问题的公共解.

为了削弱映射 $F$ 的余强制性, 2006 年, Nadezhkina 和 Takahashi[4] 基于求解变分不等式问题的外梯度算法^[12]提出了如下算法

其中 $\{\lambda_n\} \subset [a, b] \subset (0, \frac{1}{L})$, $\{\beta_n\} \subset [c, d] \subset (0, 1)$. 在映射 $F$ 是 Lipschitz 连续的单调映射和映射 $T$ 是非扩张映射时, 文献 [4] 证明了算法 (1.4) 所产生的序列弱收敛到变分不等式问题与不动点问题的公共解.

为了减少向 $C$ 投影的次数, 一方面, 2011 年 Censor 等^[13]将文献 [4] 中的算法第二次向 $C$ 投影替换为向某个半空间投影, 提出以下算法

其中 $\lambda \in (0, \frac{1}{L})$, $\{\beta_n\} \subset [c, d] \subset (0, 1)$. 在映射 $F$ 是单调 Lipschitz 连续和映射 $T$ 是非扩张时, 文献 [13]证明了算法 (1.5)所产生的序列弱收敛到变分不等式问题与不动点问题的公共解.

另一方面, 2018 年, Thong 和 Hieu^[6] 基于求解变分不等式的 Tseng 型外梯度算法^[14], 提出以下算法

其中 $r > 0$, $\mathit{l}\in (0, 1)$, $\{\beta_n\} \subset [c, d] \subset (0, 1)$. 在映射 $F$ 是单调 Lipschitz 连续和映射 $T$ 是拟非扩张且 $I-T$ 在 0 处半闭时, 文献 [6] 证明了算法 (1.6) 所产生的序列弱收敛到变分不等式问题与不动点问题的公共解.

为了进一步获得强收敛的结果, 2018 年 Thong 等^[6]基于 Halpern 迭代法^[15]提出如下算法

其中 $r > 0$, $\mathit{l}\in (0, 1)$, $\{\alpha_n\} \subset (0, 1)$, $\lim\limits_{n\to \infty}\alpha_n = 0$, $\sum\limits_{n = 1}^\infty\alpha_n = \infty$, 且 $\{\beta_n\} \subset [c, d] \subset (0, 1)$. 在映射 $F$ 单调 Lipschitz 连续和映射 $T$ 是拟非扩张且 $I-T$ 在 0 处半闭时, 文献 [6] 证明了算法 (1.7) 产生的序列强收敛到 $P_{{\rm Fix}(T) \cap S}(u^0)$.

众所周知, 单调映射和伪单调映射一定是拟单调映射, 但反之不一定成立, 见文献[16]. 因此, 有必要将映射 $F$ 的单调性进一步削弱. 2022 年, Yin 等[17]提出求解拟单调变分不等式问题与伪压缩映射不动点问题的公共解的如下算法

其中 $\{\alpha_n\}$, $\{\beta_n\}$, $\{\gamma_n\}$ 皆包含于 $(0,1)$, 且满足

假设映射 $T$ 是 Lipschitz 连续的伪压缩映射, 映射 $F$ 是拟单调 Lipschitz 连续的, 且对任意满足 $x^n\rightharpoonup x$, $\liminf\limits_{n\to\infty}\|F(x^n)\|=0$ 的序列 $\{x^n\}$ 都有 $F(x)=0$, 集合 $\{x\in C:F(x)=0\}\setminus S_D$ 是一个有限集, ${\rm Fix}(T)\cap S_D\ne\emptyset$, 文献 [17] 证明了算法 (1.8) 所产生的序列弱收敛到变分不等式问题与不动点问题的公共解.

一方面, 为了削弱文献 [6] 中映射 $F$ 的单调性和 Lipschitz 连续性以及映射 $T$ 的非扩张性, 另一方面, 为了削弱文献 [17] 中映射 $F$ 的 Lipschitz 连续性, 本文提出一种具有惯性项的 Tseng 型外梯度算法, 找到了变分不等式问题与不动点问题的公共解. 在映射 $F$ 是一致连续的拟单调映射和映射 $T$ 是半压缩映射的条件下, 证明了算法所产生的序列强收敛到变分不等式问题与不动点问题的公共解. 与文献 [6] 相比, 本文将映射 $F$ 的单调性削弱为拟单调, 将映射 $F$ 的 Lipschitz 连续性削弱为一致连续, 将映射 $T$ 的拟非扩张性削弱为半压缩. 与文献 [17] 相比, 本文将映射 $F$ 的 Lipschitz 连续性削弱为一致连续, 且算法产生的序列是强收敛的. 数值实验表明了本算法的有效性.

本文的内容安排如下: 在第 2 节中, 回顾一些定义和引理. 在第 3 节中, 提出算法并分析算法的收敛性. 最后, 在第 4 节中用几个数值例子说明算法的有效性.

设 $H$ 是具有内积 $\langle \cdot, \cdot\rangle$ 和范数 $\|\cdot\|$ 的实 Hilbert 空间, $C$ 是 $H$ 中的非空闭凸子集. 记 $x^n\to x$ 为序列 $\{x^n\}$ 强收敛到 $x$, 记 $x^n\rightharpoonup x$ 为序列 $\{x^n\}$ 弱收敛到 $x$.

定义2.1 设映射 $F:H\rightarrow H$, 称

(i) $F$ 是单调的, 若

(ii) $F$ 是伪单调的, 若

(iii) $F$ 是拟单调的, 若

(iv) $F$ 是 Lipschitz 连续的, 若存在 $L > 0$, 满足

(v) $F$ 是序列弱连续的, 若对任意满足 $x^n \rightharpoonup x$ 的序列 $\{x^n\}$, 都有 $F(x^n) \rightharpoonup F(x)$.

定义2.2^[8] 设映射 $T:H\rightarrow H$, 称

(i) $T$ 是非扩张映射, 若

(ii) $T$ 是拟非扩张映射, 若

(iii) $T$ 是 $\kappa$-半压缩映射, 若对任意 $z\in {\rm Fix}(T), x\in H$, 都存在 $\kappa\in[0, 1)$, 满足

(iv) $I-T$ 在 0 处是半闭的, 若对于任意的序列 $\{x_n\}\subset H$, 当 $x_n\rightharpoonup x$ 且 $(I-T)x_n\to 0$ 时, 有 $x\in {\rm Fix}(T)$.

注2.1 由定义 2.2 中映射 $T$ 的定义, 可知 (i)$\Rightarrow$(ii)$\Rightarrow$(iii), 但(i)$\nLeftarrow$(ii)$\nLeftarrow$(iii), 见文献[18,19]. 有 (i)$\Rightarrow$(iv), 但(ii)$\nRightarrow$(iv), 见文献 [20,21].

注2.2 事实上, (2.1) 式等价于

也等价于

对任意的非空闭凸集 $C\subset H$, 设与 $x\in H$ 距离最近的点为 $x$ 在 $C$ 上的投影, 记为 $P_C(x)$, 即 $P_C(x)$ 为 $C$ 中满足如下条件的点

显然, 若 $x\in C$, 则 $x=P_C(x)$. 下面给出投影的一些基本性质.

引理2.1^[22,23] 令 $C\subset H$ 是一个非空闭凸集. 对于任意 $x\in H$, $\alpha \ge \beta > 0$, 下列不等式成立

(i) $\langle P_{C}(x) - x, y - P_{C}(x)\rangle \ge 0, \forall y\in C$;

(ii) $\|y - P_{C}(x)\|^{2} \le \|y - x\|^{2} - \|P_{C}(x) - x\|^{2}, \forall y\in C$;

(iii) $\frac{\|x - P_C(x - \alpha F(x))\|}{\alpha} \le \frac{\|x - P_C(x - \beta F(x))\|}{\beta}$;

(iv) $\|x - P_C(x - \beta F(x))\| \le \|x - P_C(x - \alpha F(x))\|$.

下面给出一些引理, 其对算法收敛性的证明至关重要.

引理2.2^[24] 设 $\{\Phi_n\}$ 是一个非负实序列, 序列 $\{s_n\}\subset(0,1)$, 满足 $\sum\limits_{n = 0}^\infty s_n = \infty$, $\{\Omega_n\}$ 是一个实序列, 且满足下式

如果对满足 $\liminf\limits_{k\to\infty}(\Phi_{n_{k+1}} - \Phi_{n_k}) \ge 0$ 的 $\{\Phi_n\}$ 的任意子列 $\{\Phi_{n_k}\}$ 对应的 $\{\Omega_{n_k}\}$, 都有 $\limsup\limits_{k\to\infty}\Omega_{n_k} \le 0$, 则 $\lim\limits_{n\to\infty}\Phi_n = 0$.

关于半压缩映射有如下性质.

引理2.3^[3] 设 $T:H\rightarrow H$ 是 $\kappa$-半压缩映射且 ${\rm Fix}(T)\neq \emptyset$, 设 $T_\alpha = (1 - \alpha)I + \alpha T$, $\alpha \in (0, 1 - \kappa)$, 则

(i) ${\rm Fix}(T) = {\rm Fix}(T_\alpha)$;

(ii) $\|T_\alpha(x) - z\|^2 \le \|x - z\|^2 - \frac{1}{\alpha}(1 - \kappa -\alpha)\|(I - T_\alpha)x\|^2, \forall x\in H, z\in {\rm Fix}(T)$;

(iii) ${\rm Fix}(T)$ 是 $H$ 的闭凸子集.

本文将假设 ${\rm Fix}(T)\cap S_D\ne\emptyset$, 接下来讨论什么条件下满足该条件, 首先给出 $S_D$ 的定义.

定义2.3^[25,26] 问题 (1.1) 的对偶变分不等式是: 寻找 $x^* \in C$ 使得

记对偶变分不等式的解集为 $S_D$. 用 $S_T$ 和 $S_N$ 分别表示问题 (1.1) 的平凡解和非平凡解, 即

注2.3 由文献[25]可知, 当 $C$ 是非空闭凸集, $F$ 在 $C$ 上是连续映射时, 有 $S_D\subset S$. 进一步, 当 $F$ 在 $C$ 上是伪单调 (或单调) 映射时, 有 $S = S_D$. 但当 $F$ 是拟单调映射时, 存在 $S_D \neq S$ 的例子, 见文献[26,例 4.2].

其次给出 ${\rm Fix}(T)\cap S_D$ 非空的一些充分条件.

引理2.4 映射 $F:H\to H$ 是连续的, 若

(a) $F$ 在 $C$ 上伪单调, ${\rm Fix}(T)\cap S\neq \emptyset$;

(b) $F$ 在 $C$ 上拟单调, ${\rm Fix}(T)\cap S_N\neq \emptyset$;

(c) $F$ 在 $C$ 上拟单调, $C$ 的内部非空, 存在 $x^* \in {\rm Fix}(T)\cap S$ 使得 $F(x^*)\neq 0$,

则 ${\rm Fix}(T)\cap S_D\ne\emptyset$.

证 类似文献 [26]. 其中 (a) 是因为伪单调的定义和注2.3; (b) 是文献[26,引理 2.7] 的推论; (c) 是因为 (b) 和文献[26,定理 2.1].

我们假设下述条件成立

条件 1 映射 $F:H\to H$ 是拟单调的, 在 $H$ 的有界子集上是一致连续的, 并且在 $C$ 上是序列弱连续的, 且对任意 $x\in C$, $F(x)\neq 0$.

条件 2 映射 $T:H\to H$ 是 $\kappa$-半压缩的, 且 $I - T$ 在 0 处是半闭的.

条件 3${\rm Fix}(T)\cap S_D\ne\emptyset$.

本文提出如下算法

算法1${\bf 初始}$ 给定 $r > 0, \mathit{l}\in (0,1), \tau\in (0,1)$, $\theta > 0$. 选取正实数序列 $\{\alpha_n\}, \{\beta_n\}, \{\varepsilon_n\}$ 满足 $\{\alpha_n\}\subset(0,1)$, $\lim\limits_{n\to\infty}\alpha_n = 0$, $\sum\limits_{n = 1}^\infty \alpha_n = \infty$, $\lim\limits_{n\to\infty}\frac{\varepsilon_n}{\alpha_n} = 0$, $\{\beta_n\}\subset(a,b)\subset(0,1 - \kappa)$, 其中 $a$, $b$ 是实数满足 $0 < a < b < 1$. 任取 $x^0, x^1, u^0\in H.$

${\bf 迭代}$ 第一步 给定迭代点 $x^{n - 1}$ 与 $x^n(n \geq 1)$. 计算

其中 $0 \le \theta_n \le \bar{\theta}_n,$

计算

其中 $\lambda_n: = r\mathit{l}^{m_n}$, $m_n$ 是满足下述不等式的最小非负整数 $m$:

第二步 计算

令 $n: = n + 1$, 回到第一步.

首先, 根据算法 1 中参数的选取, 有以下结论成立.

注3.1 设 $\{x^n\}$ 是算法 1 产生的序列, $\theta_n$ 的选取见算法 1, 则

(i) $\{\theta_n\}\subset[\theta]$;

(ii) $\lim\limits_{n\to\infty}\frac{\theta_n}{\alpha_n}\|x^n - x^{n - 1}\| = 0$, 且存在 $M_1 > 0$, 对任意 $n\ge 1$, 使得 $\frac{\theta_n}{\alpha_n}\|x^n - x^{n - 1}\| \le M_1$.

其中 (i) 由 $\theta_n$ 和 $\bar{\theta}_n$ 的定义可得. 对于 (ii), $0 \le \frac{\theta_n}{\alpha_n}\|x^n - x^{n - 1}\| \le \frac{\bar{\theta}_n}{\alpha_n}\|x^n - x^{n - 1}\| \le \frac{\varepsilon_n}{\alpha_n}$, 结合 $\lim\limits_{n\to\infty}\frac{\varepsilon_n}{\alpha_n} = 0$ 可知 $\lim\limits_{n\to\infty}\frac{\theta_n}{\alpha_n}\|x^n - x^{n - 1}\| = 0$. 因此, 由极限的定义可知存在 $M_1 > 0$, 对任意 $n\ge 1$, 使得 $\frac{\theta_n}{\alpha_n}\|x^n - x^{n - 1}\| \le M_1$.

其次, 证明算法的良定性.

引理3.1 假设条件1 成立, $w^n$ 是由算法 1 产生的序列, 则对任意的 $n\ge1$ 都存在最小非负整数 $m$ 使得

证 若 $w^n\in S$, 则 $w^n = P_C(w^n - rF(w^n))$, 取 $m = 0$, (3.7) 式成立.

若 $w^n\notin S$, 采用反证法. 假设对于所有的非负整数 $m$ 满足下式

即

考虑下述两种情形.

${\bf 情形 1}$ 假设 $w^n\in C$. 因为 $P_C$ 连续, 则

再由条件 1知, 映射 $F$ 在 $H$ 的有界子集上是一致连续的, 则有

结合 (3.9) 和 (3.11) 式, 有

令 $h^m = P_C(w^n - r\mathit{l}^mF(w^n))$, 根据引理 2.1(i) 知

等价于

即

对 (3.13) 式取极限 $m\to\infty$, 结合 (3.10) 和 (3.12) 式, 得 $\langle F(w^n), x - w^n\rangle \ge 0, \forall x\in C,$ 从而 $w^n\in S$, 这与 $w^n\notin S$ 矛盾, 因此存在非负整数 $m$ 使得 (3.7) 式成立.

${\bf 情形 2}$ 假设 $w^n\notin C$. 因为 $P_C$ 连续, 则

从而

由条件 1 知, 映射 $F$ 在 $H$ 的有界子集上是一致连续的, 结合 $P_C$ 连续, 可知

由 (3.14), (3.15) 式知这与 (3.8) 式矛盾, 从而存在非负整数 $m$ 使得 (3.7) 式成立.

先给出以下引理, 这对证明算法的收敛性起着关键性的作用.

引理3.2 假设条件 1-3 成立, 若算法 1 生成的序列 $\{x^n\}$ 有界, $\lim\limits_{n\to\infty}\|w^n - y^n\| = 0$, $\lim\limits_{n\to\infty}\|w^n - x^n\| = 0$, $\lim\limits_{n\to\infty}\|q^n - x^n\| = 0$ 和 $\lim\limits_{n\to\infty}\|T(q^n) - q^n\| = 0$, 并且存在$\{x^{n_k}\}\subset\{x^n\}$ 使得 $x^{n_k}\rightharpoonup \hat{x}\in H$, 则有 $\hat{x}\in {\rm Fix}(T)\cap S_D$.

证 由于 $x^{n_k}\rightharpoonup \hat{x}$ 和 $\lim\limits_{k\to\infty}\|w^{n_k} - x^{n_k}\| = 0$, 得 $w^{n_k}\rightharpoonup \hat{x}$. 由于 $\lim\limits_{n\to\infty}\|w^n - y^n\| = 0$, 所以 $y^{n_k}\rightharpoonup \hat{x}$. 又因为 $\{y^n\}\subset C$, 及 $C$ 的闭性 (见(3.2) 式), 可得 $\hat{x}\in C$. 由 $y^n$ 的定义(3.2) 式, 以及引理 2.1 知

从而

等价于

首先证明下面两个不等式成立

要证 (3.17) 式成立, 考虑以下两种情况.

(1) 当 $\displaystyle\liminf_{k\to\infty}\lambda_{n_k} > 0$. 因为 $\{x^n\}$ 有界且 $\displaystyle\lim_{n\to\infty}\|w^n - x^n\| = 0$, 因此 $\{w^{n_k}\}$ 有界. 又因为映射 $F$ 在 $H$ 的有界子集上是一致连续的, 由文献 [27]可知, $\{F(w^{n_k})\}$ 是有界的. 又因为 $\displaystyle\lim_{k\to\infty}\|w^{n_k} - y^{n_k}\| = 0$, 所以 $\{y^{n_k}\}$ 是有界的. 对 (3.16) 式两边同时取下极限, 可得

即 (3.17) 式成立.

(2) 当 $\displaystyle\liminf_{k\to\infty}\lambda_{n_k} = 0$. 由于 $\mathit{l}\in (0, 1)$, 所以 $\lambda_{n_k}\mathit{l}^{-1} > \lambda_{n_k}$. 由引理 2.1 得

为了方便表达, 令 $t^{n_k} := P_C(w^{n_k} - \lambda_{n_k}\mathit{l}^{-1}F(w^{n_k}))$, 即 $\|w^{n_k} - t^{n_k}\| \le \frac{1}{\mathit{l}}\|w^{n_k} - y^{n_k}\|.$ 故 $\displaystyle\lim_{k\to\infty}\|w^{n_k} - t^{n_k}\| = 0$. 因此 $t^{n_k}\rightharpoonup \hat{x} \in C$, 即 $\{t^{n_k}\}$ 是有界的. 又因为映射 $F$ 在 $H$ 的有界子集上是一致连续的, 所以有

由 $m_n$ 的定义可知

即

联立(3.19) 和 (3.20) 式知

根据 $t^{n_k}$ 的定义, 结合引理 2.1 可知

上式等价于

对 (3.22) 式取下极限, 结合(3.21) 式有对任意 $x\in C$, $\displaystyle\liminf_{k\to\infty}\langle F(w^{n_k}), x - w^{n_k}\rangle \ge 0$, 从而 (3.17) 式得证.

进一步证明 (3.18) 式成立. 事实上

由于 $F$ 在 $H$ 的有界子集上一致连续, 以及 $\displaystyle\lim_{k\to\infty}\|w^{n_k} - y^{n_k}\| = 0$, 可得

联立 (3.17) 和 (3.23) 式可得

然后证明 $\hat{x}\in S_D$. 为了方便表达, 令 $V^{n_k} := \frac{F(y^{n_k})}{\|F(y^{n_k})\|^2}$, 则对任意 $k \ge 1$, $\langle F(y^{n_k}), V^{n_k}\rangle = 1$. 取

则

考虑以下两种情况: (1) 当对任意 $x\in C$, $\displaystyle\limsup_{k\to\infty}\langle F(y^{n_k}), x - y^{n_k}\rangle > 0$. 由上极限定义知, 存在 $\{y^{n_{k_j}}\}\subset\{y^{n_k}\}$ 满足 $\langle F(y^{n_{k_j}}), x - y^{n_{k_j}}\rangle > 0, \forall j \ge 1.$ 因为 $F$ 在 $H$ 上是拟单调的, 有 $\langle F(x), x - y^{n_{k_j}}\rangle \ge 0, ~ \forall j \ge 1.$ 在上式中令 $j\to\infty$ 得 $\langle F(x), x - \hat{x}\rangle \ge 0,~ \forall x\in C,$ 即 $\hat{x}\in S_D$.

(2) 当对任意 $x \in C$, $\displaystyle\limsup_{k\to\infty}\langle F(y^{n_k}), x - y^{n_k}\rangle = 0$. 由 (3.25) 式知 $\displaystyle\lim_{k\to\infty}\langle F(y^{n_k}), x - y^{n_k}\rangle = 0$. 由 $\xi_k$ 的定义 (3.24) 式得 $\displaystyle\lim_{k\to\infty}\xi_k = 0$. 由于 $y^{n_k}\rightharpoonup \hat{x}$, 映射 $F$ 在 $C$ 上弱序列连续, 所以 $F(y^{n_k})\rightharpoonup F(\hat{x})$, 且由条件 1 可知 $F(\hat{x}) \neq 0$. 注意范数映射是序列弱下半连续的^[28,29], 因此

由 $\displaystyle\lim_{k\to\infty}\xi_k = 0$ 得

从而 $\displaystyle\lim_{k\to\infty}\|\xi_kV^{n_k}\| = 0$, 即 $\displaystyle\lim_{k\to\infty}\xi_kV^{n_k} = 0$. 由 $\xi_k$ 的定义 (3.24) 式知 $\langle F(y^{n_k}), x - y^{n_k}\rangle + \xi_k > 0, \ \ \forall x\in C,$ 等价于

因为映射 $F$ 在 $H$ 上是拟单调的, 有

等价于

因为 $\displaystyle\lim_{k\to\infty}\xi_kV^{n_k} = 0$ 及 $F$ 在 $H$ 的有界集上是一致连续的, 得

在 (3.26) 式中令 $k\to\infty$, 结合 (3.27) 式得 $\langle F(x), x - \hat{x}\rangle \ge 0, \forall x\in C,$ 即 $\hat{x}\in S_D$.

最后证明 $\hat{x}\in {\rm Fix}(T)$. 因为 $\displaystyle\lim_{n\to\infty}\|x^n - q^n\| = 0$ 和 $x^{n_k}\rightharpoonup \hat{x}$, 则 $q^{n_k}\rightharpoonup \hat{x}$. 又因为 $\displaystyle\lim_{n\to\infty}\|T(q^n) - q^n\| = 0$ 及 $I - T$ 在 0 处是半闭的, 结合半闭的定义可得 $\hat{x}\in {\rm Fix}(T)$.

综上可得, $\hat{x}\in {\rm Fix}(T)\cap S_D$.

下面证明算法 1 生成的序列 $\{x^n\}$ 有界.

引理3.3 假设条件 1-3 成立, $\{w^n\}$, $\{x^n\}$, $\{y^n\}$, $\{q^n\}$, $\{z^n\}$ 是算法 1 生成的序列. 则对任意 $x^*\in {\rm Fix}(T)\cap S_D$, 以下结论成立

(i) $\|x^{n + 1} - x^*\|^2 \le \|q^n - x^*\|^2 - \beta_n(1 - \kappa - \beta_n)\|T(q^n) - q^n\|^2$;

(ii) $\|z^n - x^*\|^2 \le \|w^n - x^*\|^2 - (1 - \tau^2)\|w^n - y^n\|^2$;

(iii) 存在 $M_1 > 0$, 对任意 $n \ge 1$, 使得 $\|w^n - x^*\| \le (1 - \alpha_n)\|x^n - x^*\| + \alpha_nM_1$;

(iv) $\{x^n\}$ 有界.

证 (i) 由 $x^{n + 1}$ 的定义 (3.6) 式可知

其中 (a) 成立是因为 $T$ 是 $\kappa$-半压缩映射. 由定义 2.2 得

(ii) 由 $z^n$ 的定义 (3.4) 式可知

一方面, 因为 $x^*\in {\rm Fix}(T)\cap S_D$ 以及 $y^n\in C$, 则有 $\langle F(y^n), F(y^n) - x^*\rangle \ge 0$. 另一方面, 因为 $y^n = P_C(w^{n} - \lambda_nF(w^{n}))$, 结合引理 2.1 知, $\langle y^n - w^n + \lambda_n F(w^n), y^n - x^*\rangle \le 0$. 将其代入 (3.28) 式有

根据 (3.3) 式有 $\lambda_n^2\|F(y^n) - F(w^n)\|^2 \le \tau^2\|y^n - w^n\|^2$, 代入 (3.29) 式有

(iii) 由注 3.1 的 (ii) 可知, 存在正数 $M_1$, 对任意 $n \ge 1$, 使得 $\frac{\theta_n}{\alpha_n}\|x^n - x^{n - 1}\| \le M_1$. 因此对 $\forall n \ge 1,$

(iv) 由 $\alpha_n$ 和 $\beta_n$ 的选取可知 $\{\alpha_n\} \subset (0, 1)$, $\{\beta_n\} \subset (a, b)\subset (0, 1-\kappa)$, 因此

其中 (a) 成立是因为由 (i) 可得 $\|x^{n + 1} - x^*\| \le \|q^n - x^*\|$; (b) 成立是因为 $q^n$ 的定义 (3.5) 式; (c) 成立是因为由 (ii) 可得 $\|z^n - x^*\| \le \|w^n - x^*\|$; (d) 成立根据 (iii) 可得. 由数学归纳法得 $\begin{equation*} \|x^{n + 1} - x^*\| \le \max\{\|x^n - x^*\|, \|u^0 - x^*\| + M_1\} \le \cdots \le \max\{\|x^1 - x^*\|, \|u^0 - x^*\| + M_1\}. \end{equation*}$ 因此, 序列 $\{x^n\}$ 有界.

接下来给出如下引理, 这对后续的证明至关重要.

引理3.4 假设条件 1-3 成立, $\{w^n\}$, $\{x^n\}$, $\{y^n\}$, $\{q^n\}$, $\{z^n\}$ 是算法 1 生成的序列. 则对任意 $x^*\in {\rm Fix}(T)\cap S_D$, 以下结论成立

(i) 存在 $M_2 > 0$ 使得

(ii) 存在 $M_3 > 0$ 使得

证 (i) 由引理 3.3 的 (i) 可得

其中 (a) 成立是因为 $q^n$ 的定义 (3.5) 式; (b) 成立是由 $\{\alpha_n\}\subset (0, 1)$ 可得; (c) 成立是因为引理 3.3(ii). 由引理 3.3(iii) 得

其中 (a) 成立是因为 $\{x^n\}$ 有界 (根据引理 3.3(iv) 可知), 以及 $\{\alpha_n\}\subset (0, 1)$, 则存在 $M_2 > 0$ 使得

因此

(ii) 因为 $\{x^n\}$ 有界 (由引理 3.3(iv) 可知) 和 $\theta_n \le \theta$ (由注 3.1(i) 可知), 所以存在 $M_3 > 0$ 使得

由引理 3.3(i) 可得

其中 (a) 成立是因为 $q^n$ 的定义 (3.5) 式; (b) 成立是因为引理 3.3(ii) 以及 $\{\alpha_n\} \subset (0, 1)$; (c) 成立是因为 $w^n$ 的定义(3.1) 式; (d) 成立是因为 (3.30) 式.

最后证明 $\{x^n\}$ 强收敛到 $P_{S_D\cap {\rm Fix}(T)}(u^0)$. 由 $S_D\cap {\rm Fix}(T)\neq \emptyset$ 知 ${\rm Fix}(T)\neq \emptyset$, 结合 $T$ 是半压缩映射, 根据引理2.3 知 ${\rm Fix}(T)$ 是闭凸集. 由 $S_D$ 的定义 (2.2) 式知 $S_D$ 是闭凸集. 因此 $S_D\cap {\rm Fix}(T)$ 是非空闭凸集, 则 $P_{S_D\cap {\rm Fix}(T)}(u^0)$ 存在且唯一.

定理3.1 假设条件 1-3 成立, $\{x^n\}$ 是算法 1 生成的序列, 则 $\{x^n\}$ 强收敛到 $\widetilde{x} := P_{S_D\cap {\rm Fix}(T)}(u^0)$.

证 记 $\Phi_n := \|x^n - \widetilde{x}\|^2$, $s_n := \alpha_n$, $\Omega_n := M_3\frac{\theta_n}{\alpha_n}\|x^n - x^{n - 1}\| + 2\langle u^0 - \widetilde{x}, q^n - \widetilde{x}\rangle$, 根据引理 3.4(ii) 可知 $\Phi_{n + 1} \le (1 - s_n)\Phi_n + s_n \Omega_n, \forall n \ge 1,$ 其中 $\{s_n\} \subset (0, 1)$ 且 $\sum\limits_{n=1}^{\infty}s_n = \infty$. 由引理 2.2 知, 要证 $\Phi_n : \|x^n - \widetilde{x}\|^2\to 0(n\to\infty)$, 只需证对满足 $\displaystyle\liminf_{k\to\infty} (\Phi_{n_{k+1}} - \Phi_{n_k}) \ge 0$ 的 $\{\Phi_n\}$ 的任意子列 $\{\Phi_{n_k}\}$ 对应的 $\{\Omega_{n_k}\}$, 都有 $\displaystyle\limsup_{k\to\infty}\Omega_{n_k} \le 0$. 为此, 不妨假设存在 $\{\|x^n - \widetilde{x}\|^2\}$ 的子列 $\{\|x^{n_k} - \widetilde{x}\|^2\}$ 使得

则

其中 (a) 成立是因为 $\{\beta_n\}\subset(a,b)\subset(0,1 - \kappa)$, $\tau\in (0, 1)$; (b) 成立是因为引理 3.4(i); (c) 成立是因为 (3.31) 式. 因此

由 $z^n$ 的定义 (3.4) 式可知

其中 (a) 成立是因为 (3.3) 式. 根据 (3.33) 式可得

由于 $\{\alpha_n\} \subset (0, 1)$, 则

由注 3.1(ii) 知 $\lim\limits_{n\to\infty}\frac{\theta_n}{\alpha_n}\|x^n - x^{n - 1}\| = 0$, 因此

由 $\{\alpha_n\} \subset (0, 1)$ 可知

由于 $\{x^{n_k}\}$ 有界 (由引理 3.3(iv) 可知), 结合 $\alpha_n \to 0(n\to \infty)$, 和 (3.33), (3.34), (3.35) 式得

因为 $\{x^{n_k}\}$ 有界, 由 (3.35) 式得 $\{w^{n_k}\}$ 有界. 同理可得 $\{y^{n_k}\}$, $\{z^{n_k}\}$ 有界. 记 $\{x^{n_{k_i}}\}$ 为 $\{x^{n_k}\}$ 中满足下式的收敛子列

记 $\bar{x}$ 为 $\{x^{n_{k_i}}\}$ 的弱收敛点. 由 $\widetilde{x} = P_{{\rm Fix}(T)\cap S_D}(u^0)$ 以及引理 2.1 知

注意到 $x^{n_{k_i}}\rightharpoonup \bar{x}(i\to\infty)$, 由 (3.32), (3.33), (3.35), (3.36) 式和引理 3.2 可得 $\bar{x}\in S_D\cap {\rm Fix}(T)$. 因此 $\langle u^0 - \widetilde{x}, \bar{x} - \widetilde{x}\rangle \le 0$. 又因为 $x^{n_{k_i}}\rightharpoonup \bar{x}(i\to\infty)$, 从而

结合 (3.36) 式可知

因此, 结合注 3.1(ii) 可得

由引理 2.2 可得 $\displaystyle\lim_{n\to\infty}\|x^n - \widetilde{x}\|^2 = 0$.

本节将进行数值实验来说明算法 1 的有效性. 在 Windows 10, CPU AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx (2100 MHz) 的系统环境下使用版本为 R2016a 的 Matlab 进行计算. 用 iter 表示迭代的次数, time 表示运行所花费的时间 (以秒为单位), 当 $D_n = ||x^{n + 1} - x^n|| \le \varepsilon$ 时迭代停止.

本文例 4.1 和例 4.2 中, 映射 $F$ 分别在 $\mathbb{R}^k$ 和 $H$ 上是单调映射, 因此考虑将本文所提出的算法 1 与解决单调 (或伪单调) 变分不等式与不动点问题公共解的文献 [算法 1], [算法 2], [31,算法 3.1], [7,算法 3.1,3.2] 比较. 例 4.3 中映射 $F$ 是伪单调但不是单调的映射, 不适用于文献[算法 2], [7,算法 3.1,3.2], 因此只考虑将算法 1 与文献[算法 1], [31,算法 3.1] 比较. 例4.4中映射 $F$ 是拟单调映射, 以上算法都不适用, 我们考虑不同的 $u^0$ 对算法 1 的影响.

例4.1 考虑映射 $F:\mathbb{R}^k\to\mathbb{R}^k$ 为 $F(x) = (x_1 + \cos(x_1), x_2 + \cos(x_2),\cdots,x_k + \cos(x_k))$. 定义映射 $T:\mathbb{R}^k\to\mathbb{R}^k$ 为 $T(x) = -\frac{3}{2}x$. 可行集 $C=\mathbb{R}^k_+$.

由文献 [31] 可知, 映射 $F$ 是单调 Lipschitz 连续映射且 Lipschitz 常数 $L = 2$. 事实上, 对任意的 $z\in\mathbb{R}$, 令 $g(z):=z + \cos(z)$, 则其导数 $g'(z) = 1 - \sin(z)$, 且对任意的 $z\in\mathbb{R}$, 都有 $0\leq g'(z)\leq 2$. 进一步, 对任意的 $x, y \in\mathbb{R}^k$, 根据拉格朗日中值定理有

其中 $z_i$ 取值介于 $x_i$ 和 $y_i$ 之间, 因此映射 $F$ 是单调的. 又因为

其中 $z_i$ 取值介于 $x_i$ 和 $y_i$ 之间. 所以 $\|F(x)-F(y)\|\le 2\|x-y\|$, 即映射 $F$ 是 Lipschitz 连续映射且 Lipschitz 常数 $L = 2$.

由于映射 $F$ 是单调映射, 因此 $F$ 是拟单调映射且容易验证对任意 $x\in C$, $F(x)\neq 0$, 即满足条件 1. 结合注2.3 可知 $S = S_D$. 容易验证 $0 \in S$. 映射 $T$ 是 $\frac{1}{5}$-半压缩映射且 $I - T$ 在 0 处是半闭的, 即满足条件 2, 且 ${\rm Fix}(T) = \{0\}$, 见文献 [7]. 因此 ${\rm Fix}(T)\cap S_D = {\rm Fix}(T)\cap S = \{0\}\ne\emptyset$, 满足条件 3.

比较算法 1, 文献 [算法 1], [算法 2], [31,算法 3.1], [7,算法 3.1,3.2], 且其参数选取与原文一致并列举如下

1. 文献 [算法 1]: $\tau = \frac{0.5}{L}, \theta = 0.1, \lambda_1 = 0.1, \alpha_n = \frac{1}{\sqrt{n+3}}, \varepsilon_n = \frac{100}{(n+1)^2}, \beta_n = \frac{1-\alpha_n}{2}, \xi_n = \frac{1}{(n + 1)^2}$.

2. 文献 [算法 2]: $\tau=0.55, \theta=0.45, \lambda_1=0.43, \alpha_n = \frac{1}{3n+4}, \varepsilon_n=\frac{80}{(n+1)^2}, \beta_n=\frac{n}{2n+1}$.

3. 文献 [31,算法 3.1]: $r=1, \mathit{l}=0.5, \tau=0.2, \alpha_1=\beta_1=0.1, \alpha_n=\frac{1}{n+1}, \beta_n=\frac{n}{2n+1}, f(x)=0.5x$.

4. 文献 [7,算法 3.1,3.2]: $\tau=0.5, \lambda_0=0.5, \alpha_n=\frac{1}{\sqrt{n+1}}, \beta_n=\frac{n}{2n+1}$.

5. 算法 1: $r=0.1, \mathit{l}=0.1, \tau=0.7, \theta=0.1, \alpha_n=\frac{1}{\sqrt{n+1}}, \varepsilon_n=\frac{100}{(n+1)^2}, \beta_n=\frac{n}{2n+1}, u^0=0$.

选取初始点为 $x^0=x^1=(1000,1000,\cdots,1000)^T$, 其数值实验结果见表 1 和图 1.

例4.2 设 $H=L^2([0,1])$, 对任意 $x,y\in H$, 内积 $\langle x, y\rangle = \int_0^1x(t)y(t){\rm d}t$, 范数 $||x|| = (\int_0^1|x(t)|^2{\rm d}t)^\frac{1}{2}$. 映射 $F: H\to H$ 为

定义映射 $T: H\to H$ 为 $(Tx)(t) = \int_0^1tx(s){\rm d}s, t\in[0,1]$. 可行集 $C=\{x\in H:\int_0^1 x(t){\rm d}t \geq 0\}$.

结合文献 [8] 不难发现, 映射 $F$ 在 $H$ 上是单调 Lipschitz 连续映射且 Lipschitz 常数 $L = 1$, 且对任意 $x\in C$, $F(x)\neq 0$, 即满足条件 1. 结合注2.3 不难验证 $0 \in S = S_D$. 由于 $0 \in {\rm Fix}(T)$, 因此 ${\rm Fix}(T)\ne \emptyset$. 由文献 [8] 可知映射 $T$ 是非扩张映射, 结合注 2.1 可知映射 $T$ 是 $0$-半压缩映射且 $I - T$ 在 0 处是半闭的, 即满足条件2. $0\in {\rm Fix}(T)\cap S = {\rm Fix}(T)\cap S_D \ne \emptyset$, 即满足条件3.

比较算法 1, [算法 1], [算法 2], [31,算法 3.1], [7,算法 3.1,3.2], 且其参数选取与原文一致并列举如下

1. 文献 [算法 1]: $\tau = \frac{0.5}{L}, \theta = 0.1, \lambda_1 = 0.1, \alpha_n = \frac{1}{n+3}, \varepsilon_n = \frac{100}{(n+1)^2}, \beta_n = \frac{1-\alpha_n}{2}, \xi_n = \frac{1}{(n+1)^2}$.

2. 文献 [算法 2]: $\tau=0.65, \theta=0.55, \lambda_1=0.22, \alpha_n = \frac{1}{5n+8}, \varepsilon_n=\frac{1}{(n+1)^2}, \beta_n=\frac{n}{5n+1}$.

3. 文献 [31,算法 3.1]: $r=1, \mathit{l}=0.5, \tau=0.2, \alpha_1=\beta_1=0.1, \alpha_n=\frac{1}{n+1}, \beta_n=\frac{n}{2n+1}, f(x)=0.5x$.

4. 文献 [7,算法 3.1,3.2]: $\tau=0.5, \lambda_0=0.5, \alpha_n=\frac{1}{n+1}, \beta_n=\frac{n}{2n+1}$.

5. 算法 1: $r=1, \mathit{l}=0.3, \tau=0.5, \theta=0.2, \alpha_n=\frac{1}{\sqrt{n+1}}, \varepsilon_n=\frac{100}{(n+1)^2}, \beta_n=\frac{n}{2n+1}, u^0 = 0$.

数值实验结果见表 2 和图 2.

通过表 2 和图 2可以发现: 算法 1 的迭代步数更少, 迭代时间更短.

例4.3 映射 $F:\mathbb{R}^2\to\mathbb{R}^2$ 满足

定义映射 $T:\mathbb{R}^2\to\mathbb{R}^2$ 为 $T(x) = \frac{1}{2}(x + 2.707)$. 可行集 $C=\{x\in \mathbb{R}^2: (x_1 - 2)^2 + (x_2 - 2)^2\leq 1\}$.

由文献 [29] 可知, 映射 $F$ 是伪单调但不是单调的, 是 Lipschitz 连续映射且 Lipschitz 常数 $L = 5$, $S = \{(2.707,2.707)^T\}$. 结合注2.3 可知 $S_D = S =\{(2.707,2.707)^T\}$, 映射 $F$ 是拟单调连续映射, 且不难验证对任意 $x\in C$, $F(x)\neq 0$, 即满足条件 1. 显然映射 $T$ 是非扩张映射, 且 ${\rm Fix}(T) = \{(2.707,2.707)^T\}$, 结合注 2.1 可知映射 $T$ 是 $0$-半压缩映射且 $I - T$ 在 0 处是半闭的, 即满足条件2. ${\rm Fix}(T)\cap S_D = {\rm Fix}(T)\cap S = \{(2.707,2.707)^T\}\ne \emptyset$, 即满足条件 3.

比较算法 1, 文献 [算法 1], [31,算法 3.1], 且其参数选取与原文一致并列举如下. 由于 $F$ 不是单调的, 故文献 [算法 2], [7,算法 3.1,3.2] 不适用于本例.

1. 文献 [算法 1]: $\tau \!=\! \frac{0.5}{L},\ \theta\! =\! 0.1,\ \lambda_1 \!= \!0.1,\ \alpha_n \!= \!\frac{1}{\sqrt{n+3}},\ \varepsilon_n \!= \!\frac{100}{(n+1)^2},\ \beta_n \!=\! \frac{1-\alpha_n}{2},$$\xi_n = \frac{1}{(n+1)^2}$.

2. 文献 [31,算法 3.1]: $r\!=\!0.5,\ \mathit{l}\!=\!0.5,\ \tau\!=\!0.5,\ \alpha_1\!=\!\beta_1\!=\!0.1,\ \alpha_n\!=\!\frac{1}{n+1},\ \beta_n\!=\!\frac{n}{2n+3},$$f(x)=0.5x$.

3. 算法 1: $r\!=\!1,\ \mathit{l}\!=\!0.5,\ \tau\!=\!0.5,\ \theta\!=\!0.5,\ \alpha_n\!=\!\frac{1}{n+1},\ \varepsilon_n\!=\!\frac{100}{(n+1)^2},\ \beta_n\!=\!\frac{n}{2n+1},\ u^0\! =\! (2,2)^T$.

数值实验结果见表 3 和图 3.

通过表 3 和图 3 可以发现: 算法 1 的迭代步数更少, 迭代时间更短.

例4.4 令 $C=[-1,1]$, 映射 $F$ 满足

定义映射 $T(x) = \frac{1}{2}(x - 1)$.

由文献 [16] 可知, 映射 $F$ 在 $\mathbb{R}$ 上是拟单调 Lipschitz 连续的, 且对任意 $x\in C$, $F(x)\neq 0$, 但映射 $F$ 不是伪单调映射, 即满足条件 1. 事实上, 取 $x = 2$, $y = -1$, 则 $\langle F(x), y - x\rangle = 0$, 但 $\langle F(y), y - x\rangle = 2*(-3) < 0$. 因此映射 $F$ 在 $\mathbb{R}$ 上不是伪单调的. $S = S_D = \{-1\}$. 显然映射 $T$ 是非扩张映射, 由注 2.1 可知映射 $T$ 是 $0$-半压缩映射且 $I - T$ 在 0 处是半闭的, ${\rm Fix}(T) = \{-1\}$. ${\rm Fix}(T)\cap S_D = \{-1\}\neq \emptyset$.

由于映射 $F$ 是拟单调映射, 不是单调或者伪单调的映射, 因此其它算法不适用于本例. 比较选取不同的 $u^0$ 对算法的影响, 分别取 $u^0 = 5$ ($u^0$ 不在 $C$ 中), $u^0 = 1$ ($u^0$ 在 $C$ 中但不靠近解), $u^0 = -1$ ($u^0$ 在 $C$ 中且靠近解).

算法 1 参数选取如下.

1. 算法 1: $r=1, \mathit{l}=0.5, \tau=0.5, \theta=0.5, \alpha_n=\frac{1}{n+1}, \varepsilon_n=\frac{100}{(n+1)^2}, \beta_n=\frac{n}{2n+1}$.

数值实验结果见表 4 和图 4.

通过表 4 和图 4 可以发现: 在其它参数相同的情况下, $u^0$ 的取值越靠近解集, 算法 1 的迭代步数越少, 迭代时间越短.