数学物理学报, 2022, 42(3): 904-919 doi:

论文

关于伪单调变分不等式与不动点问题的新投影算法

杨静,, 龙宪军,

重庆工商大学数学与统计学院 重庆 400067

A New Projection Algorithm for Solving Pseudo-Monotone Variational Inequality and Fixed Point Problems

Yang Jing,, Long Xianjun,

College of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067

通讯作者: 龙宪军, E-mail: xianjunlong@ctbu.edu.cn

收稿日期: 2021-08-12  

基金资助: 国家自然科学基金.  11471059
重庆市自然科学基金.  cstc2021jcyj-msxmX0721
重庆市教育委员会科学技术研究重点项目.  KJZD-K201900801

Received: 2021-08-12  

Fund supported: NSFC.  11471059
the NSF of Chongqing.  cstc2021jcyj-msxmX0721
the Education Committee Project Research Foundation of Chongqing.  KJZD-K201900801

作者简介 About authors

杨静,E-mail:jyang1230@163.com , E-mail:jyang1230@163.com

Abstract

In this paper, we propose a new projection algorithm for finding a common element of psedomonotone variational inequality problems and fixed point set of demicontractive mappings in Hilbert spaces. We prove that this new algorithm converges strongly to the common element for a psedomonotone and uniformly continuous mapping. Finally, we provide some numerical experiments to illustrate the efficiency and advantages of the new projection algorithm.

Keywords: Variational inequality ; Fixed point ; Projection algorithm ; Uniformly continuous ; Pseudomonotone

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

本文引用格式

杨静, 龙宪军. 关于伪单调变分不等式与不动点问题的新投影算法. 数学物理学报[J], 2022, 42(3): 904-919 doi:

Yang Jing, Long Xianjun. A New Projection Algorithm for Solving Pseudo-Monotone Variational Inequality and Fixed Point Problems. Acta Mathematica Scientia[J], 2022, 42(3): 904-919 doi:

1 引言

$ H $是具有内积$ \langle \cdot, \cdot\rangle $和范数$ \|\cdot\| $的一个实Hilbert空间, $ C $$ H $中的非空闭凸子集. 设$ x\in H $, 记$ P_{C}(x) $$ x $$ C $上的投影. 设$ F: H\rightarrow H $是一个非线性映射. 变分不等式问题就是寻找点$ x\in C $使得

$ \begin{eqnarray} \langle F(x), y-x\rangle \geq 0, \; \; \forall y\in C. \end{eqnarray} $

记问题(1.1)的解集为$ VI(C, F) $. 变分不等式问题作为最优化理论的一个重要分支, 近年来受到了许多学者的关注. 这主要是由于变分不等式在图像处理、机器学习、博弈论、非线性规划等领域有着十分重要的应用[1-2]. 早期求解变分不等式问题的数值方法是由Goldstein[3]提出的投影算法: $ x_{n+1}=P_{C}(x_{n}-\alpha F(x_{n})), $其中$ \alpha>0 $, $ F $是强单调且Lipschitz连续的. 为了弱化强单调性这一条件, Tseng[4]提出了如下改进的投影算法

其中$ \lambda\in(0, \frac{1}{L}) $, $ F $是单调且Lipschitz连续的($ L $为Lipschitz常数). 由于这类算法是一种具有较快收敛速度的一步投影算法, 近年来受到了学者们的关注和推广[5-10].

另一方面, 求解非线性算子不动点的算法受到了许多学者的关注. 设$ U:H\rightarrow H $$ \alpha $ -半压缩映射(详见定义2.2). 若$ Ux=x $, 则称$ x $$ U $的不动点. 用$ Fix(U) $表示映射$ U $的不动点集合, 即$ Fix(U):=\{x\in H |Ux=x \} $. 最近, 一些学者提出了新的投影算法求解变分不等式解集与不动点集的公共元[11-14]. 例如, Thong和Hieu[12]提出了如下投影算法

其中

$ F $是单调和Lipschitz连续的假设下, Thong和Hieu[12]证明了上述算法迭代产生的序列$ \{x_{n}\} $强收敛到变分不等式问题解集与半压缩映射不动点解集的一个公共元. 注意到单调性是比较强的条件, 如何弱化这一条件是本文将要考虑的问题.

最近, 郭丹妮和蔡钢[13]提出了如下投影算法

其中$ \tau_{n}=\lambda l^{m_{n}} $, $ m_{n} $为满足下式成立的最小非负整数

在伪单调和一致连续的条件下, 郭丹妮和蔡钢[13]证明了上述算法弱收敛到变分不等式问题解集与伪非扩张映射不动点集的一个公共元. 值得注意的是郭丹妮和蔡钢[13]提出的算法需要计算两次投影. 这不仅增加了算法的计算量, 而且还会影响算法的收敛速度.

受到上述工作的启发, 本文提出了新的一步投影算法, 找到了变分不等式解集与半压缩映射不动点集的一个公共元. 在伪单调和一致连续条件下, 证明了新算法的强收敛定理. 通过数值实验可以发现, 我们得到的结果推广和提高了许多最新的结果.

2 相关定义与引理

$ x_{n}\rightharpoonup x $$ \{x_{n}\} $弱收敛于$ x $. 任意给定$ u, v \in H, \alpha \in (0, 1) $, 有

任给$ x\in H $, 则存在$ C $中唯一的最近点$ P_{C}(x) $满足$ \|x-P_{C}(x)\| \leq \|x-y\|, \; \forall y \in C. $这里$ P_{C} $叫做$ H $$ C $上的投影. 易知$ P_{C} $$ H $$ C $上的非扩张映射.

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

(ⅰ) $ F $是伪单调[15]的, 如果

(ⅱ) $ F $是Lipschitz连续的, 如果

其中$ L $为Lipschitz常数且$ L>0 $.$ L=1 $, 则称$ F $是非扩张的; 若$ L \in (0, 1) $, 则称$ F $是压缩映射.

