# A Forward-Backward-Forward Algorithm for Solving Quasimonotone Variational Inequalities

Authors: Tzu-Chien Yin; Nawab Hussain
Journal: Journal of Function Spaces
 (2022)

---

## Abstract

In this paper, we continue to investigate the convergence analysis of Tseng-type forward-backward-forward algorithms for solving quasimonotone variational inequalities in Hilbert spaces. We use a self-adaptive technique to update the step sizes without prior knowledge of the Lipschitz constant of quasimonotone operators. Furthermore, we weaken the sequential weak continuity of quasimonotone operators to a weaker condition. Under some mild assumptions, we prove that Tseng-type forward-backward-forward algorithm converges weakly to a solution of quasimonotone variational inequalities.


---

## Body

## 1. Introduction

LetH be a real Hilbert space endowed with inner product ·,· and corresponding norm ∥·∥. Let C be a nonempty closed and convex subset of H. Let f:H⟶H be an operator. Our purpose of this paper is to investigate the following Stampacchia-type variational inequality (shortly, VIC,f).Findu∈C such that
(1)fu,x−u≥0,∀x∈C.Denote the solution set of (1) by SolC,f.Variational inequality problem (1) was introduced by Stampacchia [1] in 1964. Now it is well-known that variational inequality problem (1) provides a natural, convenient, and unified framework for the study of a large number of problems in economics, operation research, and engineering (see [2–5]). Variational inequality (1) contains, as special cases, such well-known problems in mathematical programming as systems of nonlinear equations, optimization problems ([3, 6]), complementarity problems ([7–9], and fixed-point problems ([10–20]). Many iterative algorithms for solving variational inequalities and related problems have been proposed and investigated (see, for example, [1, 6, 9, 16, 21–40]). Among them, one of the influential algorithms for solving VIC,f) is the projection-gradient algorithm ([28, 39, 40]) which defines a sequence uk by
(2)uk+1=PCuk−λfuk,∀k≥0,where PC is the orthogonal projection operator onto C and λ>0 is the step size.The projection-gradient algorithm guarantees the convergence of the sequenceuk defined by (2) if f is strongly (pseudo-)monotone (see [8, 41]) or f is inverse strongly monotone (see [3, 42]). However, if f is plain monotone, then the sequence uk generated by (2) does not necessarily converge. Consequently, Korpelevich [43] proposed an extragradient algorithm which generates a sequence uk by
(3)u0∈H,vk=PCuk−λfuk,uk+1=PCuk−λfvk,∀k≥0.This algorithm guarantees the convergence of the sequenceuk defined by (3) if f is pseudomonotone. Since then, Korpelevich’s algorithm has attracted so much attention by many scholars, who modified it in several different forms (see, e.g., [34, 44–47]). Especially, Vuong [31] proved that Korpelevich’s extragradient method has weak convergence provided that f is sequentially weakly continuous and pseudomonotone.A challenging task when devise efficient algorithms for solving variational inequalities is to avoid to compute the projection operators at each iteration because the computation of the projection operator may be very expensive. In this respect, Tseng [30] modified extragradient algorithm with the following form:
(4)u0∈H,vk=PCuk−λfuk,uk+1=uk+λfuk−fvk,∀k≥0.Boţ et al. [48] approach the solution of VIC,f from a continuous perspective by means of trajectories generated by the following dynamical system of forward-backward-forward type:
(5)u0=u0,vt=PCut−λfut,u̇t+ut=vt+λfut−fvt,where λ>0 and u0∈H.Note that (5) has its roots and the existence and uniqueness of the trajectory x∈C10,+∞,H generated by (5) has been obtained (see [49]). The explicit time discretization of the dynamical system (5) yields the following Tseng-type forward-backward-forward algorithm:
(6)u0∈H,vk=PCuk−λfuk,uk+1=μkvk+λfuk−vk+1−μkuk,∀k≥0.Bot et al. ([48]) proved that the sequence uk generated by (6) converges weakly to an element in SolC,f provided f is pseudomonotone and sequentially weakly continuous. On the other hand, for solving (1) and related problems, some self-techniques have been used to relax the step size without prior knowledge of the Lipschitz constant of the operator f (see [50–53]).LetSoldC,f be the solution set of the dual variational inequality of (1), that is,
(7)SoldC,f≔u∈C∣fx,x−u≥0,∀x∈C.Note thatSoldC,f is closed convex. If C is convex and f is continuous, then SoldC,f⊂SolC,f.To prove the convergence of the sequenceuk, a common assumption SolC,f⊂SoldC,f has been used, that is,
(8)fx,x−u≥0,∀u∈SolC,f,x∈C,which is a direct consequence of the pseudomonotonicity of f. But this conclusion (that is, SolC,f⊂SoldC,f) is false, if f is quasimonotone.In this paper, we introduce a self-adaptive Tseng-type forward-backward-forward algorithm to solve quasimonotone variational inequalities (1). The algorithm is designed such that the step sizes are dynamically chosen and its convergence is guaranteed without prior knowledge of the Lipschitz constant of f. Moreover, we replace the sequential weak continuity imposed on f by a weaker condition. We show that the proposed algorithm converges weakly to a solution of quasimonotone variational inequalities under some additional conditions.


