云南师范大学，数学学院，云南 昆明

收稿日期：2022年2月3日；录用日期：2022年2月25日；发布日期：2022年3月4日

摘要

本文考虑希尔伯特空间上的伪单调变分不等式的求解算法。在现有文献的基础上，通过引入自适应步长规则和结合粘性逼近法，给出了一个新的求解伪单调变分不等式问题的惯性次梯度外梯度方法，并在一般假设条件成立下，证明了新算法在希尔伯特空间中具有强收敛性。与现有文献相比，新算法的收敛条件减弱，并且新算法的收敛性更强。

关键词

伪单调，惯性次梯度外梯度，自适应投影算法，强收敛

A New Kind of Inertial Subgradient Extragradient Methods for Solving Pseudomonotone Variational Inequalities

Zeshuai Zhang, Feng Li^*

School of Mathematics, Yunnan Normal University, Kunming Yunnan

Received: Feb. 3^rd, 2022; accepted: Feb. 25^th, 2022; published: Mar. 4^th, 2022

ABSTRACT

In this paper, we consider an algorithm for solving pseudomonotone variational inequalities in Hilbert Spaces. Based on the existing literature, a new Inertial Subgradient Extragradient method for solving pseudomonotone variational inequalities is presented by introducing adaptive step rule and viscous approximation method. And under the general assumptions, it is proved that the new algorithm has strong convergence in Hilbert space. Compared with the existing literature, the convergence condition of the new algorithm is weakened, and the convergence of the new algorithm is stronger.

Keywords:Pseudomonotone, Inertial Subgradient External Gradient, Adaptive Projection Algorithm, Strong Convergence

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

变分不等式 $VI\left(C,A\right)$ 的定义是指：找到 $x^{*}\in C$，使得下式成立：

$\langle A{x}^{*},x-x^{*}\rangle ,\forall x\in C$

其中 $A:H\to H$ 是一个映射，C是实希尔伯特空间H上的一个非空闭凸集。本文把上式的解集记作 $Sol\left(C,A\right)$。变分不等式在产生于生活中的不同领域，例如：力学、金融学等，并且它在交通问题、网络问题、信号处理等方面都有广泛的应用。

解决变分不等式问题的方法多为投影算法，Goldstein以及Levitin和Polyak在文献 [1] 和 [2] 提出了用于求解变分不等式的梯度投影法，其迭代格式为：

$y^k=x^k-{\beta }_k\nabla f(\; x\; k\; )$

$x^{k+1}=P_C(\; y\; k\; )$

现如今研究求解变分不等式的算法得到了许多学者的关注，大多数新的算法的基本思想都可以看作是对梯度投影法的扩展。例如，将 $\nabla f\left(x^k\right)$ 替换为 $A{x}^k$，可以看作是梯度投影法的一个扩展，即：

$y^k=x^k-{\beta }_{k}A{x}^k$

$x^{k+1}=P_C(\; y\; k\; )$

该算法收敛所需要的条件为算子A是Lipschitz连续且强单调的，因为这两个条件太过严格，所以此算法不能够广泛地使用。

为避免这些严格的条件，Korpelevich在文献 [3] 中提出了外梯度方法：

$y^k=P_C\left(x^k-\tau A{x}^k\right)$

$x^{k+1}=P_C\left(x^k-\tau A{y}^k\right)$

其中， $\tau \in \left(0,1/L\right)$，L为算子A的Lipschitz常数，此算法收敛所需条件为算子A是Lipschitz连续且单调的，弱化了梯度投影法中的A为强单调性的条件，提升了算法的可使用性，但此算法也存在着缺点：每完成一次迭代需要作两次在集合C上的投影，若C是一般的非空闭凸集，则此算法的效率将会大大降低。

为克服外梯度方法存在的缺陷，Censor在文献 [4] 中提出了次梯度外梯度算法：

$y^k=P_C\left(x^k-\tau A{x}^k\right)$

$T_k=\left\{w\in H|\langle x^k-\tau A{x}^k-y^k,w-y^k\rangle \le 0\right\}$

$x^{k+1}=P_{T_k}\left(x^k-\tau A{y}^k\right)$

由于计算在一个包含约束闭凸集C的半空间上的投影所需的计算成本比直接计算在原约束闭凸集C的投影的计算成本要小，故此算法相比外梯度方法提高了算法的效率。

