数学物理学报, 2021, 41(6): 1897-1911 doi:

论文

求解伪单调变分不等式问题的惯性收缩投影算法

贺月红,, 龙宪军,

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

A Inertial Contraction and Projection Algorithm for Pseudomonotone Variational Inequality Problems

He Yuehong,, Long Xianjun,

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

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

收稿日期: 2021-03-1  

基金资助: 国家自然科学基金.  11471059
重庆市基础与前沿研究计划项目.  cstc2021jcyj-msxmX0721
重庆市教育委员会科学技术研究重点项目.  KJZDK201900801
重庆工商大学科研团队项目.  ZDPTTD201908

Received: 2021-03-1  

Fund supported: the NSFC.  11471059
the Basic and Advanced Research Project of Chongqing.  cstc2021jcyj-msxmX0721
the Education Committee Project Research Foundation of Chongqing.  KJZDK201900801
the Innovative Project of CTBU.  ZDPTTD201908

作者简介 About authors

贺月红,E-mail:heyuehong1111@163.com , E-mail:heyuehong1111@163.com

Abstract

In this paper, we introduce a new inertial contraction and projection algorithm for pseudomonotone variational inequality problems. We prove the strong convergence theorem without the knowledge of the Lipschitz constant of the mapping. Finally, we give some numerical experiments to show the efficiency of the algorithm.

Keywords: Variational inequality ; Inertial contraction and projection method ; Pseudomonotone ; Strong convergence

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

本文引用格式

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

He Yuehong, Long Xianjun. A Inertial Contraction and Projection Algorithm for Pseudomonotone Variational Inequality Problems. Acta Mathematica Scientia[J], 2021, 41(6): 1897-1911 doi:

1 引言

$ H $为实Hilbert空间, $ C\subset H $是非空闭凸子集, $ \langle \cdot , \cdot \rangle $$ \left\|\cdot \right\| $分别表示$ H $中的内积和范数. 设$ x\in H $, $ P_{C}(x) $表示向量$ x $$ C $上的投影. 设$ F:H\rightarrow H $是一个映射. 本文考虑如下变分不等式问题: 寻找点$ x^*\in C $, 使得

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

$ S $为问题$ (1.1) $的解集. 近年来, 变分不等式模型在经济金融、管理、博弈论及非线性规划等领域中有着广泛的应用, 许多学者对变分不等式的理论和算法进行了研究, 也推动着变分不等式的发展, 见文献[1-8]. Korpelevich[9]最早提出了求解变分不等式的外梯度算法:

$ \begin{eqnarray} y_{n} = P_{C}(x_{n}-\lambda F(x_{n})), \; x_{n+1} = P_{C}(x_{n}-\lambda F(y_{n})), \end{eqnarray} $

其中映射$ F $是单调的且Lipschitz连续的, $ L $为Lipschitz常数, $ \lambda\in(0, \frac{1}{L}) $. 然而该算法每次迭代需要计算两次到$ C $上的投影. 若集合$ C $结构不够简单,则在$ C $上的投影难以计算, 从而会影响算法的效率和适用性. 为了克服这一缺点, He[3]在1997年提出了收缩投影算法, 该算法每次迭代只需要计算一次到$ C $上的投影, 具体算法如下:

