设 $H$ 是一个 Hilbert 空间, $C$ 为 $H$ 中的非空闭凸子集, $F:H\rightarrow H$ 为一个连续映射, 记$\langle\cdot,\cdot\rangle$, $\|\cdot,\cdot\|$ 分别为 $H$ 中的内积和范数, 并记 $P_{C}(x)$ 为点 $x\in H$ 到 $C$ 上的投影, 即

本文考虑如下的经典变分不等式问题, 记为 VI($F,C$): 寻找一个向量 $x^{*}\in C$ 使得

记 $S$ 为 VI($F,C$) 的解集, $S_{D}$ 为 VI($F,C$) 的对偶变分不等式的解集, 其中

由于 $F$ 在 $C$ 上为连续映射, 且 $C$ 为 $H$ 中的非空闭凸子集, 故 $S_{D}\subset S$. 若 $F$ 在 $C$ 上是伪单调映射, 则有 $S\subset S_{D}$. 因此, 若 $F$ 在$C$ 上为连续映射, $C$ 为 $H$ 中的非空闭凸子集, 且 $F$ 在 $C$ 上是伪单调映射时, 我们有

参见文献[引理 2.1]. 在 $S=S_{D}$ 的假设条件下考虑变分不等式的投影类型的数值算法有很多, 参见文献[2⇓⇓⇓⇓⇓⇓⇓⇓-11]. 但当 $F$ 退化为拟单调连续映射时, 存在 $S_{D}\subset S$ 的例子, 参见文献[12]中的例 4.2. 因此, 考虑非单调变分不等式的算法成为了一个热点. 例如, 在 2014 年, 为了削弱映射 $F$ 的单调性, Ye 和 He^[12] 提出了一种求解非单调变分不等式的双投影算法, 证明了在 $R^{n}$ 中假设 $S_{D}\neq\emptyset$ 时算法生成序列的全局收敛性. 然而, 这个算法的迭代点 $x_{k+1}$ 是一个向量投影到可行集 $C$ 和 $k+1$ 个半空间的交所产生, 因此计算 $x_{k+1}$ 的计算机耗时将会随着 $k$ 的增加而增加. 最近, He^[13] 阐明了如果 $C\subset R$ ($R$ 为一维的欧氏空间)是一个有界闭集, 那么 $S_{D}\neq\emptyset$ 当且仅当 $F$ 在 $C$ 上是拟单调的. 因此, 在2020 年, Liu 和 Yang^[14] 基于 Tseng^[5] 的梯度投影算法在 Hilbert 空间中提出了一种求解拟单调变分不等式的自适应算法, 在假设条件 $S_{D}\neq\emptyset$; 映射 $F:H\rightarrow H$ 具有 $L$-Lipschitz 连续性且 $L>0$; 映射 $F$ 在 $H$ 上为序列弱连续; 映射 $F$ 在 $H$ 上拟单调; 且集合 $\{z\in C|F(z)=0\}\backslash S_{D}$ 为有限集的假设下得到了算法的全局弱收敛性. 算法如下

最近,Ye^[15] 给出了一种在 $n$ 维欧氏空间中求解非单调变分不等式的投影算法, 该算法在 $S_D\neq\emptyset$, $F:R^{n}\rightarrow R^{n}$ 连续的条件下得到了算法的全局收敛性, 并且该算法的新迭代点由当前迭代点向一个半空间投影生成.

惯性方法由Polyak^[16] 提出, 通过利用前一迭代点的信息来加速凸极小化算法. 现已被用去加速变分不等式算法^{[17⇓⇓⇓-21]}. 其中, Wang^[17] 等利用惯性方法来加速算法, 给出了求解 Hilbert 空间中拟单调变分不等式的算法, 且在 $F(z)\neq0, \forall z\in C$ 的假设条件下得到了算法的全局弱收敛性, 其惯性系数 $\alpha_n$ 的取值如下.

选取 $0\leq\alpha_n\leq\bar{\alpha}_n$, 这里的

其中 $0<\alpha<1$, $\{\epsilon_n\}$ 为一个正实数序列.

注意到惯性算法的生成点与解集的距离没有 Fejer 单调性. 因此, 当惯性系数为一个固定常数并且算法所生成的迭代点趋近于变分不等式的解时, 迭代点到变分不等式解集的距离会出现反复震荡的情形, 参见文献[21]. 因此, 本文中的惯性系数没有取常数, 而是把惯性系数修改为随着迭代步数单调递减趋于 0.