现如今，许多学者将惯性思想与已有算法进行结合，得到了新的效率更高的算法，例如Dong Q L，Cho Y J和Zhong L L [5] 给出了惯性投影收缩算法，Duong和Dang [6]，Thong D V，Vinh N T和Cho Y J [7] 均给出了惯性次梯度外梯度算法，这些算法均使用了固定步长，并且算法都需要估计算子A的Lipschitz常数，而估计算子的Lipschitz常数难度较大，实际操作中也较难实现。本文所提出的算法是在文献 [6] 的基础上提出了一种新的求解伪单调变分不等式的惯性次梯度外梯度粘性方法，其中文献 [6] 中算法的迭代格式如下：

$\begin{array}{l}{\omega }^k=x^k+{\alpha }_k\left(x^k-x^{k-1}\right)\\ y^k=P_C\left({\omega }^k-\tau A{\omega }^k\right)\\ T_k=\left\{x\in H|\langle {\omega }^k-\tau A{\omega }^k-y^k,x-y^k\rangle \le 0\right\}\\ x^{k+1}=P_{T_k}\left({\omega }^k-\tau A{y}^k\right)\end{array}$

本文所提的新的算法不仅不需要估计算子A的Lipschitz常数，并且新算法还可用于求解伪单调变分不等式问题，同时证明了新算法强收敛于伪单调变分不等式的一个解。

2. 预备知识

定义1：设映射 $A:H\to H$

1) 映射A称作是单调的，如果

$\langle Ax-Ay,x-y\rangle \ge 0,\forall x,y\in H$

2) 映射A称作是伪单调的，如果

$\langle Ax,y-x\rangle \ge 0\Rightarrow \langle Ay,y-x\rangle \ge 0,\forall x,y\in H$

由定义可知任意一个单调映射一定是伪单调映射，反之则不一定成立。

引理1 [8]：若 $x\in H$，$z\in C$，则

$z\in P_C\left(x\right)\iff \langle x-z,y-z\rangle \ge 0,\forall y\in C$

引理2 [8]：若 $x\in H$，则

${\Vert P_C\left(x\right)-P_C\left(y\right)\Vert }^2\le \langle P_C\left(x\right)-P_C\left(y\right),x-y\rangle ,\forall y\in H$

引理3 [9]：对于 $A:H\to H$，$x\in C$，$a\ge b>0$ 都有以下不等式成立：

$\frac{\Vert x-P_C\left(x-aAx\right)\Vert }{a}\le \frac{\Vert x-P_C\left(x-bAx\right)\Vert }{b}$,$\Vert x-P_C\left(x-bAx\right)\Vert \le \Vert x-P_C\left(x-aAx\right)\Vert$

引理4 [10]：若变分不等式 $VIP\left(C,A\right)$，C是实Hilbert空间H中的一个非空闭凸子集， $A:C\to H$ 伪单调且连续，则

$x^{*}\in Sol\left(C,A\right)\iff \langle Ax,x-x^{*}\rangle \ge 0,\forall x\in C$

引理5 [11]：设 $\left\{{\phi }_k\right\},\left\{{\delta }_k\right\}$ 和 $\left\{{\beta }_k\right\}$ 均为非负序列，使得下式成立：

${\phi }_{k+1}\le {\phi }_k+{\beta }_k\left({\phi }_k-{\phi }_{k-1}\right)+{\delta }_k,\forall k\ge 1,{\displaystyle \underset{k=1}{\overset{+\infty }{\sum }}{\delta }_k}<+\infty$

并且存在一个实数 $\beta$，使得对于 $\forall k\in \mathbb{N}$ 都有 $0\le {\beta }_k\le \beta <1$，则以下结论成立：

1) ${\displaystyle \underset{k=1}{\overset{+\infty }{\sum }}{\left[{\phi }_k-{\phi }_{k-1}\right]}_{+}}<+\infty$，其中 ${\left[t\right]}_{+}=\max \left\{t,0\right\}$

2) 存在 ${\phi }^{*}\in \left[0,+\infty \right)$，使得 $\underset{k\to +\infty }{\lim }{\phi }_k={\phi }^{*}$

引理6 [12]：设C是实Hilbert空间H中的一个非空闭凸子集，若 $\left\{x^k\right\}\subset H$ 且满足以下两个条件：

1) 对于 $\forall x\in C$，$\underset{k\to \infty }{\lim }\Vert x^k-x\Vert$ 存在

