## A New Tseng-like Extragradient Algorithm for Common Solutions of Variational Inequalities and Fixed Point Problems

Duan Jie,, Xia Fuquan,*

School of Mathematical Science, Sichuan Normal University, Chengdu 610066

Received: 2022-05-23   Revised: 2022-09-22

Abstract

In this paper, we introduce a new inertial Tseng-like extragradient algorithm for finding a common element of the set of solutions of a variational inequalitiy problem with a pseudomonotone and non-Lipschitz continuous mapping and the set of a fixed point problem with a quasi-nonexpansive mapping in Hilbert spaces. The strong convergence of the sequences generated by the algorithm is proved under some suitable assumptions imposed on the parameters. Finally, numercial experiments are carried out on the algorithm to verify the effectiveness of the algorithm.

Keywords： Variational inequalitiy ; Fixed point problem ; Pseudomonotone mapping ; Quasi-nonexpansive mapping ; Strong convergence

Duan Jie, Xia Fuquan. A New Tseng-like Extragradient Algorithm for Common Solutions of Variational Inequalities and Fixed Point Problems. Acta Mathematica Scientia[J], 2023, 43(1): 274-290 doi:

## 1 引言

$$$\label{eq1} \langle{Ax^\ast}{x-x^\ast}\rangle \ge0,\ \ \forall x\in C,$$$