(ⅲ) $ F $是弱序列连续的, 如果对任意的序列$ \{x_{n}\} $满足$ x_{n} \rightharpoonup x $, 有$ F(x_{n}) \rightharpoonup F(x) $.

定义2.2[1, 3]  设$ U:H \rightarrow H $是映射满足$ Fix(U)\neq \emptyset $.

(ⅰ) $ I-U $在零点是半闭的, 如果

(ⅱ) $ U $$ \alpha $ -半压缩映射, 如果$ \forall x \in H $, $ \forall z\in Fix(U) $, 都存在$ 0\leq \alpha < 1 $满足

事实上, 上述定义等价于

也等价于

$ \alpha=0 $, 则称$ U $是拟非扩张映射. 显然, 拟非扩张映射是半压缩映射, 但是反之不成立, 见文献[16]中例2.

引理2.1[17]  设$ C $$ H $的非空闭凸子集, 给定$ x\in H $, $ z\in C $.

引理2.2[18]  设$ C $$ H $的非空闭凸子集, 给定$ x \in H $以及$ \alpha \geq \beta >0 $, 则有

引理2.3[19]  设$ \{a_{n_{j}}\} $是非负实序列$ \{a_{n}\} $的子列, 且存在子列满足对任意的正整数$ j $都有$ {a_{n_{j}} <a_{n_{j+1}}} $, 则存在非降整数序列$ \{m_{k}\} $满足: $ \limsup\limits_{k\rightarrow \infty} m_{k}=\infty, $且当$ k \in N $充分大时有$ a_{m_{k}} \leq a_{m_{k+1}} $, $ a_{k} \leq a_{m_{k+1}} $. 事实上$ m_{k} $是集合$ \{1, \cdots , k\} $中满足$ a_{n} < a_{n+1} $的最大整数.

引理2.4[20]  设$ \{a_{n}\} $是非负实数列, 满足$ a_{n+1} \leq (1-\eta_{n})a_{n}+\eta_{n} b_{n}, n \geq 0, $这里$ \eta_{n} \in (0, 1) $$ \{b_{n}\} $$ R $中的一个数列满足: (ⅰ) $ \sum\limits_{n=1}^{+\infty}\eta_{n} = \infty $, (ⅱ) $ \limsup\limits_{n\rightarrow \infty} b_{n} \leq 0 $, 则$ \lim\limits_{n\rightarrow \infty}a_{n} = 0 $.

本文假设

$ (C_{1}) $$ f:H \rightarrow H $是压缩映射且压缩系数$ \rho \in [0, 1) $.

$ (C_{2}) $$ U:H \rightarrow H $$ \alpha $ -半压缩映射且$ I-U $在零点是半闭的.

$ (C_{3}) $映射$ F:H \rightarrow H $是伪单调的, 在$ C $中的有界集上是一致连续的并且在$ C $上是序列弱连续的.

$ (C_{4}) $$ VI(C, F) \cap Fix(U) $非空.

$ (C_{5}) $$ \{\alpha_{n}\} \in (0, 1) $, $ \sum\limits_{n=1}^{+\infty}\alpha_{n} = \infty $, $ \lim\limits_{n\rightarrow \infty}\alpha_{n} =0 $, $ 0<c\leq\beta_{n}<1-\alpha\leq1 $, 其中$ c>0 $以及$ \alpha $为映射$ U $的半压缩系数.

3 算法与收敛性证明

本文提出如下算法:

算法3.1  选取$ \lambda_{0} >0 $, $ l\in(0, 1) $, $ \mu\in(0, 1) $, $ \gamma > 0 $. 选取初始点$ x_{0}\in H $.

步骤1  计算

其中$ \lambda_{n}=\gamma l^{m_{n}} $$ m_{n} $是使下式成立的最小非负整数$ m $:

$ \begin{equation} \gamma l^{m}\left\|F(x_{n})-F(y_{n})\right\|\leq\mu\left\|x_{n}-y_{n}\right\|. \end{equation} $

步骤2  计算

其中$ z_{n}=y_{n}+\lambda_{n}(F(x_{n})-F(y_{n})). $

步骤3  计算

$ n=n+1, $并回到步骤1.

引理3.1  假设$ (C_{3}) $$ (C_{4}) $成立, 则线性搜索准则$ (3.1) $是有意义的, 且$ \lambda_{n} \leq \gamma $.

  证明过程类似于文献[8]中引理3.1的证明过程, 故这里不再赘述.

引理3.2  假设$ (C_{3}) $$ (C_{4}) $成立, $ \{x_{n}\} $是算法$ 3.1 $迭代产生的序列. 如果存在$ \{x_{n}\} $的子列$ \{x_{n_{k}}\} $满足$ \{x_{n_{k}}\} $弱收敛于$ z \in H $$ \lim\limits_{n \rightarrow \infty}\| x_{n_{k}}-y_{n_{k}}\|=0 $, 则$ z \in VI(C, F) $.

  由$ y_{n_{k}}=P_{C}(x_{n_{k}}-\lambda_{n_{k}}F(x_{n_{k}})) $

从而

$ \begin{equation} \frac{1}{\lambda_{n_{k}}} \langle x_{n_{k}}-y_{n_{k}}, x-y_{n_{k}}\rangle +\langle F(x_{n_{k}}), y_{n_{k}}-x_{n_{k}}\rangle \leq\langle F(x_{n_{k}}), x-x_{n_{k}}\rangle, \; \; \forall x \in C. \end{equation} $

下证

$ \begin{equation} \liminf\limits_{k\rightarrow \infty}\langle F(x_{n_{k}}), x-x_{n_{k}}\rangle\geq0. \end{equation} $

考虑以下两种情形: 首先考虑$ \liminf\limits_{k \rightarrow \infty}\lambda_{n_{k}}>0 $.$ x_{n_{k}}\rightharpoonup z $可知$ \{x_{n_{k}}\} $是有界的. 由$ F $在有界集$ H $上的一致连续性知$ F(x_{n_{k}}) $是有界的. 在(3.2)式中令$ k \rightarrow \infty $, 根据$ \lim\limits_{n \rightarrow \infty}\| x_{n_{k}}-y_{n_{k}}\|=0 $可得