$ \begin{eqnarray} \left\{ \begin{array}{ll} \ y_{n} = P_{C}(x_{n}-\lambda F(x_{n})), \\ \ d({x_{n}, y_{n}}) = x_{n}-y_{n}-\lambda (F(x_{n})-F(y_{n})), \\ \ x_{n+1} = x_{n}-\gamma \beta_{n}d({x_{n}, y_{n}}), \forall n\geq 0, \end{array} \right. \end{eqnarray} $

其中映射$ F $是单调的且Lipschitz连续的, $ \lambda\in(0, \frac{1}{L}), \gamma \in (0, 2), \beta_{n}: = \frac{\langle x_{n}-y_{n}, d({x_{n}, y_{n}})\rangle }{\left\|d({x_{n}, y_{n}})\right\|^2} $. 后来, 惯性方法由于其良好的加速性质得到了学者们的广泛关注[10-11]. 据此, Dong等[10]提出了带惯性项的收缩投影算法, 同时在映射$ F $为单调且Lipschitz连续的条件下证明了该算法的弱收敛性定理. 进一步, Thong等[11]结合黏度方法得到了如下改进的惯性收缩投影算法:

$ \begin{eqnarray} \left\{ \begin{array}{ll} \ w_{n} = x_{n}+\alpha_{n}(x_{n}-x_{n-1}), \\ \ y_{n} = P_{C}(w_{n}-\lambda F(w_{n})), \\ \ d_n = w_{n}-y_{n}-\lambda (F(w_{n})-F(y_{n})), \\ \ x_{n+1} = \beta_nf(x_{n})+(1-\beta_n)(w_n-\theta_{n}d_n), \end{array} \right. \end{eqnarray} $

其中映射$ F $是单调的且Lipschitz连续的, $ \lambda \in(0, \frac{1}{L}), \theta_{n}: = (1-\lambda L)\frac{\left\|w_{n}-y_{n}\right\|^2}{\left\|d_n\right\|^2} $. Thong等证明了由算法$ (1.4) $产生的无穷序列强收敛到变分不等式问题的解.

对于算法(1.2)–(1.4), 其步长$ \lambda $都与Lipschitz常数$ L $有关, 而Lipschitz常数很难计算或估计. 因此, 为了避免估算Lipschitz常数, 学者们通常采用一类自适应方法得到步长. 2019年, Yang和Liu[12]提出了一种无需搜索得到步长的算法:

$ \begin{eqnarray} \left\{ \begin{array}{ll} \ y_n = P_{C}(x_{n}-\lambda_n F(x_{n})), \\ \ z_n = y_n-\lambda_n (F(x_n)-F(y_n)), \\ \ x_{n+1} = \alpha_nf(x_n)+(1-\alpha_n)z_n, \end{array} \right. \end{eqnarray} $

其中

$ \begin{eqnarray} \lambda_{n+1}: = \left \{ \begin{array}{ll} { } \min \left\{\frac{\mu \left\|x_{n}-y_{n}\right\|}{\left\|F(x_{n})-F(y_{n})\right\|}, \lambda_{n}\right\}, \, \, &\mbox{若}\, \, F(x_{n})-F(y_{n})\neq 0, \\ \lambda_{n} , \, \, &\mbox{其它, } \end{array} \right. \end{eqnarray} $

这里映射$ F $是单调的且Lipschitz连续的($ L $未知), $ \lambda_0 >0, \mu \in (0, 1). $

最近, Gibali等[13]给出了一种黏度投影算法, 在其算法中步长$ \tau_n $是最大的$ \tau \in \{\lambda, \lambda l, \lambda l^2, \cdots \} $满足$ \tau \left\|F(x_n)-F(y_n)\right\|\leq \mu \left\|x_n-y_n\right\|, $其算法为

$ \begin{eqnarray} \left\{ \begin{array}{ll} \ y_{n} = P_{C}(x_{n}-\tau_n F(x_{n})), \\ \ z_n = x_n-\gamma \eta_n d_n, \\ { } \ \eta_n = (1-\mu )\frac{\left\|x_n-y_n\right\|^2}{\left\|d_n\right\|^2}, \\ \ d_n = x_n-y_n-\tau_n(F(x_n)-F(y_n)), \\ \ x_{n+1} = \alpha_nf(x_n)+(1-\alpha_n)z_n, \end{array} \right. \end{eqnarray} $

Gibali等在映射$ F $是单调且Lipschitz连续的($ L $未知)条件下证明了算法的强收敛性. 然而映射$ F $单调这一假设比较强. 事实上, 许多函数不满足单调的假设. 因此, 如何在较弱的条件下证明算法的收敛性是本文讨论的重点.

本文受文献[11-13]的启发, 在映射是伪单调和Lipschitz连续($ L $未知)的假设下, 证明了由算法产生的无穷序列强收敛到变分不等式问题的解, 并用数值实验验证了算法的适用性. 本文所得结果改进和推广了文献[11-13]中相应结果.

2 相关定义与引理

$ x_n\rightharpoonup x(n\to \infty ) $$ \{x_n\} $弱收敛于$ x $, $ x_n\to x(n\to \infty ) $$ \{x_n\} $强收敛于$ x $. 对于任意的$ x\in H $, 有

对于任意的$ x, y\in H $, 有

定义2.1[8]  设$ F:H\to H $是映射, 如果对于任意的$ x, y \in H $, 有

则称$ F $是伪单调的.

定义2.2  设$ F:H\to H $是映射, 如果对于任意的$ x, y\in H, $

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

引理2.1[2]  设$ C\subset H $是非空闭凸子集. 对于任意的$ x\in H $, $ z\in C $, 有

引理2.2[2]  设$ C\subset H $是非空闭凸子集. 对于任意的$ x\in H $, 有

$ {\rm (i)} $$ \left \|P_C(x)-P_C(y)\right\|^2\leq \langle P_C(x)-P_C(y), x-y\rangle , \forall y\in H $;

$ {\rm (ii)} $$ \left \|P_C(x)-y\right\|^2\leq \left\|x-y\right\|^2-\left\|x-P_C(x)\right\|^2, \forall y\in C $.

引理2.3[14]  设$ \{a_{n_{j}}\} $是非负实序列$ \{a_{n}\} $的子列, 且子列满足对于任意的$ j\in {\Bbb N} $, 有$ a_{n_{j}} < a_{n_{j+1}} $成立, 则存在单调递增的整数子列$ \{m_{k}\} $满足: $ \lim\limits_{k \to \infty}m_{k} = \infty $; 而且当$ k\in {\Bbb N} $充分大时有: $ a_{m_{k}}\leq a_{m_{k+1}}, a_{k}\leq a_{m_{k+1}}. $事实上$ m_{k} $是集合$ \{1, 2, \cdots, k\} $中满足$ a_{n} < a_{n+1} $的最大的整数.

引理2.4[15]  设$ \{a_{n}\} $是非负实序列, 满足

其中$ \{\gamma_{n}\}\subset (0, 1) $$ \{b_{n}\} $$ {{\Bbb R}} $中的一个数列满足

$ {\rm (i)} $$ \sum\limits_{n = 0}^\infty \gamma_{n} = \infty $; $ {\rm (ii)} $$ {\limsup\limits_{n \to \infty}}b_{n}\leq 0 $, 则$ {\lim\limits_{n \to \infty}}a_{n} = 0. $

本文假设

$ (C_1) $$ S\neq \emptyset $;

$ (C_2) $映射$ F:H\to H $是伪单调且Lipschitz连续的, 但Lipschitz常数$ L $未知;

$ (C_3) $映射$ F:H\to H $满足: 若$ \{u_{n}\}\subset C $, $ u_{n}\rightharpoonup z(n\to \infty ) $, 则$ \left\|F(z)\right\|\leq {\liminf\limits_{n \to \infty}}\left\|F(u_{n})\right\| $;

$ (C_4) $序列$ \{\alpha_{n}\}, \{\beta_{n}\}\subset (0, 1) $满足

3 算法与收敛性证明

$ f:H\rightarrow {H} $是压缩映射, 压缩参数$ \rho \in(0, 1). $本文提出如下的算法:

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

步骤1  令$ w_{n} = u_{n}+\alpha_{n}(u_{n}-u_{n-1}) $, 计算

如果$ q_{n} = w_{n} $$ F(q_{n}) = 0, $则停止; $ q_{n} $是变分不等式问题(1.1) 的解. 否则, 转到步骤2.

步骤2  计算

其中

并计算

步骤3  计算

$ n: = n+1 $,转到步骤1.

引理3.1  假设条件$ (C_2) $成立, 则算法$ 3.1 $产生的步长$ \{\lambda _{n}\} $是一个非增序列, 且满足

  该引理的证明与文献[12]中引理$ 3.1 $的证明类似, 故不再赘述.

引理3.2  设$ \{d_{n}\} $是由算法$ 3.1 $产生的无穷序列, 则$ d_{n} = 0 $当且仅当$ w_{n} = q_{n}. $

类似可得

因此

$ d_{n} = 0 $当且仅当$ w_{n} = q_{n}. $

注3.1  由引理$ 3.2 $可知, 若$ d_{n} = 0 $, 则算法停止, 故$ q_{n} $是变分不等式问题$ (1.1) $的解.

引理3.3  假设条件$ (C_1) $$ (C_3) $成立, $ \{w_{n}\} $是由算法$ 3.1 $产生的无穷序列. 如果存在$ \{w_{n}\} $的子序列$ \{w_{n_{k}}\} $满足$ \{w_{n_{k}}\} $弱收敛于$ z\in H $$ {\lim\limits_{n \to \infty }\left\|w_{n_{k}}-q_{n_{k}}\right\|} = 0, $$ z\in S $.

  由$ q_{n_{k}} = P_{C}(w_{n_{k}}-\lambda_{n}F(w_{n_{k}})) $可得

上式等价于

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

因为$ \{w_{n}\} $的子序列$ \{w_{n_{k}}\} $弱收敛于$ z\in H $, 所以$ \{w_{n_{k}}\} $是有界的. 由$ F $的Lipschitz连续性可知$ \{F(w_{n_{k}})\} $也是有界的. 又因为$ \left \|w_{n_{k}}-q_{n_{k}}\right\|\to 0 $, 所以$ \{q_{n_{k}}\} $也是有界的. 在$ (3.1) $式中, 令$ k\to \infty $, 有

$ \begin{equation} {\liminf\limits_{k \to \infty}} \langle F(w_{n_{k}}), x-w_{n_{k}}\rangle \geq 0, \; \forall x\in C . \end{equation} $

注意到

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

由于$ \lim\limits_{k\to \infty}\left\|w_{n_{k}}-q_{n_{k}}\right\| = 0 $$ F $$ H $上是Lipschitz连续的, 故

结合$ (3.2) $$ (3.3) $式得

下证$ z\in S $. 选择非负递减序列$ \{\epsilon_{k}\}, $使得$ {\lim\limits_{k \to \infty}}\epsilon_{k} = 0. $对于每一个$ \epsilon_{k}, $$ N_{k} $为使得下式成立的最小正整数

$ \begin{equation} \langle F(q_{n_{j}}), x-q_{n_{j}}\rangle +\epsilon _{k}\geq 0, \; \forall j\geq N_{k}. \end{equation} $

由于$ \{\epsilon_{k}\} $是递减序列, 易知$ N_{k} $是递增序列. 则对于每一个$ k, $$ \{q_{N_{k}}\}\subset C $可知$ F(q_{N_{k}})\neq 0 $, 令$ v_{N_{k}} = \frac{F(q_{N_{k}})}{\left\|F(q_{N_{k}})\right\|^2} $. 易知$ \langle F(q_{N_{k}}), v_{N_{k}}\rangle = 1. $对于每一个$ k, $$ (3.4) $式知$ \langle F(q_{N_{K}}), x+\epsilon _{k}v_{N_{k}}-q_{N_{k}}\rangle \geq 0 $. 再由$ F $的伪单调性知

上式等价于

$ \begin{eqnarray} \langle F(x), x-q_{N_{k}}\rangle \geq \langle F(x)-F(x+\epsilon _{k}v_{N_{k}}), x+\epsilon _{k}v_{N_{k}}-q_{N_{k}}\rangle -\epsilon _{k}\langle F(x), v_{N_{k}}\rangle . \end{eqnarray} $

下证$ {\lim\limits_{k \to \infty}}\epsilon _{k}v_{N_{k}} = 0 $.$ w_{n_{k}}\rightharpoonup z $, $ k\to \infty $$ {\lim\limits_{k \to \infty }}\left\|w_{n_{k}}-q_{n_{k}}\right\| = 0 $$ q_{N_{k}}\rightharpoonup z $, $ k\to \infty. $又由$ \{q_{n}\}\subset C $$ z \in C $. 根据$ (C_3) $

又因为$ \{q_{N_{k}}\} \subset \{q_{n_{k}}\} $以及$ \epsilon _{k} \to \infty (k\to \infty ), $

所以$ {\lim\limits_{k \to \infty }}\epsilon _{k}v_{N_{k}} = 0. $又当$ k\to \infty $时, 由$ (3.5) $式知$ {\liminf\limits_{k \to \infty }}\langle F(x), x-q_{N_{k}}\rangle \geq 0. $对任意的$ x\in C $, 有

又由$ F $的伪单调性得

$ z\in S $.

定理3.1  假设条件$ (C_1) $$ (C_4) $成立, $ \{u_{n}\} $是由算法$ 3.1 $所产生的无穷序列, 则$ \{u_{n}\} $强收敛于某一个$ p\in S, $其中$ p = P_{S}\circ f(p). $

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

第一步  首先证明

$ \begin{equation} \left\|h_{n}-p\right\|^2\leq \left\|w_{n}-p\right\|^2-\frac{2-\gamma}{\gamma}\left\|w_{n}-h_{n}\right\|^2. \end{equation} $

事实上

$ \begin{eqnarray} \langle w_{n}-p, d_{n}\rangle & = &\langle w_{n}-q_{n}, d_{n}\rangle+\langle q_{n}-p, d_{n}\rangle\\ & = &\langle w_{n}-q_{n}, d_{n}\rangle+\langle q_{n}-p, w_{n}-q_{n}-\lambda_{n}(F(w_{n})-F(q_{n}))\rangle. \end{eqnarray} $

$ q_{n} = P_C(w_{n}-\lambda_nF(w_{n})) $$ \langle w_{n}-q_{n}-\lambda_{n}F(w_{n}), q_{n}-p\rangle\geq 0. $由于$ p\in S, $$ \langle F(p), q_{n}-p\rangle \geq0. $$ F $的伪单调性得$ \langle F(q_{n}), q_{n}-p\rangle\geq0. $因此, $ \langle q_{n}-p, w_{n}-q_{n}-\lambda_{n}(F(w_{n})-F(q_{n}))\rangle\geq0. $再根据$ \{\theta_{n}\} $的定义以及$ (3.7) $式有

$ \begin{equation} \langle w_{n}-p, d_{n}\rangle \geq \langle w_{n}-q_{n}, d_{n}\rangle = \theta_{n}\left\|d_{n}\right\|^2. \end{equation} $

由此可得

第二步  证明序列$ \{w_{n}\} $是有界的. 由$ (3.6) $式知

$ \begin{eqnarray} \left\|h_{n}-p\right\|\leq \left\|w_{n}-p\right\|. \end{eqnarray} $

注意到

$ \begin{eqnarray} \left\|w_{n}-p\right\| & = &\left\|w_{n}-u_{n}+u_{n}-p\right\|{}\\ &\leq& \left\|w_{n}-u_{n}\right\|+\left\|u_{n}-p\right\|{}\\ & = &\alpha_{n}\left\|u_{n}-u_{n-1}\right\|+\left\|u_{n}-p\right\|{}\\ & = &\beta_{n}\frac{\alpha_{n}}{\beta_{n}}\left\|u_{n}-u_{n-1}\right\|+\left\|u_{n}-p\right\|. \end{eqnarray} $

因为$ \frac{\alpha_{n}}{\beta_{n}}\left\|u_{n}-u_{n-1}\right\|\to 0 $, 所以存在$ M_{1}>0 $使得

$ \begin{equation} \frac{\alpha_{n}}{\beta_{n}}\left\|u_{n}-u_{n-1}\right\|\leq M_{1}, \;\forall\;n\geq 1. \end{equation} $

$ (3.9) $$ (3.11) $式知

$ \begin{equation} \left\|h_{n}-p\right\|\leq \left\|w_{n}-p\right\|\leq \left\|u_{n}-p\right\|+\beta_{n}M_{1}. \end{equation} $

另一方面

$ (3.12) $式代入上式得

因此, $ \{u_{n}\} $是有界的. 故$ \{h_{n}\} $, $ \{w_{n}\} $$ \{f(u_{n})\} $也是有界的.

第三步  证明

$ \begin{equation} \frac{2-\gamma}{\gamma}(1-\beta_{n})\left\|h_{n}-w_{n}\right\|^2\leq \left\|u_{n}-p\right\|^2-\left\|u_{n+1}-p\right\|^2+\beta_{n}M_{4}, \end{equation} $

其中$ M_{4}>0 $. 事实上

$ \begin{eqnarray} \left\|u_{n+1}-p\right\|^2 & = &\left\|\beta_{n}f(u_{n})+(1-\beta_{n})h_{n}-p\right\|^2\\ & = &\left\|\beta_{n}(f(u_{n})-p)+(1-\beta_{n})(h_{n}-p)\right\|^2\\ & = &\beta_{n}^2\left\|f(u_{n})-p\right\|^2+(1-\beta_{n})^2\left \|h_{n}-p\right\|^2+2\beta_{n}(1-\beta_{n})\langle f(u_{n})-p, h_{n}-p\rangle\\ &\leq& \beta_{n}^2(\left\|f(u_{n})-f(p)\right\|+\left\|f(p)-p\right\|)^2+(1-\beta_{n})^2\left \|h_{n}-p\right\|^2\\ &&+2\beta_{n}(1-\beta_{n})\left\|f(u_{n})-p\right\|\cdot \left\|h_{n}-p\right\|\\ &\leq& \beta_{n}^2(\rho\left\|u_{n}-p\right\|+\left\|f(p)-p\right\|)^2+(1-\beta_{n})^2\left \|h_{n}-p\right\|^2\\ &&+2\beta_{n}(1-\beta_{n})\left\|f(u_{n})-p\right\|\cdot \left\|h_{n}-p\right\|\\ &\leq& \beta_{n}\left\|u_{n}-p\right\|^2+(1-\beta_{n})\left \|h_{n}-p\right\|^2+\beta_{n}(\left\|f(p)-p\right\|^2\\ &&+2\left\|f(p)-p\right\|\cdot\left\|u_{n}-p\right\|+2\left\|f(u_{n})-p\right\|\cdot\left\|h_{n}-p\right\|). \end{eqnarray} $

$ M_{2}>0. $

$ (3.6) $$ (3.14) $式得

$ \begin{equation} \left\|u_{n+1}-p\right\|^2\leq \beta_{n}\left\|u_{n}-p\right\|^2+(1-\beta_{n})\left\|w_{n}-p\right\|^2-\frac{2-\gamma}{\gamma}(1-\beta_{n})\left\|w_{n}-h_{n}\right\|^2+\beta_{n}M_{2}. \end{equation} $

又由$ (3.12) $式得

$ \begin{eqnarray} \left\|w_{n}-p\right\|^2 &\leq &(\left\|u_{n}-p\right\|+\beta_{n}M_{1})^2{}\\ & = &\left\|u_{n}-p\right\|^2+\beta_{n}(2M_{1}\left\|u_{n}-p\right\|+\beta_{n}M_{1}^2){}\\ &\leq &\left\|u_{n}-p\right\|^2+\beta_{n}M_{3}, \end{eqnarray} $

其中$ M_{3} = 2M_{1}\left\|u_{n}-p\right\|+\beta_{n}M_{1}^2 > 0 $.$ (3.16) $式代入$ (3.15) $式得

上式等价于

其中$ M_{4}: = M_{2}+M_{3}. $

第四步  证明

$ \begin{equation} \left\|w_{n}-q_{n}\right\|^2\leq \frac{(1+\mu \frac{\lambda_{n}}{\lambda_{n+1}})^2}{\gamma^2(1-\mu \frac{\lambda_{n}}{\lambda_{n+1}})^2}\left\|h_{n}-w_{n}\right\|^2. \end{equation} $

事实上

$ \begin{eqnarray} \langle w_{n}-q_{n}, d_{n}\rangle & = &\langle w_{n}-q_{n}, w_{n}-q_{n}-\lambda_{n}(F(w_{n})-F(q_{n}))\rangle{}\\ & = &\left\|w_{n}-q_{n}\right\|^2- \lambda_{n}\langle w_{n}-q_{n}, F(w_{n})-F(q_{n})\rangle{}\\ &\geq&\left\|w_{n}-q_{n}\right\|^2-\lambda_{n}\left\|w_{n}-q_{n}\right\|\cdot \left\|F(w_{n})-F(q_{n})\right\|{}\\ & = &\left\|w_{n}-q_{n}\right\|^2-\mu \frac{\lambda_{n}}{\lambda_{n+1}}\left\|w_{n}-q_{n}\right\|^2{}\\ & = &(1-\mu \frac{\lambda_{n}}{\lambda_{n+1}})\left\|w_{n}-q_{n}\right\|^2. \end{eqnarray} $

结合$ (3.8) $$ (3.18) $式得

上式等价于

$ \begin{equation} \left\|w_{n}-q_{n}\right\|^2\leq\frac{\theta_{n}\left\|d_{n}\right\|^2}{1-\mu \frac{\lambda_{n}}{\lambda_{n+1}}} = \frac{\left\|\theta_{n}d_{n}\right\|^2}{1-\mu \frac{\lambda_{n}}{\lambda_{n+1}}}\cdot \frac{1}{\theta_{n}} = \frac{\left\|w_{n}-h_{n}\right\|^2}{\gamma^2(1-\mu \frac{\lambda_{n}}{\lambda_{n+1}})}\cdot \frac{1}{\theta_{n}}. \end{equation} $

又由引理$ 3.2 $

$ \begin{equation} \left\|d_{n}\right\|^2\leq (1+\mu \frac{\lambda_{n}}{\lambda_{n+1}})^2\left\|w_{n}-q_{n}\right\|^2. \end{equation} $

$ (3.18) $$ (3.20) $式知

$ \begin{equation} \theta_{n} = \frac{\langle w_{n}-q_{n}, d_{n}\rangle}{\left\|d_{n}\right\|^2}\geq \frac{(1-\mu \frac{\lambda_{n}}{\lambda_{n+1}})\left\|w_{n}-q_{n}\right\|^2} {(1+\mu \frac{\lambda_{n}}{\lambda_{n+1}})^2\left\|w_{n}-q_{n}\right\|^2} = \frac{1-\mu \frac{\lambda_{n}}{\lambda_{n+1}}}{(1+\mu \frac{\lambda_{n}}{\lambda_{n+1}})^2}. \end{equation} $

再由$ (3.19) $$ (3.21) $式得

第五步  证明

$ \begin{eqnarray} \left\|u_{n+1}-p\right\|^2 &\leq& (1-(1-\rho )\beta_{n})\left\|u_{n}-p\right\|^2{}\\ &&+(1-\rho )\beta_{n}\left[\frac{M}{1-\rho}\cdot \frac{\alpha_{n}} {\beta_{n}}\left\|u_{n}-u_{n-1}\right\|+\frac{2}{1-\rho}\langle f(p)-p, u_{n+1}-p\rangle \right], {\qquad} \end{eqnarray} $

其中$ M = 2\left\|u_{n}-p\right\|+\alpha_{n}\left\|u_{n}-u_{n-1}\right\|>0 $. 注意到

$ \begin{eqnarray} \left\|w_{n}-p\right\|^2 & = &\left\|u_{n}+\alpha_{n}(u_{n}-u_{n-1})-p)\right\|^2{}\\ & = &\left\|u_{n}-p\right\|^2+2\alpha_{n}\langle u_{n}-p, u_{n}-u_{n-1}\rangle+\alpha_{n} ^2\left\| u_{n}-u_{n-1}\right\|^2{}\\ &\leq& \left\|u_{n}-p\right\|^2+2\alpha_{n}\left\|u_{n}-p\right\|\cdot \left\|u_{n}-u_{n-1}\right\|+\alpha_{n} ^2\left\| u_{n}-u_{n-1}\right\|^2{}\\ & = &\left\|u_{n}-p\right\|^2+\alpha_{n}\left\|u_{n}-u_{n-1}\right\|(2\left\|u_{n}-p\right\|+\alpha_{n}\left\|u_{n}-u_{n-1}\right\|){}\\ & = &\left\|u_{n}-p\right\|^2+M\alpha_{n}\left\|u_{n}-u_{n-1}\right\|. \end{eqnarray} $

另一方面

$ \begin{eqnarray} \left\|u_{n+1}-p\right\|^2 & = &\left\|\beta_{n}f(u_{n})+(1-\beta_{n})h_{n}-p\right\|^2{}\\ & = &\left\|\beta_{n}(f(u_{n})-f(p))+(1-\beta_{n})(h_{n}-p)+\beta_{n}(f(p)-p)\right\|^2{}\\ &\leq& \left\|\beta_{n}(f(u_{n})-f(p))+(1-\beta_{n})(h_{n}-p)\right\|^2+2\beta_{n}\langle f(p)-p, u_{n+1}-p\rangle{}\\ & = & \beta_{n}\left\|f(u_{n})-f(p)\right\|^2+(1-\beta_{n})\left\|h_{n}-p\right\|^2{}\\ &&-\beta_{n}(1-\beta_{n})\left\|f(u_{n})-f(p)-h_{n}+p\right\|^2+2\beta_{n}\langle f(p)-p, u_{n+1}-p\rangle{}\\ &\leq& \beta_{n}\left\|f(u_{n})-f(p)\right\|^2+(1-\beta_{n})\left\|h_{n}-p\right\|^2+2\beta_{n} \langle f(p)-p, u_{n+1}-p\rangle{}\\ &\leq& \beta_{n}\rho^2\left\|u_{n}-p\right\|^2+(1-\beta_{n})\left\|h_{n}-p\right\|^2+2\beta_{n} \langle f(p)-p, u_{n+1}-p\rangle{}\\ &\leq& \beta_{n}\rho\left\|u_{n}-p\right\|^2+(1-\beta_{n})\left\|w_{n}-p\right\|^2+2\beta_{n} \langle f(p)-p, u_{n+1}-p\rangle . \end{eqnarray} $

$ (3.23) $$ (3.24) $式得

第六步  证明序列$ \left\{\left\|u_{n}-p\right\|^2\right\} $收敛到零, 考虑两种情形.

情形1  若存在$ N\in {\Bbb N} $使得

这就意味着$ {\lim\limits_{n \to \infty}}\left\|u_{n}-p\right\| $存在. 由$ (3.13) $式和$ \lim\limits_{n \to \infty}\beta_{n} = 0 $

$ \begin{equation} {\lim\limits_{n \to \infty}}\left\|h_{n}-w_{n}\right\| = 0. \end{equation} $

又因为

$ \begin{eqnarray} \left\|u_{n+1}-u_{n}\right\| & = &\left\|\beta_{n}f(u_{n})+(1-\beta_{n} )h_{n}-u_{n}\right\|{}\\ & = &\left\|\beta_{n}f(u_{n})-\beta_{n}u_{n}+\beta_{n}u_{n}+(1-\beta_{n} )h_{n}-u_{n}\right\|{}\\ &\leq& \beta_{n}\left\|f(u_{n})-u_{n}\right\|+(1-\beta_{n} )\left\|h_{n}-u_{n}\right\|. \end{eqnarray} $

另一方面,

$ (3.25) $式得$ \left\|h_{n}-u_{n}\right\|\to 0. $再由$ (3.26) $式知$ \left\|u_{n+1}-u_{n}\right\|\to 0 $. 联合$ (3.17) $$ (3.25) $式得

$ \begin{equation} \left\|w_{n}-q_{n}\right\|\to 0. \end{equation} $

又由于$ \left\{{u_{n}} \right\} $是有界的, 也即存在$ \left\{{u_{n}} \right\} $的子序列$ \left\{{u_{n_{k}}} \right\} $弱收敛于某一点$ z\in H $满足

同理, 因为$ \left\{{w_{n}} \right\} $也是有界的, 所以存在$ \left\{{w_{n}}\right\} $的子序列$ \left\{{w_{n_{k}}}\right\} $弱收敛于某一点$ z\in H $且根据$ (3.27) $式有

故由引理$ 3.3 $$ z\in S $. 再根据$ p $的定义和引理$ 2.1 $

因此

$ \begin{eqnarray} {\limsup\limits_{n \to \infty}}\langle f(p)-p, u_{n+1}-p\rangle &\leq& {\limsup\limits_{n \to \infty}}\langle f(p)-p, u_{n+1}-u_{n}\rangle +{\limsup\limits_{n \to \infty}}\langle f(p)-p, u_{n}-p\rangle{}\\ & = &\langle f(p)-p, z-p\rangle \leq0. \end{eqnarray} $

最后由引理$ 2.4 $$ (3.22) $$ (3.28) $式得$ {\lim\limits_{n \to \infty}\left\|u_{n}-p\right\|} = 0 $, 即$ u_{n}\to p, n\to \infty $.

情形2  若存在序列$ \left\{\left\|u_{n}-p\right\|^2\right\} $的子序列$ \left\{\left\|u_{n_{j}}-p\right\|^2\right\} $满足

在这种情况下, 由引理$ 2.3 $可知存在一个非减序列$ \left\{m_{k}\right\} $使得$ {\lim\limits_{k \to \infty}m_{k}} = \infty $且有如下不等式成立:

$ \begin{align} \left\|u_{m_{k}}-p\right\|^2\leq \left\|u_{m_{k}+1}-p\right\|^2, \; \forall k\in {\Bbb N}, \end{align} $

$ \begin{align} \left\|u_{k}-p\right\|^2\leq \left\|u_{m_{k}}-p\right\|^2. \end{align} $

则由$ (3.13) $$ (3.29) $式得

因此

类似于情形$ 1 $证明可得

$ \begin{align} \left\|u_{m_{k}+1}-u_{m_{k}}\right\|\to 0 \end{align} $

以及

$ \begin{align} {\limsup\limits_{n \to \infty}}\langle f(p)-p, u_{m_{k}+1}-p\rangle\leq0. \end{align} $

联立$ (3.22) $$ (3.29) $式有

由此可得

$ \begin{align} \left\|u_{m_{k}+1}-p\right\|^2\leq \frac{2}{1-\rho} \langle f(p)-p, u_{m_{k}+1}-p\rangle +\frac{M}{1-\rho }\cdot\frac{\alpha_{m_{k}}}{\beta_{m_{k}}}\left\|u_{m_{k}}-u_{m_{k}-1}\right\|. \end{align} $

故由$ (3.31) $$ (3.32) $$ (3.33) $式知

再由$ (3.29) $$ (3.30) $式得$ {\limsup\limits_{k \to \infty}}\left\|u_{k}-p\right\|\leq0 $, 即$ u_{k}\to p, k\to \infty $.

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

$ (1) $$ F $的单调性推广为伪单调性.

$ (2) $定理$ 3.1 $的证明不要求Lipschitz常数$ L $的任何信息, 而文献[11]中定理$ 1 $要求步长$ \lambda \in (0, \frac{1}{L}) $.

$ (3) $定理$ 3.1 $$ r\in (0, 2) $, 而文献[11]中定理$ 1 $$ r = 1 $.

注3.3  定理$ 3.1 $推广了文献[12]中定理$ 3.1 $到伪单调性情形, 同时增加了惯性项使算法的收敛速度更快.

注3.4  定理$ 3.1 $推广了文献[13]中定理$ 3.2 $到伪单调性情形, 同时$ \theta_{n} $的定义比文献[13]中的更加简洁并且增加了惯性项, 使收敛速度更快.

4 数值实验

本节给出数值实验, 所有代码均在MATLAB R2019a和Windows10系统下运行. 计算机基本参数为AMD Ryzen 5 3550H with Radeon Vega Mobile Gfx 2.10 GHz和16GB内存. 为了体现本文算法的数值效果, 将算法3.1 (记为NIPCM算法)与文献[11]的IPCM算法、文献[12]的Y.L算法和文献[13]的VPTA算法进行比较, 其中"Iter"代表程序循环次数, "Time" 代表程序的CPU运行时间, 单位为秒.

例1  设$ H = L^2([0, 1]) $, 内积

范数

$ C: = \{x\in H: \left\| x\right\|\leq 1\} $为单位球. 设$ F:C\rightarrow H $满足$ (Fx)(t) = \max \{0, x(t)\}, $$ F $$ C $上为单调Lipschitz连续的. 进一步, 由变分不等式的解集$ S = \{0\} $可得

选取$ \mu = 0.85 $, $ \gamma = 1.99 $, $ u_1(t) = f(t) = 0.9t $和不同的初始点$ u_{0}(t) $, 其中$ t\in [0, 1] $为等差分布的数列, 取终止条件为$ \left\|u_{n+1}-u_{n}\right\|\leq 10^{-30} $对算法进行测试, 结果见表 1图 15 (取$ u_0(t) = \frac{1}{600}(t^2-e^{-t}) $).

表 1   改变初始值取值

$u_0 = {(t^3+1)e^{-t}}$$u_0 = \frac{1}{500}[{\rm cost}+\sin(-5t)]$$u_0 = \frac{1}{600}(t^2-e^{-t})$
IterTimeIterTimeIterTime
NIPCM60.042980.053570.0427
VPTA330.02381250.1098780.0573
Y.L3400.04373400.03193400.0525
IPCM5330.05675330.06125330.0633

新窗口打开| 下载CSV


图 1

图 1   NIPCM算法


图 2

图 2   IPCM算法


图 3

图 3   VPTA算法


图 4

图 4   Y.L算法


图 5

图 5   算法对比图


例2  设算子$ F:{{\Bbb R}} ^m\to {{\Bbb R}} ^m $满足

其中$ q\in {{\Bbb R}} ^{m} $, 同时

其中$ B\in {{\Bbb R}} ^{m\times m}, H\in {{\Bbb R}} ^{m\times m} $是斜对称矩阵, $ D\in {{\Bbb R}} ^{m\times m} $为对角元素非负的对角矩, 可行集为$ C = \{x\in {{\Bbb R}} ^m|Qx\leq b\}, $$ Q\in {{\Bbb R}} ^{m\times m}, $$ b\in {{\Bbb R}} ^m, $$ q $, $ b $, $ Q $, $ B $, $ H $$ (2, -2) $中随机产生, $ D $中的对角元素在$ (0, 2) $中产生. 我们选取$ \gamma = 1 $, $ \mu = 0.05, $$ \alpha_{n} = \frac{2-\gamma}{1.01\gamma } $和初始点$ u_0 = (1, 1, \cdots , 1)^T\in {{\Bbb R}} ^m $, 终止条件为$ \left\|u_n\right\|<\epsilon $, 测试结果见表 2图 6.

表 2   改变终止条件精度

$\epsilon = 10^{-4}$$\epsilon = 10^{-10}$$\epsilon = 10^{-20}$$\epsilon = 10^{-30}$
IterTimeIterTimeIterTimeIterTime
NIPCM320.7108611.1787791.4880882.1495
VTPA409.03754010.31254010.8281409.8906
Y.L643.2096662.4719693.3800682.9023
IPCM-$>50$-$>50$-$>50$-$>50$

新窗口打开| 下载CSV


图 6

图 6   NIPCM算法取不同的$ f(x) $


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

$ {\rm (i)} $ NIPCM算法、VPTA算法、Y.L算法和IPCM算法均收敛于变分不等式问题的解, 但NIPCM算法受初始点取值的影响最小, 见表 1.

$ {\rm (ii)} $从迭代次数、程序CPU运行时间和算法精度来看, NIPCM算法、Y.L算法和VPTA算法均优于IPCM算法, 尤其是NIPCM算法充分体现了迭代步数较少的优势, 而VPTA算法和Y.L算法稳定性较弱, 这可能会对该算法的收敛性造成影响, 见图 15表 1.

$ {\rm (iii)} $在适当参数的选取下, 初始值$ u_{0}(t) $$ f(x) $的取值对NIPCM算法的影响较小(见表 1图 6), 但终止条件精度的选取对NIPCM算法的影响较大(见表 2).

$ {\rm (iv)} $ NIPCM算法优于VPTA算法、Y.L算法和IPCM算法.

参考文献

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

[本文引用: 1]

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

[本文引用: 2]

He B .

A class of projection and contraction methods for monotone variational inequalities

Appl Math Optim, 1997, 35 (1): 69- 76

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

Cai X , Gu G , He B .

On the O(1/t) convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators

Comput Optim Appl, 2014, 57 (2): 339- 363

DOI:10.1007/s10589-013-9599-7     

Censor Y , Gibali A , Reich S .

The subgradient extragradient method for solving variational inequalities in Hilbert space

J Optim Theory Appl, 2011, 148 (2): 318- 335

DOI:10.1007/s10957-010-9757-3     

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

URL    

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

URL    

Tseng P .

A modified forward-backward splitting method for maximal monotone mappings

SIAM J Control Optim, 2000, 38 (2): 431- 446

DOI:10.1137/S0363012998338806     

Karamardian S .

Complementarity problems over cones with monotone and pseudo-monotone maps

J Optim Theory Appl, 1976, 18 (4): 445- 454

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

Korpelevich G M .

The extragradient method for finding saddle points and other problems

Ekonomika i Mat Metody, 1976, 12, 747- 756

URL     [本文引用: 1]

Dong L Q , Cho Y J , Zhong L L , Rassias M T .

Inertial projection and contraction algorithms for variational inequalities

J Glob Optim, 2018, 70 (3): 687- 704

DOI:10.1007/s10898-017-0506-0      [本文引用: 2]

Thong D V , Vinh N T , Cho Y J .

New strong convergence theorem of the inertial projection and contraction method for variational inequality problems

Numer Algor, 2020, 84 (1): 285- 305

DOI:10.1007/s11075-019-00755-1      [本文引用: 8]

Yang J , Liu H W .

Strong convergence result for solving monotone variational inequalities in Hilbert space

Numer Algor, 2019, 80 (3): 741- 752

DOI:10.1007/s11075-018-0504-4      [本文引用: 4]

Gibali A , Thong D V , Tuan P A .

Two simple projection-type methods for solving variational inequalities

Anal Math Phys, 2019, 9, 2203- 2225

DOI:10.1007/s13324-019-00330-w      [本文引用: 6]

Maingé P E .

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

SIAM J Control Optim, 2008, 47 (3): 1499- 1515

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

Xu H K .

Iterative algorithms for nonlinear operators

J Lond Math Soc, 2002, 66 (1): 240- 256

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

/