本文主要采取了变动的惯性系数来加速文献[14]中的算法, 其中惯性系数的选取参见后面的 (3.1)式. 并且, 本文在与文献[14]相同的假设条件下证明了算法的全局弱收敛性. 数值实验表明通过选取合适的参数能够使得新算法比文献[14]中的算法有更少的迭代步数和计算机耗时, 见注 4.1.

本节中我们用 $F:H\rightarrow H$ 表示一个连续映射, $H$ 为一个Hilbert 空间, $C$ 为 $H$ 中的一个非空闭凸子集, $P_{C}(x)$ 为点 $x\in H$ 到 $C$ 上的投影, 即 $P_{C}(x):={\rm argmin}\{\|y-x\||y\in C\}.$并用 $\langle\cdot,\cdot\rangle$, $\|\cdot,\cdot\|$ 分别表示 $H$ 中的内积和范数. $R^m$ 表示 $m$ 维的欧式空间, $R_{+}^{m}$ 为 $R^m$ 的非负卦象.下面介绍本文的一些定义和引理, 它们将用于算法的收敛性分析.

定义2.1 (i)若映射 $F$ 满足

则称 $F$ 在 $H$ 上是单调的；

(ii)若映射 $F$ 满足

则称 $F$ 在 $H$ 上是伪单调的；

(iii)若映射 $F$ 满足

则称 $F$ 在 $H$ 上是拟单调的；

(iv)若存在常数 $L>0$, 满足

则称映射 $F$ 在 $H$ 上 $L$-Lipschitz连续.

引理2.1^[22] 设 $C$ 为 $H$ 中的一个非空闭凸子集, 那么对于任意固定的 $x\in H$, 都有

引理2.2^[23] 对任意的 $x,y\in H$, $\lambda\in R$ 则有

引理2.3^[23] 设 $C$ 为 $H$ 中的一个非空闭凸子集, $\{x_n\}$ 为 $H$ 中的序列, 若满足

(i) 对任意的 $x\in C$, $\lim\limits_{n\rightarrow\infty}\|x_n-x\|$ 存在；

(ii) 序列 $\{x_n\}$ 的任意弱聚点都属于 $C$. 那么, 序列 $\{x_n\}$ 弱收敛到 $C$ 中的一点.

引理2.4^[24] 设 $\{a_n\}$, $\{b_n\}$, $\{\theta_n\}$ 为 $[0,+\infty)$ 中的实数序列. 若对于任意的 $n\geq1$ 都存在一个实数 $\theta$, 使得

那么有以下结论成立

(a) $\sum\limits_{n=1}^{+\infty}[a_n-a_{n-1}]<+\infty$, 这里的 $[t]_{+}:=\max\{t,0\}$;

(b) 存在一个 $a^*\in[0,+\infty)$, 使得 $\lim\limits_{n\rightarrow\infty}a_n=a^*$.

为了考虑变分不等式问题, 本文还做了如下假设

(A) 映射 $F$ 在 $H$ 上为 $L$-Lipschitz连续, 其中 $L>0$;

(B) $S_D\neq\emptyset$;

(C) 映射 $F$ 在 $H$ 上为序列弱连续, 即对于 $H$ 中的一个序列 $\{x_n\}$, 当 $\{x_n\}$ 弱收敛到一点 $x$, 都有 $\{F(x_n)\}$ 弱收敛到 $F(x)$;

(D) 映射 $F$ 在 $H$ 上拟单调;

(E) 集合 $\{z\in C|F(z)=0\}\backslash S_D$ 为有限集.

在这一节里, 我们主要介绍算法及其收敛性分析. 我们先介绍算法如下.

算法 3.1 步骤1 选取初始点 $x_{-1}=x_{0}\in H$ 以及参数 $0<\mu<1, \lambda_0>0$. 此外, 选取正实数序列 $\{p_n\}$, $\{\varepsilon_n\}$, $\{\beta_n\}$, 并且满足 $\sum\limits_{n=0}^{+\infty}p_n<+\infty$, $\sum\limits_{n=0}^{+\infty}\varepsilon_n<+\infty$, $\{\beta_n\}$单调递减趋于 0. 取 $n:=0$.

步骤2 选取 $\alpha_n$, 使得 $0\leq\alpha_n\leq\bar{\alpha}_n\leq\beta_0$, 其中

步骤3

如果 $\omega_n=y_n$ 或者 $F(y_n)=0$, 停止. 否则进行步骤 4.

步骤4

步骤5

步骤6 令 $n:=n+1$, 返回步骤 2.