现考虑$ \liminf\limits_{k \rightarrow \infty}\lambda_{n_{k}}=0 $.$ z_{n_{k}}=P_{C}(x_{n_{k}}-\lambda_{n_{k}} l^{-1}F(x_{n_{k}})) $. 观察到$ \lambda_{n_{k}} l^{-1} >\lambda_{n_{k}} $. 由引理2.2知

$ \lim\limits_{k \rightarrow \infty}\| x_{n_{k}}-z_{n_{k}}\|=0 $.$ \{y_{n_k}\}\subseteq C $, $ x_{n_{k}} \rightharpoonup z $以及$ \lim\limits_{n \rightarrow \infty}\| x_{n_{k}}-y_{n_{k}}\|=0 $可知$ z \in C $. 进一步有$ z_{n_{k}}\rightharpoonup z \in C $, 从而$ \{z_{n_{k}}\} $有界. 根据$ F $的一致连续性得

$ \begin{equation} \lim\limits_{k \rightarrow \infty}\| F(x_{n_{k}})-F(z_{n_{k}})\|=0. \end{equation} $

根据线搜索准则(3.1)知

$ \begin{equation} \frac{\|F(x_{n_{k}})-F(z_{n_{k}})\|}{\mu} > \frac{\|x_{n_{k}}-z_{n_{k}}\|}{\lambda_{n_{k}}l^{-1}}. \end{equation} $

联立(3.4)和(3.5)式可得$ \lim\limits_{k \rightarrow \infty} \frac{\|x_{n_{k}}-z_{n_{k}}\|}{\lambda_{n_{k}}l^{-1}}=0. $结合$ \{z_{n_{k}}\} $的定义有$ \langle x_{n_{k}}-\lambda_{n_{k}}l^{-1}F(x_{n_{k}})-z_{n_{k}}, x-z_{n_{k}}\rangle \leq 0, \forall x \in C, $从而

在上式中令$ k \rightarrow \infty $$ \liminf\limits_{k \rightarrow \infty}\langle F(x_{n_{k}}), x-x_{n_{k}}\rangle \geq 0 $. 从而(3.3)式得证.

另一方面, 观察到

$ \begin{equation} \langle F(y_{n_{k}}), x-y_{n_{k}}\rangle=\langle F(y_{n_{k}})-F(x_{n_{k}}), x-x_{n_{k}}\rangle+\langle F(x_{n_{k}}), x-x_{n_{k}}\rangle+\langle F(y_{n_{k}}), x_{n_{k}}-y_{n_{k}}\rangle. \end{equation} $

$ \lim\limits_{n \rightarrow \infty}\| x_{n_{k}}-y_{n_{k}}\|=0 $以及$ F $的一致连续性知

联立(3.3)和(3.6)式可得

下证$ z\in VI(C, F) $.$ \{\varepsilon_{k}\} $为单调递减且趋近于0的正实数列. 对每一个$ \varepsilon_{k} $, 记$ N_{k} $为满足下式的最小正整数

$ \begin{equation} \langle F(y_{n_{j}}), x-y_{n_{j}}\rangle+\varepsilon_{k}\geq0, \forall j\in N_{k}. \end{equation} $

$ \{\varepsilon_{k}\} $是递减序列知$ \{N_{k}\} $是递增序列. 从而对于每一个$ \varepsilon_{k} $, 由$ \{y_{N_{k}}\}\subset C $$ F(y_{N_{k}})\neq 0 $.

易知$ \langle F(y_{N_{k}}), v_{N_{k}}\rangle=1 $. 联立(3.7)式可知, 对任意的$ k \in N_{k} $都有

根据$ F $的伪单调性知$ \langle F(x+\varepsilon_{k}v_{N_{k}}), x+\varepsilon_{k}v_{N_{k}}-y_{N_{k}}\rangle\geq0. $故有

$ \begin{equation} \langle F(x), x-y_{N_{k}}\rangle\geq \langle F(x)-F(x+\varepsilon_{k}v_{N_{k}}), x+\varepsilon_{k}v_{N_{k}}-y_{N_{k}}\rangle-\varepsilon_{k}\langle F(x), v_{N_{k}}\rangle. \end{equation} $

下证$ \lim\limits_{n\rightarrow \infty}\varepsilon_{k}v_{N_{k}}=0 $. 事实上, 由$ x_{n_{k}}\rightharpoonup z $以及$ \| x_{n_{k}}-y_{n_{k}}\| \rightarrow 0 $$ y_{n_{k}}\rightharpoonup z $($ k\rightarrow \infty $). 由于$ F $$ H $的有界闭集上序列弱连续, 故$ F(y_{n_{k}})\rightharpoonup F(z) $.$ F(z)=0 $, 则$ z $是变分不等式的一个解. 若$ F(z)\neq0 $, 由$ (C_{3}) $

$ \{y_{N_{k}}\} $$ \subseteq $$ \{y_{n_{k}}\} $以及$ \varepsilon_{k}\rightarrow0(k \rightarrow \infty) $

$ \lim\limits_{n\rightarrow \infty}\varepsilon_{k}v_{N_{k}}=0 $, 由(3.8)式和$ F $的一致连续性得

因此, 对任意的$ x \in C $

根据文献[21]中引理2.1可知$ z \in VI(C, F) $. 证毕.

定理3.1  假设$ (C_{1}) $$ (C_{4}) $成立, 则由算法3.1迭代产生的序列$ \{x_{n}\} $是有界的.

  该定理的证明分为以下三步进行.

第一步: 设$ q\in VI(C, F) $, 首先证明

$ \begin{equation} \|z_{n}-q\| \leq\|x_{n}-q\|. \end{equation} $

事实上, 由$ z_{n}=y_{n}+\lambda_{n}(F(x_{n})-F(y_{n})) $可得