## 2. Preliminaries

LetC be a nonempty convex and closed subset of a real Hilbert space H. Use “⇀” and “⟶” to denote weak convergence and strong convergence, respectively. Let f:H⟶H be an operator. Recall that f is said to be
(i)
strongly monotone if there exists a positive constantα such that
(9)fu−fv,u−v≥α∥u−v∥2,∀u,v∈H(ii)
α-inverse strongly monotone if there exists a positive constant α such that
(10)fu−fv,u−v≥α∥fu−fv∥2,∀u,v∈H(iii)
monotone if(11)fu−fv,u−v≥0,∀u,v∈H(iv)
pseudomonotone if(12)fv,u−v≥0impliesfu,u−v≥0,∀u,v∈H(v)
quasimonotone if(13)fv,u−v>0impliesfu,u−v≥0,∀u,v∈HIt is easy to see thatstrongmonotonicity⇒monotonicity⇒pseudomonotonicity⇒quasimonotonicity.But the reverse assertions are not true in general.Example 1 (see [50]).
LetH=ℝ4 and C=x1,x2,x3,x4T∈ℝ4:x1−x2−x3≥1. Let f:C⟶ℝ4 be defined by fx=∥x∥2+2u for all x∈C, where u=1,−1,−1,0T. Then, f is pseudomonotone on C. But f is not monotone on C.Example 2 (see [33]).
The functionf:ℝ⟶ℝ defined by fx=x2 is quasimonotone on ℝ, but not pseudomonotone on ℝ.An operatorf:H⟶H is said to be η-Lipschitz continuous if there exists a positive constant η such that
(14)fu−fv≤ηu−v,∀u,v∈H.Ifη=1, then f is said to be nonexpansive.An operatorf:H⟶H is said to be sequentially weakly continuous if for given sequence uk: uk⇀u implies that fuk⇀fu.For∀x∈H, there exists a unique point in C, denoted by PCx satisfying
(15)∥x−PCx∥≤∥y−x∥,∀y∈C.Moreover,PC has the following property:
(16)x−PCx,y−PCx≤0,∀x∈H,∀y∈C.


## 3. Main Results