注3.1 注意到惯性算法的生成点与解集的距离没有 Fejer单调性. 因此, 本文的惯性系数 $\alpha_n$ 由 (3.1) 式中的$\bar{\alpha}_n$ 所确定. 通过让 $\{\beta_n\}$ 为一单调递减趋近于 $0$ 的实数列, 可以迫使 $\{\alpha_n\}$ 也是一个单调递减趋近于 $0$ 的实数列. 此外, 若 $\beta_n=0,\forall n$, 则算法3.1退化为文献[14]中的算法3.1.

引理 3.1 设 $\{\lambda_n\}$ 为算法3.1 所生成的序列, $\{p_n\}$ 满足算法 3.1 中步骤 1 的假设条件, 且 $p=\sum\limits_{n=0}^{+\infty}p_n$. 那么

证 见文献[引理 3.1].

引理 3.2 假设条件 (a), (b) 成立, $\{x_n\}$, $\{y_n\}$, $\{\omega_n\}$, $\{\alpha_n\}$, $\{\lambda_n\}$ 为算法3.1所生成的序列, $\{\varepsilon_n\}$, $\{\beta_n\}$ 满足算法 3.1中步骤1的假设条件. 则我们有以下结论成立

(a) 对于任意固定 $u\in S_D$, $\lim\limits_{n\rightarrow\infty}\|x_n-u\|$ 存在. 进而可知序列 $\{x_n\}$ 是有界的；

(b) $\lim\limits_{n\rightarrow\infty}\|\omega_n-y_n\|= \lim\limits_{n\rightarrow\infty}\|x_{n+1}-x_n\|= \lim\limits_{n\rightarrow\infty}\|x_n-y_n\|=0$.

证 (a)对于任意固定的 $u\in S_D$, 由 (3.4) 式可得

由 $y_n$ 的定义以及引理 2.1 有 $\langle y_n-\omega_n+\lambda_nF(\omega_n),y_n-u\rangle\leq0$, 变形后可化为

于是结合(3.6)式, 可以得到如下不等式关系

这里的第二个不等式的成立是依据 $y_n\in C, u\in S_D$, 第三个不等式的成立是根据 (3.5) 式中$\lambda_{n+1}$ 的定义得出. 接下来, 利用引理 3.1 以及 $0<\mu<1$ 可得

结合(3.7)式可知, 存在一个正整数 $N_0$, 都有

另一方面, 由 (3.2) 式中 $\omega_n$ 的定义以及引理 2.2 可得

结合(3.9)式通过变形可以得到, 对于任意的 $n\geq N_0$, 都有

在(3.1)式中, 根据 $\bar{\alpha}_n$ 的定义, 可以观察到

那么

最后由引理 2.4 以及 (3.11), (3.13) 式可以推出结论 (a) 成立. 下面证明结论 (b) 成立.

通过利用 (3.9), (3.10) 式可以观察到对于任意的 $n\geq N_0$ 都有

因此, 由结论 (a) 以及 $0\leq\alpha_n\leq\beta_n\leq\beta_0$, 对 (3.14) 式取 $n\rightarrow\infty$, 则有

再结合 (3.7) 和 (3.8) 式可得

接下来, 由 (3.4)式, 引理 3.1 以及 $F$ 的 $L$-Lipschitz连续性可得

再由 (3.15)式, 则

此外, 通过利用 (3.15), (3.16)式, 以及三角不等式

可得

另外, 由(3.2)式中 $\omega_n$ 的定义可以知道

那么

再由 (3.17)式, $0\leq\alpha_n\leq\beta_n\rightarrow0, n\rightarrow\infty$ 以及序列 $\{x_n\}$ 的有界性, 可得

最后, 利用(3.16),(3.18)式和三角不等式 $\|x_n-y_n\|\leq\|x_n-x_{n+1}\|+\|x_{n+1}-y_n\|$ 可以推出 $\lim\limits_{n\rightarrow\infty}\|x_n-y_n\|=0$. 故结论 (b) 成立.

引理 3.3 假设条件 (A)-(D) 成立, $\{x_n\}$, $\{y_n\}$, $\{\omega_n\}$ 为算法3.1所生成的序列. 设 $\bar{x}$ 为 $\{x_n\}$ 的任一弱聚点, 则 $\bar{x}\in C$, 并且我们还有 $F(\bar{x})=0$ 或 $\bar{x}\in S_D$.