$ \begin{eqnarray} \left\|z_{n}-q\right\|^{2}&=&\left\|y_{n}+\lambda_{n}(F(x_{n})-F(y_{n}))-q\right\|^{2}\\ &=&\left\|y_{n}-q\right\|^{2}+\lambda_{n}^{2}\left\|F(x_{n})-F(y_{n})\right\|^{2}+2\lambda_{n}\langle y_{n}-q, F(x_{n})-F(y_{n})\rangle\\ &=&\left\|y_{n}-x_{n}\right\|^{2}+\left\|x_{n}-q\right\|^{2}+2\langle y_{n}-x_{n}, x_{n}-q\rangle+\lambda_{n}^{2}\left\|F(x_{n})-F(y_{n})\right\|^{2}\\ &&+2\lambda_{n}\langle y_{n}-q, F(x_{n})-F(y_{n})\rangle\\ &=&\left\|x_{n}-q\right\|^{2}-\left\|y_{n}-x_{n}\right\|^{2}+\lambda_{n}^{2}\left\|F(x_{n})-F(y_{n})\right\|^{2}\\ &&+ 2\langle y_{n}-(x_{n}-\lambda_{n}F(x_{n})), y_{n}-q\rangle-2\lambda_{n}\langle y_{n}-q, F(y_{n})\rangle\\ &\leq&\left\|x_{n}-q\right\|^{2}-(1-\mu^{2})\left\|y_{n}-x_{n}\right\|^{2}+ 2\langle y_{n}-(x_{n}-\lambda_{n}F(x_{n})), y_{n}-q\rangle\\ &&-2\lambda_{n}\langle y_{n}-q, F(y_{n})\rangle. \end{eqnarray} $

$ q\in VI(C, F) $以及$ F $的伪单调性有

$ \begin{equation} \langle y_{n}-q, F(y_{n})\rangle \geq 0. \end{equation} $

又因为$ y_{n}=P_{C}(x_{n}-\lambda_{n}F(x_{n})) $, 根据引理2.1知对任意的$ y \in C $

$ \begin{equation} \langle y_{n}-(x_{n}-\lambda_{n}F(x_{n})), y_{n}-q\rangle \leq 0. \end{equation} $

联立(3.10)–(3.12)式可得

$ \begin{eqnarray} \left\|z_{n}-q\right\|^{2} &\leq &\left\|x_{n}-q\right\|^{2}-(1-\mu^{2})\left\|y_{n}-x_{n}\right\|^{2}+ 2\langle y_{n}-(x_{n}-\lambda_{n}F(x_{n})), y_{n}-q\rangle\\ && -2\lambda_{n}\langle y_{n}-q, F(y_{n})\rangle\\ &\leq& \left\|x_{n}-q\right\|^{2}-(1-\mu^{2})\left\|y_{n}-x_{n}\right\|^{2}. \end{eqnarray} $

从而(3.9)式得证.

第二步: 证明

$ \begin{equation} \|q_{n}-q\| \leq\|z_{n}-q\|. \end{equation} $

观察到

$ \begin{eqnarray} \left\|q_{n}-q\right\|^{2}&=&\left\|(1-\beta_{n})z_{n}+\beta_{n}U(z_{n})-q\right\|^{2}\left\|(1-\beta_{n})(z_{n}-q)+\beta_{n}(U(z_{n})-q)\right\|^{2}\\ &=&(1-\beta_{n})\left\|z_{n}-q\right\|^{2}+\beta_{n}\left\|U(z_{n})-q\right\|^{2} -\beta_{n}(1-\beta_{n})\left\|U(z_{n})-z_{n}\right\|^{2}. \end{eqnarray} $

因为$ U $$ \alpha $ -半压缩映射, 由定义2.2以及(3.13)式可得

$ \begin{eqnarray} \left\|q_{n}-q\right\|^{2}&\leq&(1-\beta_{n})\left\|z_{n}-q\right\|^{2}+ \beta_{n}(\left\|z_{n}-q\right\|^{2}+\alpha\left\|U(z_{n})-z_{n}\right\|^{2})\\ &&-\beta_{n}(1-\beta_{n})\left\|U(z_{n})-z_{n}\right\|^{2}\\ &=&\left\|z_{n}-q\right\|^{2}-\beta_{n}(1-\alpha-\beta_{n})\left\|U(z_{n})-z_{n}\right\|^{2}. \end{eqnarray} $

$ \{\beta_{n}\} $的定义以及(3.16)式可得(3.14)式成立.

第三步: 证明算法3.1迭代产生的序列$ \{x_{n}\} $有界. 事实上, 存在正整数$ n_{0} $使得

故算法3.1迭代产生的序列$ \{x_{n}\} $有界, 从而$ \{f(x_{n})\} $, $ \{q_{n}\} $$ \{z_{n}\} $也是有界的.

定理3.2  假设$ (C_{1}) $$ (C_{5}) $成立, 则算法3.1迭代产生的序列$ \{x_{n}\} $强收敛到$ q \in VI(C, F)\cap Fix(U) $, 这里$ q=P_{Fix(U) \cap VI(C, F)}\circ f(q) $.

  该定理的证明分为以下三步进行.

第一步: 证明

$ \begin{eqnarray} &&\beta_{n}(1-\alpha_{n})(1-\alpha-\beta_{n})\left\|U(z_{n})-z_{n}\right\|^{2}+(1-\alpha_{n})(1-\mu^{2})\left\|y_{n}-x_{n}\right\|^{2}\\ &\leq&\alpha_{n}\left\|f(x_{n})-q\right\|^{2}+\left\|x_{n}-q\right\|^{2}-\left\|x_{n+1}-q\right\|^{2}. \end{eqnarray} $

观察到