$$$\label{sf2} \left\{ \begin{array}{lr} y_n=P_C(x_n-\lambda Ax_n),& \\ x_{n+1}=P_C(x_n-\lambda Ay_n), \end{array} \right.$$$

$\begin{matrix}\label{sf3} \left\{ \begin{array}{lr} y_n=P_C(x_n-\lambda Ax_n),& \\ x_{n+1}=y_n-\lambda (Ax_n -Ay_n), \end{array} \right. \end{matrix}$

$$$\label{sf4} \left\{ \begin{array}{lr} w_n=x_n+\alpha_n(x_n-x_{n-1}),& \\ y_n=P_C(w_n-\lambda_n Aw_n),& \\ z_n=y_n-\lambda_n(Ay_n-Aw_n), & \\ x_{n+1}=\beta_nf(x_n)+ (1-\beta_n)z_n, \end{array} \right.$$$

$r{l}^m\| Ay_n-Aw_n\|\le\mu\|y_n-w_n\|,$

$$$\label{sf5} \left\{ \begin{array}{lr} x_0\in C,& \\ y_n=P_C(x_n-\lambda Ax_n),& \\ x_{n+1}=(1-\beta_n)x_n+\beta_nTP_C(x_n-\lambda Ay_n), \end{array} \right.$$$

$$$\label{sf6} \left\{ \begin{array}{lr} x_0\in H,& \\ w_n=x_n+\alpha_n(x_n-x_{n-1}),& \\ y_n=P_C(w_n-\lambda_n Aw_n),& \\ z_n=P_{C_n}(w_n-\lambda_n Ay_n), & \\ x_{n+1}=(1-\beta_n)x_n+\beta_nTz_n, \end{array} \right.$$$

$r{l}^m\| Ay_n-Aw_n\|\le\mu\|y_n-w_n\|.$

2021年, Ceng等[14]为计算空间$H$ 中变分不等式问题(1.1)和不动点问题(1.2)公共解, 提出算法(1.9), 具体形式如下

$$$\label{sf7} \left\{ \begin{array}{lr} x_0\in H,& \\ w_n=Tx_n+\alpha_n(Tx_n-Tx_{n-1}),& \\ y_n=P_C(w_n-\lambda_n Aw_n),& \\ z_n=P_{C_n}(w_n-\lambda_n Ay_n), & \\ x_{n+1}=\beta_nf(x_n)+\gamma_nx_n+((1-\gamma_n)I-\beta_n\rho F)Tz_n, \end{array} \right.$$$

(i) $\lim\limits_{n\to \infty}\beta_n=0, \sum\limits^{\infty}_{n=1}\beta_n=\infty$;

(ii) $\sup\limits_{n\ge1}(\alpha_n/\beta_n)<\infty;$

(iii) $0<\liminf\limits_{n\to\infty}\gamma_n\le\limsup\limits_{n\to\infty}\gamma_n<1;$

## 2 预备知识

$\|P_C(x)-x\|=\min\{\|x-y\|:y\in H\}.$

$T^\lambda x:=Tx-\lambda\mu F(Tx),\ \ \forall x\in C,$

$T^\lambda$是压缩映射, 即对任意$x,y\in C$, 有$\|T^\lambda x-T^\lambda y\| \le (1-\lambda\tau)\|x-y\|,$ 其中 $\tau=1-\sqrt{1-\mu(2\eta-\mu\kappa^2)}\in (0,1].$

(i) $\|x_{m_k}-p\|^2\le\|x_{m_k+1}-p\|^2$;

(ii) $\|x_{k}-p\|^2\le\|x_{m_k+1}-p\|^2.$

(i) $\frac{\|x-P_C(x-\alpha Ax)\|}{\alpha}\le\frac{\|x-P_C(x-\beta Ax)\|}{\beta};$

(ii) $\|x-P_C(x-\beta Ax)\|\le\|x-P_C(x-\alpha Ax)\|.$

## 3 算法及收敛性分析

$\begin{eqnarray*} \lim\limits_{m\to\infty}\|w_n-P_C(w_n-r{l}^mAw_n)\|=0. \end{eqnarray*}$

$x_{n+1}-z_n=\beta_nf(x_n)+\gamma_n(x_n-z_n)+(1-\gamma_n)(Tz_n-z_n) -\beta_n\rho FTz_n,$

$\begin{eqnarray*} (1-\gamma_n)\|Tz_n-z_n\| &=&\|x_{n+1}-z_n-\beta_nf(x_n)-\gamma_n(x_n-z_n) +\beta_n\rho FTz_n\|\\ &\le&\|x_{n+1}-z_n\|+\beta_n(\|f(x_n)\|+\|\rho FTz_n\|)+\gamma_n\|x_n-z_n\|\\ &\le&\|x_{n+1}-x_n\|+\|x_n-z_n\|+\beta_n(\|f(x_n)\|+\|\rho FTz_n\|)+\|x_n-z_n\|\\ &=&\|x_{n+1}-x_n\|+2\|x_n-z_n\|+\beta_n(\|f(x_n)\|+\|\rho FTz_n\|). \end{eqnarray*}$

$$$\label{szb1} \liminf\limits_{n\to\infty}\|Tz_n-z_n\|=0.$$$

$\begin{eqnarray*} \langle{w_{n_k}-\lambda_{n_k}Aw_{n_k}-y_{n_k}}{x-y_{n_k}}\rangle\le 0,\ \ \forall x\in C, \end{eqnarray*}$

$$$\label{szb3} \frac{1}{\lambda_{n_k}}\langle{w_{n_k}-y_{n_k}}{x-y_{n_k}}\rangle +\langle{Aw_{n_k}}{y_{n_k}-w_{n_k}}\rangle \le\langle{Aw_{n_k}}{x-w_{n_k}}\rangle,\ \ \forall x\in C.$$$

$$$\|w_{n_k}-t_{n_k}\| \le\frac{1}{{l}}\|w_{n_k}-y_{n_k}\|\to0,\ \ k\to\infty.$$$

$$$\label{szb8} \liminf\limits_{k\to\infty}\langle{Aw_{n_k}}{x-w_{n_k}}\rangle\ge0.$$$

$A$$H的有界子集上是一致连续的, 并且\lim\limits_{k\to\infty}\|w_{n_k}-y_{n_k}\|=0, 可得 $$\label{szb9} \lim\limits_{k\to\infty}\|Aw_{n_k}-Ay_{n_k}\|=0.$$ 因为 \langle{Ay_{n_k}}{x-y_{n_k}}\rangle=\langle{Ay_{n_k}-Aw_{n_k}}{x-w_{n_k}}\rangle +\langle{Aw_{n_k}}{x-w_{n_k}}\rangle+\langle{Ay_{n_k}}{w_{n_k}-y_{n_k}}\rangle. 结合(3.15)和(3.16)式, 有 \begin{eqnarray*} \liminf\limits_{k\to\infty}\langle{Ay_{n_k}}{x-y_{n_k}}\rangle\ge0. \end{eqnarray*} 任取单调递减正实数列\{\xi_k\}\subset (0,1).$$k\to\infty$ 时, 有 $\xi_k\to0.$ 对任意的$k\ge1$, 设$l_k$是最小正整数, 使得

$$$\label{szb10} \langle{Ay_{n_j}}{x-y_{n_j}}\rangle+\xi_k\ge0,\ \ \forall j\ge l_k.$$$

$\{y_{l_k}\}$的定义知$\{y_{l_k}\}\subset C$, 对任意的$k\ge 1$, 有$Ay_{l_k}\ne 0$.$h_{l_k}=\frac{Ay_{l_k}}{\|Ay_{l_k}\|^2}$, 因此对任意的$k\ge1$, 有$\langle{Ay_{l_k}}{h_{l_k}}\rangle=1$, 那么(3.17)式可写为

$\langle{Ay_{l_k}}{(x+\xi_{k}h_{l_k})-y_{l_k}}\rangle\ge0,\ \ \forall k\ge 1.$

$\langle{A(x+\xi_{k}h_{l_k})}{(x+\xi_{k}h_{l_k})-y_{l_k}}\rangle\ge0,\ \ \forall k\ge 1,$

$$$\label{szb11} \langle{Ax}{x-y_{l_k}}\rangle\ge\langle{Ax-A(x+\xi_{k}h_{l_k})}{(x+\xi_{k}h_{l_k})-y_{l_k}}\rangle -\langle{Ax}{\xi_{k}h_{l_k}}\rangle,\ \ \forall k\ge 1.$$$

$\begin{eqnarray*} 0\le\limsup\limits_{k\to\infty}\|\xi_{k}h_{l_k}\|= \limsup\limits_{k\to\infty}(\frac{\xi_{k}}{\|Ay_{n_k}\|}) \le\frac{\limsup\limits_{k\to\infty}\xi_{k}}{\liminf\limits_{k\to\infty}\|Ay_{n_k}\|}=0.\\ \end{eqnarray*}$

$$$\label{szc1} \|z_n-p\|^2\le\|w_n-p\|^2-(1-\mu^2)\|w_n-y_n\|^2,\ \ \forall p\in {\rm Fix}(T)\cap VI(C,A).$$$

$\begin{matrix}\label{szc2} \|z_n-p\|^2&=&\|y_n-\lambda_n(Ay_n-Aw_n)-p\|^2 \\ &=&\|y_n-p\|^2+\lambda_n^2\|Ay_n-Aw_n\|^2 -2\lambda_n\langle{y_n-p}{Ay_n-Aw_n}\rangle \\ &=&\|w_n-p\|^2+\|w_n-y_n\|^2+2\langle{y_n-w_n}{w_n-p}\rangle \\ & &+\lambda_n^2\|Ay_n-Aw_n\|^2-2\lambda_n\langle{y_n-p}{Ay_n-Aw_n}\rangle \\ &=&\|w_n-p\|^2+\|w_n-y_n\|^2-2\langle{y_n-w_n}{y_n-w_n}\rangle+2\langle{y_n-w_n}{y_n-p}\rangle \\ &&+\lambda_n^2\|Ay_n-Aw_n\|^2-2\lambda_n\langle{y_n-p}{Ay_n-Aw_n}\rangle \\ &=&\|w_n-p\|^2-\|w_n-y_n\|^2+2\langle{y_n-w_n}{y_n-p}\rangle \\ & &+\lambda_n^2\|Ay_n-Aw_n\|^2-2\lambda_n\langle{y_n-p}{Ay_n-Aw_n}\rangle \\ &=&\|w_n-p\|^2-\|w_n-y_n\|^2+2\langle{y_n-w_n+\lambda_nAw_n}{y_n-p}\rangle \\ & &+\lambda_n^2\|Ay_n-Aw_n\|^2-2\lambda_n\langle{Ay_n}{y_n-p}\rangle. \end{matrix}$

$\begin{eqnarray*} \|z_n-p\|^2&\le&\|w_n-p\|^2-\|w_n-y_n\|^2+\lambda_n^2\|Ay_n-Aw_n\|^2\\ &\le&\|w_n-p\|^2-\|w_n-y_n\|^2+\mu^2\|y_n-w_n\|^2\\ &=&\|w_n-p\|^2-(1-\mu^2)\|w_n-y_n\|^2. \end{eqnarray*}$

$\begin{eqnarray*} \|x_{n}-p\|\le \max\{\|x_1-p\|,\frac{M_1+\|f(p)-p\|+\|(I-\rho F)p\|}{\tau-\delta}\},\ \ \forall n\ge1. \end{eqnarray*}$

$x_{n+1}$的定义知

$\begin{matrix}\label{szd31} \|x_{n+1}-p\|^2&=&\|\beta_nf(x_n)+\gamma_nx_n+[(1-\gamma_n)I-\beta_n\rho F]Tz_n-p\|^2 \\ &=&\|\beta_n(f(x_n)-f(p))+\gamma_n(x_n-p)+ (1-\gamma_n)[(I-\frac{\beta_n}{1-\gamma_n}\rho F)Tz_n \\ & &-(I-\frac{\beta_n}{1-\gamma_n}\rho F)p] +\beta_n(f-\rho F)p\|^2 \\ &\le&\|\beta_n(f(x_n)-f(p))+\gamma_n(x_n-p) +(1-\gamma_n) [(I-\frac{\beta_n}{1-\gamma_n}\rho F)Tz_n \\ & &-(I-\frac{\beta_n}{1-\gamma_n}\rho F)p]\|^2 +2\beta_n\langle{(f-\rho F)p}{x_{n+1}-p}\rangle \\ &\le&[\beta_n\delta\|x_n-p\|+\gamma_n\|x_n-p\|+(1-\gamma_n) (1-\frac{\beta_n}{1-\gamma_n}\tau)\|z_n-p\|]^2 \\ & &+2\beta_n\langle{(f-\rho F)p}{x_{n+1}-p}\rangle \\ &\le&\beta_n\delta\|x_n-p\|^2+\gamma_n\|x_n-p\|^2+ (1-\beta_n\tau-\gamma_n)\|z_n-p\|^2 \\ & &+2\beta_n\langle{(f-\rho F)p}{x_{n+1}-p}\rangle \\ &\le&(\beta_n\delta+\gamma_n)\|x_n-p\|^2+(1-\beta_n\tau-\gamma_n)\|z_n-p\|^2+\beta_n M_2, \end{matrix}$

$\|x_n-w_n\|=\alpha_n\|x_n-x_{n-1}\| \to0,\ \ n\to\infty.$

$\|z_n-y_n\|=\lambda_n\|Ay_n-Aw_{n}\|\to0,\ \ n\to\infty,$

$\|x_n-y_n\|\le\|x_n-w_n\|+\|w_n-y_n\|\to0,\ \ n\to\infty,$
$\|x_n-z_n\|\le\|x_n-w_n\|+\|w_n-y_n\|+\|y_n-z_n\|\to0,\ \ n\to\infty.$

$\begin{matrix}\label{szd43} \limsup\limits_{n\to\infty}\langle{(f-\rho F)p}{x_n-p}\rangle &=&\lim\limits_{k\to\infty}\langle{(f-\rho F)p}{x_{n_k}-p}\rangle \\ &=&\langle{(f-\rho F)p}{z-p}\rangle\le0. \end{matrix}$

$\begin{matrix}\label{szd44} \limsup\limits_{n\to\infty}\langle{(f-\rho F)p}{x_{n+1}-p}\rangle &\le&\limsup\limits_{n\to\infty}(\langle{(f-\rho F)p}{x_{n+1}-x_{n}}\rangle +\langle{(f-\rho F)p}{x_n-p}\rangle) \\ &\le&\limsup\limits_{n\to\infty}[\|(f-\rho F)p\|\|x_{n+1}-x_{n}\|+\langle{(f-\rho F)p}{x_{n}-p}\rangle] \\ &\le&0. \end{matrix}$

$$$\label{szd45} \limsup\limits_{n\to\infty}[\frac{2\langle{(f-\rho F)p}{x_{n+1}-p}\rangle}{\tau-\delta}+\frac{(1-\beta_n\tau-\gamma_n) \alpha_n\|x_n-x_{n-1}\|M_5}{(\tau-\delta)\beta_n}]\le0.$$$

$\|x_{n_j}-p\|^2\le\|x_{n_j+1}-p\|^2.$

$$$\label{szd46} \|x_{m_k}-p\|^2\le\|x_{m_k+1}-p\|^2,$$$
$$$\label{szd47} \|x_{k}-p\|^2\le\|x_{m_k+1}-p\|^2.$$$

$\begin{eqnarray*} (1-\beta_{m_k}\tau-\gamma_{m_k})(1-\mu^2)\|w_{m_k}-y_{m_k}\|^2 &\le&\|x_{m_k}-p\|^2-\|x_{{m_k}+1}-p\|^2+\beta_{m_k} M_4\\ &\le&\beta_{m_k} M_4. \end{eqnarray*}$

$$$\label{szd48} \lim\limits_{k\to\infty}\frac{\alpha_{m_k}}{\beta_{m_k}}\|x_{m_k}-x_{m_k-1}\|=0,$$$
$$$\label{szd49} \limsup\limits_{k\to\infty}\langle{(f-\rho F)p}{x_{m_k+1}-p}\rangle \le0.$$$

$\begin{eqnarray*} &&\|x_{m_k+1}-p\|^2\\ &\le&[1-\beta_{m_k}(\tau-\delta)]\|x_{m_k}-p\|^2 \\ &&+\beta_{m_k}(\tau-\delta) [\frac{2\langle{(f-\rho F)p}{x_{{m_k}+1}-p}\rangle}{\tau-\delta}+\frac{(1-\beta_{m_k}\tau-\gamma_{m_k}) \alpha_{m_k}\|x_{m_k}-x_{{m_k}-1}\|M_5}{(\tau-\delta)\beta_{m_k}}]\\ &\le&[1-\beta_{m_k}(\tau-\delta)]\|x_{m_k+1}-p\|^2\\ &&+\beta_{m_k}(\tau-\delta) [\frac{2\langle{(f-\rho F)p}{x_{{m_k}+1}-p}\rangle}{\tau-\delta}+\frac{(1-\beta_{m_k}\tau-\gamma_{m_k}) \alpha_{m_k}\|x_{m_k}-x_{{m_k}-1}\|M_5}{(\tau-\delta)\beta_{m_k}}]. \end{eqnarray*}$

$\begin{eqnarray*} \|x_{m_k+1}-p\|^2 \le\frac{2\langle{(f-\rho F)p}{x_{{m_k}+1}-p}\rangle}{\tau-\delta}+\frac{(1-\beta_{m_k}\tau-\gamma_{m_k}) \alpha_{m_k}\|x_{m_k}-x_{{m_k}-1}\|M_5}{(\tau-\delta)\beta_{m_k}}. \end{eqnarray*}$

$\begin{matrix}\label{szd410} \|x_{k}-p\|^2&\le&\|x_{m_k+1}-p\|^2 \\ &\le&\frac{2\langle{(f-\rho F)p}{x_{{m_k}+1}-p}\rangle} {\tau-\delta}+\frac{(1-\beta_{m_k}\tau-\gamma_{m_k}) \alpha_{m_k}\|x_{m_k}-x_{{m_k}-1}\|M_5}{(\tau-\delta)\beta_{m_k}}.\end{matrix}$

## 4 算法的计算机检验

1. Alg.1的参数选取: $r=0.99; l=0.05; \alpha=\mu=0.5; \rho=2; \tau_n=\frac{1}{n^2}; \beta_n=\frac{1}{2(n+1)}; \gamma_n=\frac{n}{2(n+1)}$. 其中, $T(x)=f(x)=F(x)=\frac{x}{3}$.

2. Alg.N的参数选取: $\lambda=0.5; \beta_n=\frac{1}{2(n+1)}$. 并且选取$T(x)=\frac{x}{3}$.

3. Alg.T的参数选取: $r=0.99; l=0.05; \mu=0.5; \alpha_n=\frac{n}{2(n+1)}; \beta_n=\frac{1}{2(n+1)}$. 并且选取$T(x)=\frac{x}{3}$.

$F_1(x)=(f_1(x),f_2(x),\cdots, f_n(x)),$
$F_2(x)=Mx+q,$
$f_i(x)=x^2_{i-1}+x^2_{i}+x_{i-1}x_{i}+x_{i}x_{i+1},i=1,2,\cdots, m,$

$M = \left(\begin{array}{cccccc} 4& ~-2 ~& & &\\ 1& 4 &-2 & &\\ & 1 & 4 & ~-2~ &\\ & & \ddots&\ddots &\vdots\\ & & & 1 &4\\ \end{array}\right).$

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

Goldstein A A.

Convex programming in Hilbert space

Bull New Ser Am Math Soc, 1964, 70(5): 109-112

Korpelevich G M.

The extragradient method for finding saddle points and other problems

Ekonomikai Matematicheskie Metody, 1976, 12: 747-756

Tseng P.

A modified forward-backward splitting method for maximal monotone mapping

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

Cai G, Yekini S, Iyiola O S.

Inertial Tseng's extragradient method for solving variational inequality problems of pseudo-monotone and non-lipschitz operators

J Ind Manag Optim, 2021, 1: 1-30

Moudafi A.

Viscosity approximation methods for fixed-points problems

J Math Anal Appl, 2000, 241: 46-55

The hybrid steepest descent method for the variational inequality problem over the intersection of fixed point sets of nonexpansive mappings

//Butnariu D, Censor Y, Reich S, Eds. Inherently Parallel Algorithms in Feasibility and Optimization and Their Application. New York: Elservier, 2001: 473-504

Halpern B.

Fixed points of nonexpanding maps

Bull Amer Math, 1967, 73: 957-961

Ishikawa S.

Fixed points by a new iteration method

Proc Amer Math Soc, 1974, 44: 147-150

Marino G, Xu H K.

A general iterative method for nonexpansive mappings in Hilbert spaces

J Math Anal Appl, 2006, 318: 43-52

Tian M.

A general iterative method for nonexpansive mappings in Hilbert spaces

Nonlinear Anal, 2010, 73(3): 689-694

Ke Y F, Ma C F.

The generalized viscosity implicit rules of nonexpansive mappings in Hilbert spaces

Fixed Point Theory Appl, 2015, 2015: 190

Nadezhkina N, Takahashi W.

Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings

J Optim Theory Appl, 2006, 128(1): 191-201

Thong D V, Hieu D V.

Inertial subgradient extragradient algorithms with line-search process for solving variational inequality problems and fixed point problems

Numer Algor, 2019, 80(4): 1283-1307

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(4): 715-740

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

Cottle R W, Yao J C.

Pseudo-monotone complementarity problems in Hilbert space

J Optim Theory Appl, 1992, 72(2): 281-295

Xu H K.

Iterative algorithms for nonlinear operators

J London Math Soc, 2002, 66: 240-256

Xu H K, Kim T H.

Convergence of hybrid steepest-descent methods for variational inequalities

J Optim Theory Appl, 2003, 119(1): 185-201

Glowinski R, Lions J L, Trémolières R. Numerical Analysis of Variational Inequalities. Amsterdam: Elsevier, 1981

Iusem A, Otero R G.

Inexact versions of proximal point and augmented lagrangian algorithms in Banach spaces

Numer Funct Anal Optim, 2001, 22: 609-640

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

He B S, Liao L Z.

Improvements of some projection methods for monotone nonlinear variational inequalities

J Optim Theory Appl, 2002, 112(1): 111-128

Sun D F.

A projection and contraction method for the nonlinear complementarity problem and it's extensions

Math Numer Sinica, 1994, 16(3): 183-194

/

 〈 〉