证 由引理 3.2(a) 可知, 序列 $\{x_n\}$ 是有界的. 因此, 设 $\bar{x}$ 为 $\{x_n\}$ 的任一弱聚点, 即存在 $\{x_n\}$ 的子序列$\{x_{n_k}\}$, 使得当 $k\rightarrow\infty$ 时, 有 $\{x_{n_k}\}$ 弱收敛到 $\bar{x}$. 此外, 根据引理 3.2(b)可知, 当 $k\rightarrow\infty$ 时, $\{y_{n_k}\}$ 与$\{\omega_{n_k}\}$ 均弱收敛到 $\bar{x}$. 由于 $\{y_n\}\subset C$, 且 $C$ 为 $H$ 中的非空闭凸子集($C$ 为弱闭集), 有 $\bar{x}\in C$.下面分两种情形进行讨论.

情形1 当 $\limsup\limits_{k\rightarrow\infty}\|F(y_{n_k})\|=0$ 时, 可得出 $F(\bar{x})=0$. 证明过程同文献 [引理 3.3].

情形2 当 $\limsup\limits_{k\rightarrow\infty}\|F(y_{n_k})\|>0$ 时, 那么存在一个常数 $K\in N$,使得 $\|F(y_{n_k})\|>0$, $\forall k>K$. 利用引理 2.1 以及 (3.3)式中 $y_n$ 的定义可得

那么对于任意固定的 $x\in C$, 利用 (3.19) 式以及 $\lambda_n>0, \forall n$ 可推出

由引理 3.1, 引理 3.2(b) 以及 $F$ 的 Lipschitz 连续性可得

当 $\limsup\limits_{k\rightarrow\infty}\langle F(y_{n_k}),x-y_{n_k}\rangle>0$ 时, 即 $\{y_{n_k}\}$ 存在一个子序列 $\{y_{n_{k_i}}\}$ 满足

这意味着存在一个正整数 $N_1$ 使得

再由 $F$ 的拟单调性以及 $\{y_{n_{k_i}}\}$ 弱收敛到 $\bar{x}$ 可推出

当 $\limsup\limits_{k\rightarrow\infty}\langle F(y_{n_k}),x-y_{n_k}\rangle=0$ 时, 根据 (3.20) 式可以推出

设

那么

取 $z_{n_k}=\frac{F(y_{n_k})}{\|F(y_{n_k})\|^{2}}, \forall k>K,$即 $\langle F(y_{n_k}), z_{n_k}\rangle=1$, 结合 (3.22) 式可得

则

由 $F$ 在 $H$ 上的拟单调性可知

这意味着

因此

下面说明 $\lim\limits_{k\rightarrow\infty}\eta_kz_{n_k}=0$. 因为 $F$ 在 $H$上为序列弱连续且 $\{y_{n_k}\}$ 弱收敛到 $\bar{x}$, 所以 $\{F(y_{n_k})\}$ 弱收敛到 $F(\bar{x})$.这结合范数的弱下半连续性可知

由此, 结合 $\eta_k$ 与 $z_{n_k}$ 的定义以及 $\lim\limits_{k\rightarrow\infty}\eta_k$ 存在可知

即 $\lim\limits_{k\rightarrow\infty}\eta_kz_{n_{k}}=0$.

由 $F$ 在 $H$ 上具有 Lipschitz 连续性可知 $\{F(x+\eta_kz_{n_k})\}$ 是有界的. 现对(3.23)式取 $k\rightarrow\infty$, 于是可推出 $\langle F(x),x-\bar{x}\rangle\geq0, \forall x\in C$. 最后结合(3.21) 式可知 $\bar{x}\in S_D$.证毕.

引理 3.4 假设条件 (A)-(E) 成立, $\{x_n\}$ 为算法 3.1所生成的序列, 则 $\{x_n\}$ 弱收敛到 $S$ 中一点.

证 设 $A_{x}$ 为 $\{x_n\}$ 的所有弱聚点构成的集合. 则由引理 3.3 可知 $A_{x}\subset C$.下面我们分情况讨论.

情况1 若存在 $\tilde{x}\in A_{x}$ 使得 $\tilde{x}\in S_D$. 此时, 则由引理 3.2(a) 可知$\lim\limits_{n\rightarrow\infty}\|x_n-\tilde{x}\|$ 存在. 因此, 不妨设 $x_n-\tilde{x}\rightarrow a(n\rightarrow\infty)$, 其中 $a$ 为一常数. 由此, 结合 $\tilde{x}$ 为 $\{x_n\}$ 的弱聚点可知 $a=0$. 进而结合 $S_D\subset S$ 可知结论成立.