$ \begin{eqnarray} \left\|x_{n+1}-q\right\|^{2} &=&\left\|\alpha_{n}f(x_{n})+(1-\alpha_{n})q_{n}-q\right\|^{2}\\ &=&\left\|\alpha_{n}(f(x_{n})-q)+(1-\alpha_{n})(q_{n}-q)\right\|^{2}\\ &=&\alpha_{n}\left\|f(x_{n})-q\right\|^{2}+(1-\alpha_{n})\left\|q_{n}-q\right\|^{2} -\alpha_{n}(1-\alpha_{n})\left\|f(x_{n})-q_{n}\right\|^{2}\\ &\leq&\alpha_{n}\left\|f(x_{n})-q\right\|^{2}+(1-\alpha_{n})\left\|q_{n}-q\right\|^{2}. \end{eqnarray} $

将(3.13)和(3.16)式代入(3.18)式得

由此可得(3.17)式成立.

第二步: 证明

$ \begin{equation} \left\|x_{n+1}-q\right\|^{2} \leq(1-\alpha_{n}(1-\rho))\left\|x_{n}-q\right\|^{2}+\alpha_{n}(1-\rho)\frac{2}{1-\rho}\langle f(q)-q, x_{n+1}-q\rangle. \end{equation} $

事实上

由于$ f $是压缩映射, 结合(3.9)和(3.15)式可得

$ \begin{eqnarray} \left\|x_{n+1}-q\right\|^{2} &\leq &\alpha_{n}\left\|f(x_{n})-f(q)\right\|^{2}+(1-\alpha_{n})\left\|q_{n}-q\right\|^{2} +2\alpha_{n}\langle f(q)-q, x_{n+1}-q\rangle \\ &\leq& \alpha_{n}\rho\left\|x_{n}-q\right\|^{2}+(1-\alpha_{n})\left\|x_{n}-q\right\|^{2} +2\alpha_{n}\langle f(q)-q, x_{n+1}-q\rangle\\ &=&(1-\alpha_{n}(1-\rho))\left\|x_{n}-q\right\|^{2}+\alpha_{n}(1-\rho)\frac{2}{1-\rho}\langle f(q)-q, x_{n+1}-q\rangle. \end{eqnarray} $

故(3.19)式成立.

第三步: 证明序列$ \{\|x_{n}-q\|^{2}\} $收敛到零, 即算法3.1产生的序列$ \{x_{n}\} $强收敛到$ VI(C, F)\cap Fix(U) $中的一个元. 下面将分两种情况进行讨论.

情形1  若存在正整数$ N $, 当$ n\geq N $时, 有$ \|x_{n+1}-q\|^{2} \leq \|x_{n}-q\|^{2} $, 这说明$ \lim\limits_{n \rightarrow \infty}\|x_{n}-q\|^{2} $存在. 结合$ \{\alpha_{n}\} $, $ \{\beta_{n}\} $的定义以及(3.17)式可得

$ \begin{equation} \lim\limits_{n\rightarrow \infty}\|x_{n}-y_{n}\|=0, \end{equation} $

$ \begin{equation} \lim\limits_{n\rightarrow \infty}\|z_{n}-Uz_{n}\|=0. \end{equation} $

另一方面

根据(3.21)式可得

$ \begin{equation} \lim\limits_{n\rightarrow \infty}\|z_{n}-y_{n}\|=0. \end{equation} $

联立(3.21)和(3.23)式有

$ \begin{equation} \lim\limits_{n\rightarrow \infty}\|z_{n}-x_{n}\|=0. \end{equation} $

对于$ q_{n}=(1-\beta_{n})z_{n}+\beta_{n}U(z_{n}) $, 由(3.22)式可得

$ \begin{equation} \lim\limits_{n\rightarrow \infty}\|q_{n}-z_{n}\|=0. \end{equation} $

注意到$ x_{n+1}=\alpha_{n} f(x_{n})+(1-\alpha_{n})q_{n} $, 故

$ \begin{eqnarray} \left\|x_{n+1}-x_{n}\right\| &=&\left\|\alpha_{n}f(x_{n})+(1-\alpha_{n})q_{n}-x_{n}\right\|\\ &\leq& \alpha_{n}\left\|f(x_{n})-x_{n}\right\|+(1-\alpha_{n})\left\|q_{n}-x_{n}\right\|\\ &\leq& \alpha_{n}\left\|f(x_{n})-x_{n}\right\|+\left\|q_{n}-x_{n}\right\|\\ &\leq& \alpha_{n}\left\|f(x_{n})-x_{n}\right\|+\left\|q_{n}-z_{n}\right\|+\left\|z_{n}-x_{n}\right\|. \end{eqnarray} $

结合(3.24)–(3.26)式可得

$ \begin{equation} \lim\limits_{n\rightarrow \infty}\|x_{n+1}-x_{n}\|=0. \end{equation} $

因为$ \{x_{n}\} $有界, 所以存在$ \{x_{n}\} $的收敛子列$ \{x_{n_{k}}\} $$ x^{*} \in H $使得$ x_{n_{k}}\rightharpoonup x^{*} $且满足

下证: $ x^{*} \in VI(C, F)\cap Fix(U) $. 注意到$ x_{n_{k}}\rightharpoonup x^{*} $, 故由(3.21)式和引理3.2可得$ x^{*} \in VI(C, F) $. 另一方面, 由(3.24)式可得$ z_{n_{k}}\rightharpoonup x^{*} $. 又因为$ I-U $在零点是半闭的, 故由(3.22)式可得$ x^{*} \in Fix(U) $. 因此$ x^{*}\in VI(C, F) \cap Fix(U) $.

$ q=P_{Fix(U) \cap VI(C, F)} \circ f(q) $以及引理2.1知

注意到$ x^{*}\in VI(C, F) \cap Fix(U) $, 故$ \langle f(q)-q, x^{*}-q\rangle \leq 0 $. 从而有

因此, 由(3.27)式可得

由(3.19)式和引理2.4可得$ \lim\limits_{n\rightarrow \infty}\|x_{n}-q\|=0 $, 即算法3.1迭代产生的序列$ \{x_{n}\} $强收敛到$ q $.