2) $\left\{x^k\right\}$ 的每个序列弱聚点均在C中

则 $\left\{x^k\right\}$ 弱收敛于C中某一点。

引理7 [7]：设 $\left\{a_n\right\}$ 是非负实数序列，使得

$a_{n+1}\le \left(1-{\alpha }_n\right)a_n+{\alpha }_n{b}_n,\forall n\ge 0$

其中 $\left\{{\alpha }_n\right\}\subset \left(0,1\right)$ 和 $\left\{b_n\right\}$ 两个序列满足：1) ${\displaystyle \underset{n=0}{\overset{\infty }{\sum }}{\alpha }_n}=\infty$ ；2) $\underset{n\to \infty }{\lim \sup }{b}_n\le 0$，则有 $\underset{n\to \infty }{\lim }{a}_n=0$。

引理8 [13]：设 $\left\{a_n\right\}$ 是非负实数序列，使得存在 $\left\{a_n\right\}$ 的子列 $\left\{a_{n_j}\right\}$，有 $a_{n_j}<a_{n_j+1},\forall j\in \mathbb{N}$，则存在递增的序列 $\left\{m_k\right\}\subset \mathbb{N}$，$\underset{k\to \infty }{\lim }{m}_k=\infty$，使得下列不等式成立：

$\begin{array}{cc}{a}_{m_k}\le a_{m_k+1},& a_k\le a_{m_k+1}\end{array},\forall k\in \mathbb{N}$

引理9 [14] (lamma 3.3)：若映射A满足本文假设条件， $\left\{{\omega }^k\right\}$ 是由算法所生成的序列，且存在 $\left\{{\omega }^k\right\}$ 的一个子列 $\left\{{\omega }^{k_j}\right\}$，使得 ${\omega }^{k_j}$ 弱收敛于 $z\in H$，且 $\underset{k\to \infty }{\lim }\Vert {\omega }^k-y^k\Vert =0$，则 $z\in Sol\left(C,A\right)$。

全文假设：

1) 可行集合C是H上的一个非空闭凸集；

2) $A:H\to H$ 在H上是伪单调且Lipschitz连续的，在C上是序列弱连续的；

3) $Sol\left(C,A\right)\ne \varnothing$。

3. 伪单调惯性次梯度外梯度粘性方法及其强收敛性

3.1. 伪单调惯性次梯度外梯度粘性算法

算法3.1：

Step 1：初始点 $x^0,x^1\in H$，初始值 $\epsilon >0$，$r_k>0$，$\gamma \in \left(0,2\right)$，$m,n\in \left(0,1\right)$，$\nu \in \left(0,1/2\right)$，$\alpha >0$，$k=1$