情况2 若对任意的 $\tilde{x}\in A_{x}$ 都有 $\tilde{x}\notin S_D$, 则由引理 3.3 可知 $F(\tilde{x})=0$. 因此, 我们有 $A_{x}\subset\{z\in C|F(z)=0\}\backslash S_D$. 这结合假设条件 (E) 可知 $A_{x}$ 为有限集. 因此, 文献[14]中的引理3.5成立. 进而,结合引理3.2(b)中的 $\lim\limits_{n\rightarrow\infty}\|x_{n+1}-x_n\|=0$ 以及文献[14] 中的定理3.1可知 $\{x_n\}$ 弱收敛到 $S$ 中一点.证毕.

本节中, 我们通过数值实验来比较本文算法 3.1 (简记为 YCY) 及 Liu 和 Yang^[14] 的算法 3.1 (简记为 LY). 使用的工具是 R2014a 版本的 MATLAB 在 CPU 型号为 Intel(R) Core(TM) i3-1000NG4 (四核, 主频 1.10GHz) 和内存为 8.0GB 的笔记本电脑上运行的. LY 的参数选取见文献[14], 即 $\mu=0.5, \lambda_0=1, p_n=\varepsilon_n=\frac{100}{(n+1)^{1.1}}$. YCY 的参数选取方案如下.

YCY1: $\mu=0.5, \lambda_0=1, p_n=\varepsilon_n=\frac{100}{(n+1)^{1.1}}, \beta_n=\frac{1}{100ln(n+2)}$;

YCY2: $\mu=0.5, \lambda_0=1, p_n=\varepsilon_n=\frac{100}{(n+1)^{1.1}}, \beta_n=\frac{1}{0.286(n+1)ln(n+2)}$;

YCY3: $\mu=0.5, \lambda_0=1, p_n=\varepsilon_n=\frac{100}{(n+1)^{1.1}}, \beta_n=\frac{1}{n+1}$;

YCY4: $\mu=0.5, \lambda_0=1, p_n=\varepsilon_n=\frac{100}{(n+1)^{1.1}}, \beta_n=(\frac{1\cdot3\cdot\cdot\cdot(2n-1)}{2\cdot4\cdot\cdot\cdot2n})^3$.

YCY与 LY 的终止条件分别为$\|\omega_n-y_n\|/\min\{\lambda_n, 1\}\leq\varepsilon$, $\|x_n-y_n\|/\min\{\lambda_n, 1\}\leq\varepsilon$. 用 cpu (单位:秒)来记计算机的耗时, 用 iter 来记算法迭代的步数. 定义 $x_{-1}=x_0$ 为 YCY 的初始点, $x_0$ 为 LY 的初始点. 取 $\varepsilon=10^{-6}$. YCY 与 LY 的数值结果均取 MATLAB 运行5次后的平均值.

例4.1 本例被文献[14]用于拟单调变分不等式问题的算法检验. 设$C=[-1,1]$.

例4.2 本例被文献[25] 用于单调变分不等式问题的算法检验. 设

这里的向量 $d$ 中的每一个元素从 $(-500,0)$ 中随机产生. 对于随机矩阵$M=NN^{T}+S+D\in R^{m\times m}$, 其中, $N\in R^{m\times m}$ 为一个随机矩阵, $S\in R^{m\times m}$为一个随机反对称矩阵, $D\in R^{m\times m}$ 为一个随机对角矩阵, 这里 $S$ 与 $D$ 中的每一个元素分别于 $(-5,5)$ 与 $(0,0.3)$ 中随机产生. 因此, $M$ 为正定矩阵, 且 $F$ 为$L$-Lipschitz连续, 其 Lipschitz 常数 $L=\|M\|$.

例4.3 本例在 $R^m$ 中用来测试与比较YCY和LY的数值实验结果. 在维数 $m=5$ 时, 本例被文献[12]用于拟单调变分不等式的算法检验. 设

其中 $H=hI$, $I\in R^{m\times m}$ 为单位矩阵, $h\in(0.1,1.6)$, $q=(-1,\cdots,-1)^{T}\in R^m$, $r=1$, 则 $G$ 是 $C$ 上的光滑拟凸函数. 令 $F(x)=(F_{1}(x),\cdots F_{m}(x))^{T}$为$G(x)$ 的导函数, 则

因此, VI($F,C$) 是拟单调变分不等式, 且$S_D=\{(\frac{a}{m},\cdots,\frac{a}{m})\}$.

注4.1 从表1-表3可以看出:当YCY的参数选取方案为YCY2时, 算法YCY(惯性的 LY)比LY有更少的迭代步数和计算机耗时.