情形2  若存在$ \{\|{x_{n}-q}\|^{2}\} $的子序列$ \{\|{x_{n_{j}}}-q\|^{2}\} $满足$ \|{x_{n_{j}}}-q\|^{2} \leq \|{x_{n_{j}+1}}-q\|^{2} $, 则由引理2.3知, 存在非降整数序列$ m_{k} $使得$ \lim\limits_{k\rightarrow \infty} m_{k} = \infty $以及

$ \begin{equation} \|{x_{k}}-q\|^{2} \leq \|x_{m_{k}+1}-q\|^{2}. \end{equation} $

根据(3.17)式可得

由假设条件可得

类似情形1的证明可得

$ \begin{equation} \limsup\limits_{k\rightarrow \infty}\langle f(q)-q, x_{m_{k}+1}-q\rangle \leq 0. \end{equation} $

由(3.20)式可得

从而

$ \begin{equation} \left\|x_{m_{k}+1}-q\right\|^{2} \leq \frac{2}{1-\rho}\langle f(q)-q, x_{m_{k}+1}-q\rangle. \end{equation} $

由(3.28)–(3.30)式得

即算法3.1迭代产生的序列$ \{x_{n}\} $强收敛到$ q $.

注3.1  定理3.2从以下三个方面改进了文献[12]中定理3.5:

(ⅰ) 映射$ F $的单调性弱化为伪单调性;

(ⅱ) $ F $的Lipschitz连续性弱化为一致连续性;

(ⅲ) 算法3.1中步长的选取与文献[12]中算法3.2不同. 事实上, 我们的步长选择更优.

4 数值实验

为了体现本文所给算法的数值效果, 本节通过例子将算法3.1与文献[7]中算法4、文献[8]中算法1和算法2、文献[12]中算法3.1和算法3.2以及文献[13] 中算法3.1进行比较. 文中所有代码都是在MATLAB R2018a和Windows 10系统下运行的. 计算机基本参数为Intel Core(TM)i5-7300HQ CPU@2.50GHz和16GB内存, 其中"Iter" 表示算法迭代次数, "CPU time" 表示程序运算的时间, 单位为秒.

例4.1  设映射$ F: {{\Bbb R}} ^m\rightarrow {{\Bbb R}} ^m $

其中$ Q $是正定矩阵, $ P $是半正定矩阵, $ q\in {{\Bbb R}} ^m $$ \beta>0 $. 易知, $ F $是一个伪单调映射但不是单调映射. 取$ C:=\{x\in {{\Bbb R}} ^m|Bx\leq b\} $, 这里$ B $$ p\times m $阶矩阵以及$ b \in {{\Bbb R}} _{+}^p $.$ p=10 $.$ f(x)=0.5x, Ux=-\frac{3x}{2} $, 由文献[12]知, $ U $$ \alpha $ -半压缩映射$ (\alpha=\frac{1}{5}) $.$ \alpha_{n}=\frac{1}{n+1} $以及$ \beta_{n}=0.1 $ ($ n $为迭代次数). 其它参数分别取为$ l=0.5 $以及$ \lambda_{1}=0.5 $. 停机条件为$ \left\|x_{n}-y_{n}\right\| \leq 10^{-8} $. 在此条件下, 我们探究了$ m $, $ \gamma $以及$ f $的选取对算法3.1的影响, 具体数值结果如图 1图 2以及表 1所示. 通过图 1图 2表 1可以发现: 本文算法3.1收敛到变分不等式问题解集和不动点问题的一个公共元, 且收敛速度与空间的维数$ m $, $ \gamma $的选择以及压缩映射$ f $的选取有关.

图 1

图 1   例1 $ m=60 $, $ f(x)=0.5x $时, 不同$ \gamma $下算法3.1的对比


图 2

图 2   例1 $ f(x)=0.5x $, $ \left\|x_{n}-y_{n}\right\| \leq 10^{-8} $时, 不同$ m, \; \gamma $下算法3.1的迭代次数对比


表 1   例4.1 $\gamma=0.5$, 算法3.1不同情况的展现

$f(x)$$m=30$$m=60$$m=90$
IterCPU timeIterCPU timeIterGPU time
$\frac{x}{4}$510.8511520.7227520.7869
$\frac{x}{2}$530.7082580.8453620.9145
$\frac{\sin(x)}{2}$550.7157530.6831570.9798
$\frac{\cos(x)}{2}$2365.74413189.468942719.516

新窗口打开| 下载CSV


例4.2  设映射$ F: {{\Bbb R}} ^m\rightarrow {{\Bbb R}} ^m $满足$ F(x)=Mx+q $[12], 这里$ q\in {{\Bbb R}} ^m $$ M=NN^{T}+S+D, $其中$ N, S, D \in {{\Bbb R}} ^{m\times m} $, $ S $斜对称矩阵, $ D $对角元素非负的对角矩阵. 容易得到$ F $是一个单调且Lipschitz连续的映射, 其中Lipschitz常数$ L=\|M\| $. 可行集$ C=\{x\in {{\Bbb R}} ^m \mid Bx \leq b\} $, 这里$ B \in {{\Bbb R}} ^{k\times m} $, $ b \in {{\Bbb R}} ^{k}_{+} $分别是随机产生的$ k\times m $阶矩阵和$ k\times 1 $阶非负向量. 定义映射$ U: {{\Bbb R}} ^m\rightarrow {{\Bbb R}} ^m $$ Ux=\frac{x}{2}\sin x $. 由文献[12] 知, $ U $是一个$ \alpha $ -半压缩映射$ (\alpha=0) $.$ f(x)=0.5x $, $ \alpha_{0}=0.1 $, $ \beta_{0}=0.1 $, $ \lambda_{0}=0.5 $, $ \gamma=0.5 $, $ k=10 $, $ l=\mu=0.5 $, $ \alpha_{n}=\frac{1}{n+1} $, $ \beta_{n}=\frac{n}{2n+3} $. 初始点$ x_{0} $随机产生, $ q, N, S $$ (-2, 2) $中随机产生, $ D $中的对角元素在$ (0, 2) $中随机产生. 停机条件为$ \left\|x_{n+1}-x_{n}\right\| \leq err $, 这里$ err $表示提前设定的误差界. 在此条件下, 将本文算法3.1与文献[7]中算法4、文献[8]中算法1以及[8]中算法2进行比较. 数值实验结果如图 3图 4以及表 2所示. 通过图 3图 4以及表 2可以发现: 本文算法3.1不仅迭代次数少, 而且迭代时间也更短.