In this section, we present our main results.LetH be a real Hilbert space and C⊂H a nonempty closed convex set. Assume that the following conditions are satisfied:(C1) The operatorf is quasimonotone on H.(C2) The operatorf is η-Lipschitz continuous on H.(C3)SoldC,f≠∅ and u∈C:fu=0\SoldC,f is a finite set.Assume that the operatorf possesses the following property: for any given sequence uk⊂H,
(17)uk⇀u†∈H,liminfk⟶+∞fuk=0implythatfu†=0.Remark 1.
If the operatorf is sequentially weakly continuous, then f satisfies the above property (17).Next, we propose a self-adaptive Tseng-type forward-backward-forward algorithm for solving the quasimonotone variational inequality (1).Algorithm 1: Let λ0>0 and δ∈0,1. Select the starting point u0∈H and the sequence of relaxation parameters μkk≥0⊂0,1 satisfying liminfk⟶+∞μk>0. Set k=0.
Step 1. Letuk and λk be given. Computevk=Pcuk−λkfuk.Criterion: ifvk=uk, then stop.Step 2. Computeuk+1=μkvk+λkfuk−fvk+1−μkuk,λk+1=minδ∥uk−vk∥/∥fuk−fvk∥,λk,fuk≠fvk,λk,else,updatek to k+1 and go to Step 1.Remark 2.
Ifvk=uk, that is, uk=PCuk−λkfuk, then uk∈SolC,f. In what follows, we assume that vk≠uk. In this case, we can obtain an infinite sequence uk generated by Algorithm 1.Remark 3.
According to the definition (3.4) ofλk, λk is monotonically decreasing and therefore converges. Set limk⟶+∞λk=λ~. It is obvious that minδ/η,λ0≤λ~≤λ0.Next, we prove the convergence of the sequenceuk generated by Algorithm 1.Theorem 4.
Suppose that the conditions (C1)-(C3) and (17) are satisfied. Then, the sequence uk generated by Algorithm 1 converges weakly to a point in SolC,f.Proof.
Letx∗∈SoldC,f. Set wk=vk+λkfuk−fvk,∀k≥0. Then, we have
(18)wk−x∗2=vk+λkfuk−fvk−x∗2=vk−x∗2+2λkfuk−fvk,vk−x∗+λk2fuk−fvk2=uk−x∗2+vk−uk2+2vk−uk,uk−x∗+2λkfuk−fvk,vk−x∗+λk2fuk−fvk2=uk−x∗2−vk−uk2+2vk−uk,vk−x∗+2λkfuk−fvk,vk−x∗+λk2fuk−fvk2.
Sincex∗∈SoldC,f⊂C, from (16) and (3.2), we achieve uk−λkfuk−vk,x∗−vk≤0. It follows that
(19)uk−vk,x∗−vk≤λkfuk,x∗−vk.
Usingvk∈C and x∗∈SoldC,f, we obtain
(20)fvk,vk−x∗≥0.
By (18), (19), and (20), we receive
(21)wk−x∗2≤uk−x∗2−vk−uk2+2λkfuk,x∗−vk+2λkfuk−fvk,vk−x∗+λk2fuk−fvk2=uk−x∗2−vk−uk2+2λkfvk,x∗−vk+λk2fuk−fvk2≤uk−x∗2−vk−uk2+λk2fuk−fvk2.
From (3.4), we havefuk−fvk≤δ/λk+1uk−vk. This together with (21) implies that
(22)wk−x∗2≤uk−x∗2−1−δ2λk2λk+12vk−uk2.
Note thatlimk⟶+∞λk/λk+1=1. So, there exists an integer K such that 1−δ2λk2/λk+12>0 when k≥K. Hence, from (22), we deduce ∥wk−x∗∥≤∥uk−x∗∥ when k≥K.
In terms of (3.3), we get(23)uk+1−x∗=μkwk−x∗+1−μkuk−x∗≤μkwk−x∗+1−μkuk−x∗≤uk−x∗.
Thus, the sequence∥uk−x∗∥ is monotonically decreasing and limk⟶+∞∥uk−x∗∥ exists. So, the sequence uk is bounded.
By virtue of (22) and (23), we have
(24)∥uk+1−x∗∥2≤μk∥wk−x∗∥2+1−μk∥uk−x∗∥2≤∥uk−x∗∥2−μk1−δ2λk2λk+12∥vk−uk∥2.
It follows that(25)μk1−δ2λk2λk+12∥vk−uk∥2≤∥uk−x∗∥2−∥uk+1−x∗∥2.
Sincelimk⟶+∞1−δ2λk2/λk+12=1−δ2>0, liminfk⟶+∞μk>0, and limk⟶+∞∥uk−x∗∥ exist, it follows from (25) that
(26)limk⟶+∞vk−uk=0.
Sincef is Lipschitz, from (26), we obtain
(27)limk⟶+∞fvk−fuk=0.
Thanks to (3.3), we derive(28)uk+1−uk≤μkuk−vk+μkλkfuk−fvk.
Based on (26)–(28), we deduce
(29)limk⟶+∞uk+1−uk=0.
According to (16) and (3.2), we have
(30)uk−λkfuk−vk,x−vk≤0,∀x∈C.
It follows that(31)1λkuk−vk,x−vk+fuk,vk−uk≤fuk,x−uk,∀x∈C.
Sinceuk is bounded, by (26), vk is also bounded. At the same time, using the Lipschitz continuity of f, fuk is bounded. Combining (26), (27), and (31), we attain
(32)liminfk⟶+∞fuk,x−uk≥0,∀x∈C.
Sinceuk is bounded, there exists a subsequence uki of uk such that uki⇀u^∈C as i⟶+∞. By virtue of (32), we have
(33)liminfi⟶+∞fuki,x−uki≥0,∀x∈C.
Next, we consider two possible cases.
Case 1.liminfi⟶+∞∥fuki∥=0. Since uki⇀u^ and f satisfies (17), we deduce that fu^=0.
Case 2.liminfi⟶+∞∥fuki∥>0. In this case, ∃I0>0 such that fuki≠0 for all i≥I0. From (33), we obtain
(34)liminfi⟶+∞fuki∥fuki∥,x−uki≥0,∀x∈C.
Choose a positive strictly decreasing sequenceεj such that εj⟶0 as j⟶+∞. Thanks to (34), there exists a strictly increasing subsequence kij with the property that kij≥I0 and
(35)fukijfukij,x−ukij+εj>0,∀j≥0.
It follows that(36)fukij,x−ukij+εjfukij>0,∀j≥0.
Setyj=fukij/∥fukij∥2 for all j≥0. Thus, we have fukij,yj=1 for each j≥0. From (36), we deduce
(37)fukij,x+εjfukijyj−ukij>0,∀j≥0.
Sincef is quasimonotone on H, by (37), we get
(38)fx+εjfukijyj,x+εjfukijyj−ukij≥0,∀j≥0.
Observe thatlimj⟶+∞εj∥fukij∥∥yj∥=limj⟶+∞εj=0. Since f is Lipschitz continuous, fx+εj∥fukij∥yj⟶fx as j⟶+∞. Thus, taking the limit as j⟶+∞ in (38), we obtain that
(39)fx,x−u^≥0,∀x∈C.
So,u^∈SoldC,f.
Next, we proveuk has finite weak cluster points in SolC,f. First, we show that uk has at most one weak cluster point in SoldC,f. Let u^∈SoldC,f and u~∈SoldC,f be two distinct weak cluster points of uk. There exist two sequences uki and ukj of uk satisfying uki⇀u^ as i⟶+∞ and ukj⇀u~ as j⟶+∞. Note that for all k≥0,
(40)2uk,u^−u~=∥uk−u~∥2−∥uk−u^∥2+∥u^∥2−∥u~∥2.
Sincelimk⟶+∞∥uk−u^∥ and limk⟶+∞∥uk−u~∥ exist, by (40), we conclude that limk⟶+∞uk,u^−u~ exists, denoted by l. Thus,
(41)l=limi⟶+∞uki,u^−u~=limj⟶+∞ukj,u^−u~.
Sinceuki⇀u^ and ukj⇀u~, from (41), we have
(42)l=u^,u^−u~=u~,u^−u~,which implies that ∥u^−u~∥2=0 and hence, u^=u~. Therefore, uk has at most one weak cluster point in SoldC,f. By the condition (C3), u∈C,fu=0\SoldC,f is a finite set. Therefore, uk has finite weak cluster points in SolC,f.
Letp1,p2,⋯,pt be the finite weak cluster points of uk in SolC,f. Set I=1,2,⋯,t and
(43)σ=min∥pn−pm∥3,n,m∈I,n≠m.
Taking any weak cluster pointpn,n∈I, there exists a subsequence unki of uk such that unki⇀pn as i⟶+∞. Then, we have
(44)limi⟶+∞unki,pn−pm∥pn−pm∥=pn,pn−pm∥pn−pm∥,∀m∈I.
Observe that∀m≠n,
(45)pn,pn−pm∥pn−pm∥=∥pn−pm∥2+∥pn∥2−∥pm∥22∥pn−pm∥>σ+∥pn∥2−∥pm∥22∥pn−pm∥.
According to (44) and (45), there exists a large enough positive integer ni such that when i≥ni,
(46)unki∈x:x,pn−pm∥pn−pm∥>σ+∥pn∥2−∥pm∥22∥pn−pm∥,m∈I,m≠n.
Set(47)Rn=⋂m=1,m≠ntx:x,pn−pm∥pn−pm∥>σ+∥pn∥2−∥pm∥22∥pn−pm∥.
In the light of (46) and (47), we have unki∈Rn when i≥maxni,n∈I.
Now, we show thatuk∈⋃n=1tRn for a large enough k. Assume that there exists a subsequence ukj of uk such that ukj∉⋃n=1tRn. By the boundedness of ukj, there exists a subsequence of ukj convergent weakly to p†. Without loss of generality, we still denote the subsequence as ukj. According to assumptions, ukj∉⋃n=1tRn, so ukj∉Rn for any n∈I. Therefore, there exists a subsequence ukjs of ukj such that ∀s≥0,
(48)ukjs∉x:x,pn−pm∥pn−pm∥>σ+∥pn∥2−∥pm∥22∥pn−pm∥,m∈I,m≠n.
Thus,(49)p†∉x:x,pn−pm∥pn−pm∥>σ+∥pn∥2−∥pm∥22∥pn−pm∥,m∈I,m≠n,which implies that p†≠pn,n∈I. This is impossible. So, for a large enough positive integer K0, uk∈⋃n=1tRn when k≥K0.
Next, we show thatuk has a unique weak cluster point in SolC,f. First, from (29), there exists a positive integer K1≥K0 such that ∥uk+1−uk∥<σ for all k≥K1. Assume that uk has at least two weak cluster points in SolC,f. Then, there exists K^≥K1 such that uK^∈Rn and uK^+1∈Rm, where n,m∈I and t≥2, that is,
(50)uK^∈Rn=⋂m=1,m≠ntx:x,pn−pm∥pn−pm∥>σ+∥pn∥2−∥pm∥22∥pn−pm∥,uK^+1∈Rm=⋂n=1,n≠mtx:x,pm−pn∥pm−pn∥>σ+∥pm∥2−∥pn∥22∥pm−pn∥.
Therefore,(51)uK^,pn−pm∥pn−pm∥>σ+∥pn∥2−∥pm∥22∥pn−pm∥,(52)uK^+1,pm−pn∥pm−pn∥>σ+∥pm∥2−∥pn∥22∥pm−pn∥.
Combining (51) and (52), we achieve
(53)uK^−uK^+1,pn−pm∥pn−pm∥>2σ.
At the same time, we have(54)uK^+1−uK^<σ.
Based on (53) and (54), we deduce
(55)2σ<uK^−uK^+1,pn−pmpn−pm≤uK^−uK^+1<σ.
This leads to a contradiction. Thus,uk has a unique weak cluster point in SolC,f. Therefore, uk converges weakly to a point in SolC,f. This completes the proof.☐Algorithm 2: Let λ0>0 and δ∈0,1. Select the starting point u0∈H. Set k=0.
Step 1. Letuk and λk be given. Computevk=PCuk−λkfuk.Criterion: ifvk=uk, then stop.Step 2. Computeuk+1=vk+λkfuk−fvk,λk+1=minδ∥uk−vk∥/∥fuk−fvk∥,λk,fuk≠fvk,λk,else,updatek to k+1 and go to Step 1.Corollary 5.
Suppose that the conditions (C1)-(C3) and (17) are satisfied. Then, the sequence uk generated by Algorithm 2 converges weakly to a point in SolC,f.Remark 6.
Iff is pseudomonotone, then Theorem 4 and Corollary 5 hold.Remark 7.
If the operatorf is sequentially weakly continuous and also satisfies conditions (C1)-(C3), then Theorem 4 and Corollary 5 still hold.Remark 8.
Our main purpose is to solve (1); hence, a natural condition is SolC,f≠∅. In order to prove our main theorem, we assume that SoldC,f≠∅. Note that SoldC,f⊂SolC,f. This means that even if SolC,f≠∅, SoldC,f≠∅ does not necessarily hold. A question is under what conditions SoldC,f≠∅ holds. In fact, we have the following results:
(i)
Iff is pseudomonotone on C and SolC,f≠∅, then SoldC,f≠∅(ii)
Iff is quasimonotone on C, intC≠∅ and u∣fu=0≠∅, then SoldC,f≠∅ (see [35])



---

*Source: 7117244-2022-01-04.xml*