${\alpha }_k=\{\begin{array}{ll}\min \left\{\frac{1}{k^2\Vert x^k-x^{k-1}\Vert },\alpha \right\}\hfill & x^k\ne x^{k-1}\hfill \\ \alpha \hfill & x^k=x^{k-1}\hfill \end{array}$

Step 2： ${\omega }^k=x^k+{\alpha }_k\left(x^k-x^{k-1}\right)$，计算 ${\lambda }_k=r_k{\xi }^{m_k}$，$y^k=P_C\left({\omega }^k-\gamma {\lambda }_{k}A{\omega }^k\right)$

其中 $m_k$ 是使得下式成立的最小正整数m：

$r_k{\xi }^m\Vert A{\omega }^k-A{y}^k\Vert \le \nu \Vert {\omega }^k-y^k\Vert$

若 $\Vert {\omega }^k-y^k\Vert \le \epsilon$，则算法停止。

Step 3：令 $T_k=\left\{x\in H|\langle {\omega }^k-\gamma {\lambda }_{k}A{\omega }^k-y^k,x-y^k\rangle \le 0\right\}$，$z^k=P_{T_k}\left({\omega }^k-\gamma {\lambda }_{k}A{y}^k\right)$，计算

$x^{k+1}={\eta }_{k}f\left(x^k\right)+\left(1-{\eta }_k\right)z^k$

Step 4：如果 ${\lambda }_k\Vert A{\omega }^k-A{y}^k\Vert \le m\Vert {\omega }^k-y^k\Vert$，$r_{k+1}=\frac{{\lambda }_k}{n}$ ；否则 $r_{k+1}={\lambda }_k$。令 $k=k+1$，转step 2。

3.2. 算法的收敛性证明

设函数 $f:H\to H$ 是关于收缩参数 $\kappa \in \left[0,1\right)$ 的一个收缩映射，并且算法3.1中的序列 $\left\{{\eta }_k\right\}\subset \left(0,1\right)$，$\left\{{\alpha }_k\right\}$，$\left\{x_k\right\}$ 满足：

$\underset{k\to \infty }{\lim }{\eta }_k=0$,${\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{\eta }_k}=\infty$,$\underset{k\to \infty }{\lim }\frac{{\alpha }_k}{{\eta }_k}\Vert x^k-x^{k-1}\Vert =0$

为证明算法3.1的强收敛性，我们首先证明几个引理：

引理3.1 由算法3.1生成的序列 $\left\{x^k\right\}$ 有界。

由命题2.1和 $z^k$ 定义可得

${\Vert z^k-p\Vert }^2\le {\Vert {\omega }^k-p\Vert }^2-\left(1-\gamma \nu \right){\Vert {\omega }^k-y^k\Vert }^2-\left(1-\gamma \nu \right){\Vert z^k-y^k\Vert }^2$ (1)

因为 $0<\gamma \nu <1$，所以我们有

$\begin{array}{c}\Vert z^k-p\Vert \le \Vert {\omega }^k-p\Vert \\ =\Vert x^k+{\alpha }_k\left(x^k-x^{k-1}\right)-p\Vert \\ \le \Vert x^k-p\Vert +{\alpha }_k\Vert x^k-x^{k-1}\Vert \\ =\Vert x^k-p\Vert +{\eta }_k\frac{{\alpha }_k}{{\eta }_k}\Vert x^k-x^{k-1}\Vert ,k\ge 0\end{array}$ (2)

又因为 $\frac{{\alpha }_k}{{\eta }_k}\Vert x^k-x^{k-1}\Vert \to 0\left(k\to \infty \right)$，所以存在 $M_1>0$ 使得 $\frac{{\alpha }_k}{{\eta }_k}\Vert x^k-x^{k-1}\Vert \le M_1$

故(2)式等价于

$\Vert z^k-p\Vert \le \Vert {\omega }^k-p\Vert \le \Vert x^k-p\Vert +{\eta }_k{M}_1,\forall k\ge 0$ (3)

由 $x^{k+1}$ 的定义和范数的三角不等式可知

$\begin{array}{c}\Vert x^{k+1}-p\Vert =\Vert \left(1-{\eta }_k\right)z^k+{\eta }_{k}f\left(x^k\right)-p\Vert \\ =\Vert \left(1-{\eta }_k\right)\left(z^k-p\right)+{\eta }_k\left(f\left(x^k\right)-p\right)\Vert \\ \le \left(1-{\eta }_k\right)\Vert z^k-p\Vert +{\eta }_k\Vert f\left(x^k\right)-p\Vert \\ =\left(1-{\eta }_k\right)\Vert z^k-p\Vert +{\eta }_k\Vert f\left(x^k\right)-f\left(p\right)+f\left(p\right)-p\Vert \\ \le \left(1-{\eta }_k\right)\Vert z^k-p\Vert +{\eta }_k\Vert f\left(x^k\right)-f\left(p\right)\Vert +{\eta }_k\Vert f\left(p\right)-p\Vert \\ \le \left(1-{\eta }_k\right)\Vert z^k-p\Vert +{\eta }_k\kappa \Vert x^k-p\Vert +{\eta }_k\Vert f\left(p\right)-p\Vert \end{array}$ (4)

将(3)式代入(4)式得

$\begin{array}{c}\Vert x^{k+1}-p\Vert \le \left(1-{\eta }_k\right)\Vert x^k-p\Vert +{\eta }_k{M}_1+{\eta }_k\kappa \Vert x^k-p\Vert +{\eta }_k\Vert f\left(p\right)-p\Vert \\ =\left(1-{\eta }_k\left(1-\kappa \right)\right)\Vert x^k-p\Vert +{\eta }_k\left(M_1+\Vert f\left(p\right)-p\Vert \right)\\ =\left(1-{\eta }_k\left(1-\kappa \right)\right)\Vert x^k-p\Vert +{\eta }_k\left(1-\kappa \right)\left(\frac{M_1+\Vert f\left(p\right)-p\Vert }{1-\kappa }\right)\\ \le \max \left\{\Vert x^k-p\Vert ,\frac{M_1+\Vert f\left(p\right)-p\Vert }{1-\kappa }\right\}\\ \le \cdots \le \max \left\{\Vert x^0-p\Vert ,\frac{M_1+\Vert f\left(p\right)-p\Vert }{1-\kappa }\right\}\end{array}$

上式意味着 $\left\{x^k\right\}$ 有界。

引理3.2 若对于 $\gamma \in \left(0,2\right)$，$\nu \in \left(0,1/2\right)$，${\eta }_k\subset \left(0,1\right)$，$\left\{x^k\right\}$ 、 $\left\{y^k\right\}$ 、 $\left\{z^k\right\}$ 、 $\left\{{\omega }^k\right\}$ 是算法3.1所生成的序列，则 $\exists M_4>0$，使得下式成立：

$\left(1-\gamma \nu \right){\Vert {\omega }^k-y^k\Vert }^2+\left(1-\gamma \nu \right){\Vert z^k-y^k\Vert }^2\le {\Vert x^k-p\Vert }^2-{\Vert x^{k+1}-p\Vert }^2+{\eta }_k{M}_4$

由 $x^{k+1}$ 的定义，我们有

$\begin{array}{c}{\Vert x^{k+1}-p\Vert }^2\le {\eta }_k{\Vert f\left(x^k\right)-p\Vert }^2+\left(1-{\eta }_k\right){\Vert z^k-p\Vert }^2\\ \le {\eta }_k{\left(\Vert f\left(x^k\right)-f\left(p\right)\Vert +\Vert f\left(p\right)-p\Vert \right)}^2+\left(1-{\eta }_k\right){\Vert z^k-p\Vert }^2\\ \le {\eta }_k{\left(\kappa \Vert x^k-p\Vert +\Vert f\left(p\right)-p\Vert \right)}^2+\left(1-{\eta }_k\right){\Vert z^k-p\Vert }^2\\ \le {\eta }_k{\left(\Vert x^k-p\Vert +\Vert f\left(p\right)-p\Vert \right)}^2+\left(1-{\eta }_k\right){\Vert z^k-p\Vert }^2\\ ={\eta }_k{\Vert x^k-p\Vert }^2+\left(1-{\eta }_k\right){\Vert z^k-p\Vert }^2+{\eta }_k\left(2\Vert x^k-p\Vert \Vert f\left(p\right)-p\Vert +{\Vert f\left(p\right)-p\Vert }^2\right)\end{array}$

因为 $\Vert x^k-p\Vert$ 和 $\Vert f\left(p\right)-p\Vert$ 有界，所以存在 $M_2>0$，使得

${\Vert x^{k+1}-p\Vert }^2\le {\eta }_k{\Vert x^k-p\Vert }^2+\left(1-{\eta }_k\right){\Vert z^k-p\Vert }^2+{\eta }_k{M}_2$ (5)

又因为

$\begin{array}{c}{\Vert {\omega }^k-p\Vert }^2\le {\left(\Vert x^k-p\Vert +{\eta }_k{M}_1\right)}^2\\ ={\Vert x^k-p\Vert }^2+{\eta }_k\left(2\Vert x^k-p\Vert M_1+{\eta }_k{M}_1^2\right)\end{array}$

所以存在 $M_3>0$，使得

${\Vert {\omega }^k-p\Vert }^2\le {\Vert x^k-p\Vert }^2+{\eta }_k{M}_3$ (6)

因此结合(1) (5) (6)三式得

$\begin{array}{c}{\Vert x^{k+1}-p\Vert }^2\le {\eta }_k{\Vert x^k-p\Vert }^2+\left(1-{\eta }_k\right){\Vert z^k-p\Vert }^2+{\eta }_k{M}_2\\ \le {\eta }_k{\Vert x^k-p\Vert }^2+{\eta }_k{M}_2+\left(1-{\eta }_k\right){\Vert {\omega }^k-p\Vert }^2-\left(1-\gamma \nu \right){\Vert {\omega }^k-y^k\Vert }^2-\left(1-\gamma \nu \right){\Vert z^k-y^k\Vert }^2\\ \le {\eta }_k{\Vert x^k-p\Vert }^2+{\eta }_k{M}_2+\left(1-{\eta }_k\right){\Vert x^k-p\Vert }^2+{\eta }_k{M}_3-\left(1-\gamma \nu \right){\Vert {\omega }^k-y^k\Vert }^2-\left(1-\gamma \nu \right){\Vert z^k-y^k\Vert }^2\\ ={\Vert x^k-p\Vert }^2+{\eta }_k{M}_4-\left(1-\gamma \nu \right){\Vert {\omega }^k-y^k\Vert }^2-\left(1-\gamma \nu \right){\Vert z^k-y^k\Vert }^2\end{array}$

其中 $M_4=M_2+M_3$，上式移项即证。

引理3.3 若 $p\in Sol\left(C,A\right)$，$\left\{x^k\right\}$ 是由算法3.1所生成的序列，则必然存在正数M，使得下列不等式成立

${\Vert x^{k+1}-p\Vert }^2\le \left(1-\left(1-\kappa \right){\eta }_k\right){\Vert x^k-p\Vert }^2+\left(1-\kappa \right){\eta }_k\left[\frac{2}{1-\kappa }\langle f\left(p\right)-p,x^{k+1}-p\rangle +\frac{3M}{1-\kappa }\frac{{\alpha }_k}{{\eta }_k}\Vert x^k-x^{k-1}\Vert \right]$

根据 $x^{k+1}$ 和 ${\omega }^k$ 的定义，我们有

$\begin{array}{c}{\Vert x^{k+1}-p\Vert }^2={\Vert {\eta }_{k}f\left(x^k\right)+\left(1-{\eta }_k\right)z^k-p\Vert }^2\\ ={\Vert {\eta }_k\left(f\left(x^k\right)-f\left(p\right)\right)+\left(1-{\eta }_k\right)\left(z^k-p\right)+{\eta }_k\left(f\left(p\right)-p\right)\Vert }^2\\ \le {\Vert {\eta }_k\left(f\left(x^k\right)-f\left(p\right)\right)+\left(1-{\eta }_k\right)\left(z^k-p\right)\Vert }^2+2{\eta }_k\langle f\left(p\right)-p,x^{k+1}-p\rangle \\ \le {\eta }_k{\kappa }^2{\Vert x^k-p\Vert }^2+\left(1-{\eta }_k\right){\Vert z^k-p\Vert }^2+2{\eta }_k\langle f\left(p\right)-p,x^{k+1}-p\rangle \\ \le {\eta }_k\kappa {\Vert x^k-p\Vert }^2+\left(1-{\eta }_k\right){\Vert {\omega }^k-p\Vert }^2+2{\eta }_k\langle f\left(p\right)-p,x^{k+1}-p\rangle \end{array}$ (7)

$\begin{array}{c}{\Vert {\omega }^k-p\Vert }^2={\Vert x^k+{\alpha }_k\left(x^k-x^{k-1}\right)-p\Vert }^2\\ ={\Vert x^k-p\Vert }^2+2{\alpha }_k\langle x^k-p,x^k-x^{k-1}\rangle +{\alpha }_k^2{\Vert x^k-x^{k-1}\Vert }^2\\ \le {\Vert x^k-p\Vert }^2+2{\alpha }_k\Vert x^k-p\Vert \Vert x^k-x^{k-1}\Vert +{\alpha }_k^2{\Vert x^k-x^{k-1}\Vert }^2\end{array}$ (8)

结合(7) (8)得

$\begin{array}{c}{\Vert x^{k+1}-p\Vert }^2\le \left(1-\left(1-\kappa \right){\eta }_k\right){\Vert x^k-p\Vert }^2+2{\eta }_k\langle f\left(p\right)-p,x^{k+1}-p\rangle +2{\alpha }_k\Vert x^k-p\Vert \Vert x^k-x^{k-1}\Vert +{\alpha }_k{}^2{\Vert x^k-x^{k-1}\Vert }^2\\ \le \left(1-\left(1-\kappa \right){\eta }_k\right){\Vert x^k-p\Vert }^2+\left(1-\kappa \right){\eta }_k\frac{2}{1-\kappa }\langle f\left(p\right)-p,x^{k+1}-p\rangle \\ +{\alpha }_k\Vert x^k-x^{k-1}\Vert \left(2\Vert x^k-p\Vert +\alpha \Vert x^k-x^{k-1}\Vert \right)\\ \le \left(1-\left(1-\kappa \right){\eta }_k\right){\Vert x^k-p\Vert }^2+\left(1-\kappa \right){\eta }_k\frac{2}{1-\kappa }\langle f\left(p\right)-p,x^{k+1}-p\rangle +3M{\alpha }_k\Vert x^k-x^{k-1}\Vert \\ =\left(1-\left(1-\kappa \right){\eta }_k\right){\Vert x^k-p\Vert }^2+\left(1-\kappa \right){\eta }_k\frac{2}{1-\kappa }\langle f\left(p\right)-p,x^{k+1}-p\rangle +3M{\eta }_k\frac{{\alpha }_k}{{\eta }_k}\Vert x^k-x^{k-1}\Vert \\ =\left(1-\left(1-\kappa \right){\eta }_k\right){\Vert x^k-p\Vert }^2+\left(1-\kappa \right){\eta }_k\left[\frac{2}{1-\kappa }\langle f\left(p\right)-p,x^{k+1}-p\rangle +\frac{3M}{1-\kappa }\frac{{\alpha }_k}{{\eta }_k}\Vert x^k-x^{k-1}\Vert \right]\end{array}$

其中 $M=\underset{k\in \mathbb{N}}{\max }\left\{\Vert x^k-p\Vert ,\alpha \Vert x^k-x^{k-1}\Vert \right\}>0$。

最后利用以上所证引理，给出算法3.1的强收敛性证明：

定理3.1 若假设条件成立，则由算法3.1所生成的序列 $\left\{x^k\right\}$ 强收敛于 $p=P_{Sol\left(C,A\right)}\circ f\left(p\right)$。

证明：要证序列 $\left\{x^k\right\}$ 强收敛于p，即证 $\Vert x^k-p\Vert \to 0\left(k\to \infty \right)$，为此，本文分两种情况进行讨论

情况1： $\exists N\in \mathbb{N}$ 使得对于 $\forall k\ge N$ 时都有， ${\Vert x^{k+1}-p\Vert }^2\le {\Vert x^k-p\Vert }^2$

上述情况意味着极限 $\underset{k\to \infty }{\lim }\Vert x^k-p\Vert$ 存在，由引理4.2可知

$\Vert {\omega }^k-y^k\Vert \to 0,\Vert z^k-y^k\Vert \to 0$ (9)

又

$\Vert x^k-{\omega }^k\Vert ={\alpha }_k\Vert x^k-x^{k-1}\Vert ={\eta }_k\frac{{\alpha }_k}{{\eta }_k}\Vert x^k-x^{k-1}\Vert \to 0$ (10)

$\Vert x^{k+1}-z^k\Vert ={\eta }_k\Vert f\left(x^k\right)-z^k\Vert \to 0$ (11)

且

$\Vert x^{k+1}-x^k\Vert \le \Vert x^{k+1}-z^k\Vert +\Vert z^k-y^k\Vert +\Vert y^k-{\omega }^k\Vert +\Vert {\omega }^k-x^k\Vert$ (12)

结合(9) (10) (11) (12)得

$\Vert x^{k+1}-x^k\Vert \to 0$ (13)

根据上极限的性质可以得到，存在 $\left\{x^k\right\}$ 的子列 $\left\{x^{k_j}\right\}$，使得

$\underset{k\to \infty }{\lim \sup }\langle f\left(p\right)-p,x^k-p\rangle =\underset{j\to \infty }{\lim }\langle f\left(p\right)-p,x^{k_j}-p\rangle$

由引理3.1可知 $\left\{x^k\right\}$ 有界，故子列 $\left\{x^{k_j}\right\}$ 也有界，并且子列弱收敛于点 $z\in H$，则有

$\underset{k\to \infty }{\lim \sup }\langle f\left(p\right)-p,x^k-p\rangle =\underset{j\to \infty }{\lim }\langle f\left(p\right)-p,x^{k_j}-p\rangle =\langle f\left(p\right)-p,z-p\rangle$

由 $\Vert x^k-{\omega }^k\Vert \to 0$ 可知 ${\omega }^{k_j}$ 也弱收敛于点 $z\in H$，又由引理9可知 $z\in Sol\left(C,A\right)$，结合p的定义和(13)式得

$\underset{k\to \infty }{\lim \sup }\langle f\left(p\right)-p,x^{k+1}-p\rangle =\underset{k\to \infty }{\lim \sup }\langle f\left(p\right)-p,x^k-p\rangle =\langle f\left(p\right)-p,z-p\rangle \le 0$

因此结合引理3.3和引理7可得

$\underset{k\to \infty }{\lim }\Vert x^k-p\Vert =0$

情况2：存在 ${\Vert x^k-p\Vert }^2$ 的一个子列 ${\Vert x^{k_j}-p\Vert }^2$，使得对于 $\forall j\ge 1$，满足

${\Vert x^{k_j}-p\Vert }^2<{\Vert x^{k_j+1}-p\Vert }^2$

根据引理8，存在满足 $\underset{k\to \infty }{\lim }{m}_k=\infty$ 的递增序列 $\left\{m_k\right\}$，使得对于 $\forall k\ge 1$，都有

$\begin{array}{cc}{\Vert x^{m_k}-p\Vert }^2\le {\Vert x^{m_k\text{+1}}-p\Vert }^2,& {\Vert x^k-p\Vert }^2\le {\Vert x^{m_k+1}-p\Vert }^2\end{array}$ (14)

由引理3.2得

$\left(1-\gamma \nu \right){\Vert {\omega }^{m_k}-y^{m_k}\Vert }^2+\left(1-\gamma \nu \right){\Vert z^{m_k}-y^{m_k}\Vert }^2\le {\Vert x^{m_k}-p\Vert }^2-{\Vert x^{m_k+1}-p\Vert }^2+{\eta }_{m_k}{M}_4\le {\eta }_{m_k}{M}_4$

因为 ${\eta }_{m_k}\to 0$，所以

$\underset{k\to \infty }{\lim }\Vert {\omega }^{m_k}-y^{m_k}\Vert =0$

同理依据情况1的证明过程可以得到

$\underset{k\to \infty }{\lim }\Vert x^{m_k+1}-x^{m_k}\Vert =0$

由引理3.3和(14)式得

$\begin{array}{c}{\Vert x^{m_k+1}-p\Vert }^2\le \left(1-{\eta }_{m_k}\left(1-\kappa \right)\right){\Vert x^{m_k}-p\Vert }^2+{\eta }_{m_k}\left(1-\kappa \right)\left[\frac{2}{1-\kappa }\langle f\left(p\right)-p,x^{m_k+1}-p\rangle +\frac{3M}{1-\kappa }\frac{{\alpha }_{m_k}}{{\eta }_{m_k}}\Vert x^{m_k}-x^{m_k-1}\Vert \right]\\ \le \left(1-{\eta }_{m_k}\left(1-\kappa \right)\right){\Vert x^{m_k+1}-p\Vert }^2+{\eta }_{m_k}\left(1-\kappa \right)\left[\frac{2}{1-\kappa }\langle f\left(p\right)-p,x^{m_k+1}-p\rangle +\frac{3M}{1-\kappa }\frac{{\alpha }_{m_k}}{{\eta }_{m_k}}\Vert x^{m_k}-x^{m_k-1}\Vert \right]\end{array}$

对上式进行化简得到

${\Vert x^{m_k+1}-p\Vert }^2\le \frac{2}{1-\kappa }\langle f\left(p\right)-p,x^{m_k+1}-p\rangle +\frac{3M}{1-\kappa }\frac{{\alpha }_{m_k}}{{\eta }_{m_k}}\Vert x^{m_k}-x^{m_k-1}\Vert$ (15)

因此

$\underset{k\to \infty }{\lim \sup }\Vert x^{m_k+1}-p\Vert \le 0$ (16)

结合(14) (16)两式，得 $\underset{k\to \infty }{\lim \sup }\Vert x^k-p\Vert \le 0$，这意味着 $\underset{k\to \infty }{\lim }\Vert x^k-p\Vert =0$，证明完毕。

4. 结语

随着算法迭代的增加，算法所生成的迭代点越来越靠近最优解点，若算法迭代在接近最优解点时仍使用固定步长，有时会导致迭代步数增加，进而影响算法的效率。本文借鉴已有算法思路，引入了自适应步长准则，利用了粘性逼近法构造出了新的算法，该算法不仅具有强收敛性，而且新算法不用估计算子的Lipschitz常数，更具有实用性；除此之外，新算法的收敛条件相对于原算法有所减弱。

文章引用

张泽帅,李 峰. 一类新的伪单调惯性次梯度外梯度粘性方法
A New Kind of Inertial Subgradient Extragradient Methods for Solving Pseudomonotone Variational Inequalities[J]. 应用数学进展, 2022, 11(03): 888-897. https://doi.org/10.12677/AAM.2022.113095

参考文献