图 3

图 3   例2 $ m=50 $, $ err=10^{-8} $时, 四种算法的对比


图 4

图 4   例2 $ m=60 $, $ err=10^{-8} $时, 四种算法的对比


表 2   例4.2 $err=10^{-8}$时, 四种算法的比较

$err=10^{-8}$$m=50$$m=60$$m=70$
IterCPU timeIterCPU timeIterCPU time
Alg 3.1410.3043420.3151420.9606
Alg 1 in [8]1360.94051450.9811190238.337
Alg 2 in [8]3292.57704903.79675274.3241
Alg 4 in [7]2373.20415339.08556513106.62

新窗口打开| 下载CSV


例4.3  设映射$ F:{{\Bbb R}} ^m\rightarrow {{\Bbb R}} ^m $满足$ F(x):=x+\cos(x) $, 易知$ F $是单调且Lipschitz连续的, 其中Lipschitz常数为2. 取可行集$ C={{\Bbb R}}_{+}^{m} $. $ U: {{\Bbb R}} ^m\rightarrow {{\Bbb R}} ^m $定义为$ Ux=-\frac{3x}{2} $. 由文献[12] 知, $ U $$ \alpha $ -半压缩映射$ (\alpha=\frac{1}{5}) $, 但$ U $不是拟非扩张映射. 取$ f(x)=0.5x $, $ m=10 $, $ \alpha_{0}=0.1 $, $ \beta_{0}=0.1 $, $ \lambda_{0}=0.5 $, $ \gamma=1 $, $ l=0.5 $, $ \mu=0.2 $, $ \alpha_{n}=\frac{1}{n+1}, \beta_{n}=\frac{n}{2n+1} $. 停机条件为$ \left\|x_{n}-x_{n-1}\right\| \leq 10^{-9} $. 在此条件下, 将本文算法3.1与文献[12] 中算法3.1和算法3.2进行比较. 测试结果如图 5图 6以及表 3所示. 通过图 5图 6以及表 3可以发现: 本文算法3.1更优.

图 5

图 5   例3 $ \alpha_{n}=\frac{1}{\sqrt{n+1}} $时, 三种算法的对比


图 6

图 6   例3 $ \alpha_{n}=\frac{1}{n+1} $时, 三种算法的对比


表 3   例4.3不同误差界下3种算法的比较

$err$Alg.3.1Alg.3.2 in [12]Alg.3.1 in [12]
IterCPU timeIterCPU timeIterGPU time
$10^{-10}$120.0144170.0239248680.2387
$10^{-12}$140.0154190.0243$\geq 10^{6}$1.7069
$10^{-14}$160.0165220.0297$\geq 10^{7}$15.944

新窗口打开| 下载CSV


例4.4  假设$ H=l^{2} $, 令$ C:=\{x=(x_{1}, x_{2}, \cdots , x_{i}, \cdots )\in H:\left|x_{i}\right|\leq\frac{1}{i}, i=1, 2, \cdots , n, \cdots \} $. 设映射$ F:C\rightarrow H $$ F(x):=(\left\|x\right\|+\frac{1}{\left\|x\right\|+s})x $[8], 其中$ s>0 $为常实数. 由文献[8]知, $ F $是一个伪单调且一致连续的映射, 但$ F $不是Lipschitz连续的. 令$ s=0.5 $, 可行集$ C=\{x\in {{\Bbb R}} ^m: \frac{-1}{i}\leq x_{i}\leq\frac{1}{i}, i=1, 2, \cdots , m\} $. 定义映射$ U: {{\Bbb R}} ^m\rightarrow {{\Bbb R}} ^m $$ Ux=\frac{x}{2} \sin x $. 由文献[12]知, $ U $$ \alpha $ -半压缩映射$ (\alpha=0) $.$ f(x)=0.5x $, $ m=30 $, $ \alpha_{n}=\frac{1}{n+1} $, $ \beta_{n}=0.5 $, $ \lambda_{0}=0.5 $, $ \gamma=0.5 $, $ l=\mu=0.5 $, 初始点$ x_{0}=[0, 1]^{m} $, 停机条件为$ \left\|x_{n}\right\| \leq err $, $ err $为设定的误差界. 在此条件下, 将算法3.1与文献[13]中算法3.1、文献[8]中算法1和文献[8]中算法2进行比较. 具体数值实验结果如图 7图 8表 4所示. 由图 7图 8表 4可知, 在不同的误差界下, 本文算法3.1的收敛速度明显优于文献[13]中算法3.1、文献[8]中算法1和文献[8]中算法2. 另一方面, 由于$ F $既不是单调的, 也不是Lipschitz连续的, 故文献[7]中算法4和文献[12]中算法3.1和算法3.2不适用于本例. 由此可见, 我们的算法适用性范围更广.

图 7

图 7   例4 $ m=20 $, $ err\leq 10^{-5} $时, 三种算法的对比


图 8

图 8   例4 $ m=20 $, $ err\leq 10^{-10} $时, 三种算法的对比


表 4   例4.4不同误差界下4中算法的比较

$10^{-5}$$10^{-10}$$10^{-15}$
IterCPU timeIterCPU timeIterGPU time
Alg 3.1280.0138660.01631040.0529
Alg 1 in [8]390.0238800.02741200.0635
Alg 2 in [8]450.02571260.03572070.0933
Alg 3.1 in [13]420.0142860.01751270.0548

新窗口打开| 下载CSV


注4.1  从数值实验的结果来看, 我们有如下结论:

