## 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

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

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

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

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}$

$\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}$

$\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}$

$\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}$

$\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$单调这一假设比较强. 事实上, 许多函数不满足单调的假设. 因此, 如何在较弱的条件下证明算法的收敛性是本文讨论的重点.

## 2 相关定义与引理

$x_n\rightharpoonup x(n\to \infty ) $$\{x_n\} 弱收敛于 x , x_n\to x(n\to \infty )$$ \{x_n\}$强收敛于$x$. 对于任意的$x\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).$本文提出如下的算法:

由$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}$

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

$$$\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 .$$$

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

$\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}$

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

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

$\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) 式有 $$\langle w_{n}-p, d_{n}\rangle \geq \langle w_{n}-q_{n}, d_{n}\rangle = \theta_{n}\left\|d_{n}\right\|^2.$$ 由此可得 第二步 证明序列 \{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 使得 $$\frac{\alpha_{n}}{\beta_{n}}\left\|u_{n}-u_{n-1}\right\|\leq M_{1}, \;\forall\;n\geq 1.$$ (3.9)$$ (3.11)$式知

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

$(3.12)$式代入上式得

$$$\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}.$$$

$\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}$

$$$\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.$$$

$\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}$

$$$\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}.$$$

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

$\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) 式得 $$\left\|w_{n}-q_{n}\right\|\to 0.$$ 又由于 \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}$

\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}

\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}

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

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

## 4 数值实验

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

 $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})$ Iter Time Iter Time Iter Time NIPCM 6 0.0429 8 0.0535 7 0.0427 VPTA 33 0.0238 125 0.1098 78 0.0573 Y.L 340 0.0437 340 0.0319 340 0.0525 IPCM 533 0.0567 533 0.0612 533 0.0633

### 图 5

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

## 参考文献 原文顺序 文献年度倒序 文中引用次数倒序 被引期刊影响因子

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

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

He B .

A class of projection and contraction methods for monotone variational inequalities

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

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

Censor Y , Gibali A , Reich S .

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

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

Tseng P .

A modified forward-backward splitting method for maximal monotone mappings

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

Karamardian S .

Complementarity problems over cones with monotone and pseudo-monotone maps

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

Korpelevich G M .

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

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

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

Yang J , Liu H W .

Strong convergence result for solving monotone variational inequalities in Hilbert space

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

Gibali A , Thong D V , Tuan P A .

Two simple projection-type methods for solving variational inequalities

Anal Math Phys, 2019, 9, 2203- 2225

Maingé P E .

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

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

Xu H K .

Iterative algorithms for nonlinear operators

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

/

 〈 〉