(ⅰ) 由图 1图 2表 1知, 在例1给定的条件下, 算法3.1收敛到变分不等式问题的解集和半压缩算子不动点集合的一个公共元素, 且收敛速度与压缩映射$ f $的选取、$ \gamma $的选取以及$ m $的选取有关.

(ⅱ) 由图 3图 4知, 给定误差界和$ m $, 算法3.1比文献[7]中算法4、文献[8]中算法1和文献[8]中算法2运行的时间更短, 迭代次数更少.

(ⅲ) 由表 2可知, $ m $的选取对4种算法都有一定的影响, 但是算法3.1的稳定性更好.

(ⅳ) 由图 5图 6知, $ \alpha_{n} $的选取会影响例4.3所示3种算法的收敛速度. 又由表 3知, 在其它条件相同时, 算法3.1的迭代时间、迭代次数以及稳定性方面都要优于文献[12]中算法3.1.

(ⅴ) 由图 7图 8表 4知, 在误差界相同的情况下, 算法3.1比文献[13]中算法3.1、文献[8]中算法1和文献[8]中算法2迭代收敛速度更快.

(ⅵ) 在例4.4的情况下, 文献[7]中算法4和文献[12]中算法3.1和算法3.2不再适用. 由此可见, 算法3.1适用范围更广.

参考文献

Facchinei F, Pang J S. Finite-Dimensional Variational Inequalities and Complementarity Problems. New York: Springer, 2003

[本文引用: 2]

Kinderlehrer D, Stampacchia G. An Introduction to Variational Inequalities and Their Applications. New York: Academic Press, 1980

[本文引用: 1]

Goldstein A A .

Convex programming in Hilbert space

Bull Amer Math Soc, 1964, 70, 709- 710

DOI:10.1090/S0002-9904-1964-11178-2      [本文引用: 2]

Tseng P .

A modified forward-backward splitting method for maximal monotone mappings

SIAM J Control Optim, 2000, 38, 431- 446

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

贺月红, 龙宪军. 求解伪单调变分不等式问题的惯性收缩投影算法. 数学物理学报, 2021, 41A(6): 1897-1911

URL     [本文引用: 1]

He Y H, Long X J. A inertial contraction and projection algorithm for pseudomonotone variational inequality problems. 2021, 41A(6): 1897-1911

URL     [本文引用: 1]

万升联. 解变分不等式的一种二次投影算法. 数学物理学报, 2021, 41A(1): 237-244

URL    

Wan S L. A double projection algorithm for solving variational inequalities. 2021, 41A(1): 237-244

URL    

Fan J J , Qin X L .

Weak and strong convergence of inertial Tseng's extragradient algorithms for solving variational inequality problems

Optimization, 2021, 70, 1195- 1216

DOI:10.1080/02331934.2020.1789129      [本文引用: 6]

Thong D V , Voung P T .

Modified Tseng's extragradient methods for solving pseudo-monotone variational inequalities

Optimization, 2019, 68, 2207- 2226

DOI:10.1080/02331934.2019.1616191      [本文引用: 18]

Yang J , Liu H W .

Strong convergence result for solving monotone variational inequalities in Hilbert space

Numer Algor, 2019, 80, 741- 752

DOI:10.1007/s11075-018-0504-4     

Lei M , He Y R .

An extragradient method for solving variational inequalities without monotonocity

J Optim Theory Appl, 2021, 188, 432- 446

DOI:10.1007/s10957-020-01791-x      [本文引用: 1]

Thong D V , Hieu D V .

Mann-type algorithms for variational inequality problems and fixed point problems

Optimization, 2020, 69, 2305- 2326

DOI:10.1080/02331934.2019.1692207      [本文引用: 1]

Thong D V , Hieu D V .

Some extragradient-viscosity algorithms for solving variational inequality problems and fixed point problems

Numer Algor, 2019, 82, 761- 789

DOI:10.1007/s11075-018-0626-8      [本文引用: 16]

郭丹妮, 蔡钢. 关于变分不等式和不动点问题的新迭代算法[OL]. 数学学报(中文版), [2021-01-15]. http://kns.cnki.net/kcms/detail/11.2038.O1.20210114.1040.010.html

[本文引用: 8]

Guo D N, Cai G. A new iterative method for solving variational inequality and fixed point problems[OL]. Acta Mathematica Sinica(Chinese Series), [2021-01-15]. http://kns.cnki.net/kcms/detail/11.2038.O1.20210114.1040.010.html

[本文引用: 8]

Ceng L C , Shang M J .

Hybrid inertial subgradient extragradient methods for variational inequalities and fixed point problems involving asymptotically nonexpansive mappings

Optimization, 2021, 70, 715- 740

DOI:10.1080/02331934.2019.1647203      [本文引用: 1]

Karamardian S .

Complementarity problems over cones with monotone and pseudomonotone maps

J Optim Theory Appl, 1976, 18, 445- 454

DOI:10.1007/BF00932654      [本文引用: 1]

Chidume C E , Maruster S .

Iterative methods for the computation of fixed points of demicontractive mappings

J Comput Appl Math, 2010, 234, 861- 882

DOI:10.1016/j.cam.2010.01.050      [本文引用: 1]

Goebel K, Reich S. Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings. New York: Marcel Dekker, 1984

[本文引用: 1]

Denisov S V , Semenov V V , Chabak L M .

Convergence of the modified extragradient method for variational inequalities with non-Lipschitz operators

Cybern Syst Anal, 2015, 51, 757- 765

DOI:10.1007/s10559-015-9768-z      [本文引用: 1]

Maingé P E .

A hybrid extragradient-viscosity method for monotone operators and fixed point problems

SIAM J Control Optim, 2008, 47, 1499- 1515

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

Xu H K .

Iterative algorithms for nonlinear operators

J Lond Math Soc, 2002, 66, 240- 256

DOI:10.1112/S0024610702003332      [本文引用: 1]

Cottle R W , Yao J C .

Pseudo-monotone complementarity problems in Hilbert space

J Optim Theo Appl, 1992, 75, 281- 295

DOI:10.1007/BF00941468      [本文引用: 1]

/