# Two New Weak Convergence Algorithms for Solving Bilevel Pseudomonotone Equilibrium Problem in Hilbert Space

Authors: Gaobo Li
Journal: Journal of Mathematics
 (2022)

---

## Abstract

In this paper, we introduce two new subgradient extragradient algorithms to find the solution of a bilevel equilibrium problem in which the pseudomonotone and Lipschitz-type continuous bifunctions are involved in a real Hilbert space. The first method needs the prior knowledge of the Lipschitz constants of the bifunctions while the second method uses a self-adaptive process to deal with the unknown knowledge of the Lipschitz constant of the bifunctions. The weak convergence of the proposed algorithms is proved under some simple conditions on the input parameters. Our algorithms are very different from the existing related results in the literature. Finally, some numerical experiments are presented to illustrate the performance of the proposed algorithms and to compare them with other related methods.


---

## Body

## 1. Introduction

LetH be a real Hilbert space and C be a nonempty closed convex subset of H. Let g:H×H⟶ℝ be a bifunction with gx,x=0 for all x∈C. The equilibrium problem (EP for short) is associated with g and C to find z∈C such that(1)gz,y≥0,∀y∈C.The solution set of (1) is denoted by EPg,C.Ifgx,y=Gx,y−x for all x,y∈H, where G is a mapping from H into itself, then the problem (1) becomes the following variational inequality problem (VIP for short):(2)findx∗∈Csuch thatGx∗,y−x∗≥0,∀y∈C.The solution set of (2) is denoted by VIG,C.The EP (1) has a simple form and is very general in the sense that it includes, as special cases, the variational inequality problem, fixed point problem, complementarity problem, optimization problem as well as the Nash equilibrium problem; see,for example [1,2]. Many methods have been proposed for approximating a solution of the EP (1). Mastroeni [3] used the auxiliary problem principle which was first introduced for solving the optimization problems to solve EP (1) and presented the iteration algorithm in the form(3)x0∈C,xn+1=argminλgxn,y+12y−xn2:y∈C,where the stepsize λ>0. For obtaining the convergence of this algorithm, the bifunction g is required to be strongly monotone and Lipschitz-type continuous. To avoid the hypothesis of the strong monotonicity, Quoc et al. [4] first proposed the extragradient method (or the proximal-like methods) in which two strongly convex problems are solved at each iteration. The extragradient method is as follows: x0∈C and(4)yn=argminλgxn,y+12y−xn2:y∈C,xn+1=argminλgyn,y+12y−xn2:y∈C.In 2018, Hieu [5] presented a new extragradient method for solving the EP (1.1) as follows: x0,y0∈C and(5)xn+1=argminλnfyn,y+12y−xn2:y∈C,yn+1=argminλn+1fyn,y+12y−xn+12:y∈C,n≥0,where λn⊂0,∞ is a nonincreasing sequence and f is a strongly pseudomonotone and Lipschitz-type continuous mapping.In 2011, Censor et al. [6] proposed a new method, which is called the subgradient extragradient method, for solving the VIP (2). In 2016, Hieu [7] extended this method to the EP (1.1). In 2019, inspired by [5,7], Liu and Kong [8] introduced the following subgradient extragradient method for solving the EP (1): x0,y0∈C and(6)x1=argminλfy0,y+12y−x02:y∈C,y1=argminλfy0,y+12y−x12:y∈C,xn+1=argminλfy0,y+12y−xn2:y∈Hn,yn+1=argminλfy0,y+12y−xn+12:y∈C,n≥1,where Hn=z∈H:xn−λwn−1−yn,z−yn≤0 and wn−1∈∂2fyn−1,yn, and f is a pseudomonotone and Lipschitz-type continuous mapping.The advantage of equations (5) and (6) is that only one value of f at yn is computed at each iteration. On the recent methods for solving the EP (1), we refer the readers to [9–15].In this paper, our interest is the bilevel equilibrium problem (BEP for short) which consists of the following:(7)findx¯∈EPg,Csuch thatfx¯,y≥0,∀y∈EPg,C,where f:H×H⟶ℝ with fx,x=0 for all x∈H. The BEPs are the special cases of mathematical programs with equilibrium constraints and also are the generalization of variational inequality over equilibrium constraints, hierarchical minimization problems, and complementarity problems. The methods for solving BEPs have been studied extensively by many authors. Moudafi [16] introduced a proximal method and proved the weak convergence to a solution of the BEP (7). Dinh and Muu [17] proposed a penalty and gap function method for solving the BEP (7). Quy [18] introduced an algorithm by combining the proximal method with the Halpern method for solving bilevel monotone equilibrium and fixed point problem. Yuying et al. [19] presented an extragradient method as follows:(8)yn=argminλngxn,y+12y−xn2:y∈C,zn=argminλngyn,y+12y−xn2:y∈C,xn+1=ηnxn+1−ηnzn−αnμwn,wn∈∂2fzn,zn,where αn⊂0,1, λn⊂λ¯,λ¯ with λ¯>0, and ηn⊂0,1−αn. Anh and An [20] proposed the following subgradient extragradient method for solving the BEP (7):(9)yn=argminλngxn,y+12y−xn2:y∈C,zn=argminλngyn,y+12z−xn2:z∈Hn,xn+1=argminβnfzn,y+12t−zn2:z∈C,where Hn=v∈H:xn−λnwn−yn,v−yn≤0 with wn∈∂2gxn,yn, λn and βn are two nonnegative sequences.Observe that in the works mentioned above, the bifunctiong is monotone or pseudomonotone while f is strongly monotone, and then, the algorithms have a strong convergence. In this paper, inspired by [8,20], we propose two new subgradient extragradient methods for solving the BEP (7) where both the bifunction f and g are pseudomonotone. The first method needs the prior knowledge of the Lipschitz constants of the bifunctions while the second method uses a self-adaptive process to deal with the unknown knowledge of the Lipschitz constant of the bifunctions. The weak convergence of the proposed algorithms is proved under some sufficient assumptions. Finally, some numerical experiments are presented to illustrate the performance of the proposed algorithms and to compare them with other related methods.


## 2. Preliminaries

LetH be a real Hilbert space, ℝ be the set of all real numbers, and ℕ be the set of all positive integers. We list some well-known definitions and properties which will be used in our following analysis.Definition 1.
A mappingF:H⟶H is said to be(i)
monotone if(10)Fx−Fy,x−y≥0,∀x,y∈H;(ii)
pseudomonotone if(11)Fy,x−y≥0⇒Fx,x−y≥0,∀x,y∈H;(iii)
L-Lipschitz continuous if there exists a constant L>0 such that(12)Fx−Fy≤x−y,∀x,y∈H.Definition 2.
A bifunctionf:H×H⟶ℝ is said to be(i)
pseudomonotone onC if(13)fx,y≥0⇒fy,x≤0,∀x,y∈C.(ii)
Lipschitz-type continuous onC if there exists the constants c1>0 and c2>0 such that(14)fx,z≤fx,y+fy,z+c1x−y2+c2y−z2,∀x,y,z∈C.Remark 1.
IfF is L-Lipschitz continuous on H, then for each x,y∈H, fx,y=Fx,y−x is Lipschitz-type continuous with the constants c1=c2=L/2; see [21] for details.
LetC be a nonempty closed and convex subset of H. For each x∈H, there exists a unique point in C, denoted by PCx, such that(15)PCx=argminy−x:y∈C,PC is said to be the metric projection from H onto C. The following lemma characterizes the property of PC.Lemma 1.
LetPC:H⟶C be the metric projection. Then,(i)
z=PCx if and only if(16)x−z,y−z≤0,∀y∈C.(ii)
for ally∈C and x∈H,(17)y−PCx2+PCx−x2≤x−y2.Remark 2.
For any givenx¯∈H and v∈H with v≠0, let T=x∈H:v,x−x¯≤0. Then, for all y∈H, the projection ΠTy is defined by(18)∏Ty=y−max0,v,y−x¯v2v.
The formula (18) gives us an explicit manner to compute the projection of any point onto a half-space; see [22] for details.Definition 3.
(1)
The normal coneNC of C at x∈C is defined by(19)NCx=w∈H:w,y−x≤0,∀y∈C.(2)
The subdifferentiable of a convex functiong:C⟶ℝ at x∈H is defined by(20)∂gx=w∈H:gy−gx≥w,y−x,∀y∈C.Lemma 2 (see [23]).
Letg:C⟶ℝ be a convex subdifferentiable and lower semicontinuous function on C. Then, x∗ is a solution to the following convex problem:(21)mingx:x∈C,if and only if 0∈∂gx∗+NCx∗, where ∂gx∗ denotes the subdifferential of g and NCx∗ is the normal cone of C at x∗.For a proper, convex, and lower semicontinuous function:h:C⟶−∞,+∞ and λ>0, the proximal mapping of h with λ is defined by(22)progλhx=argminλhy+12x−y2:y∈C,x∈C.Lemma 3 (see [24, 25]).
For allx,y∈C and λ>0, the following inequality holds:(23)λhy−hprogλhx≥x−progλhx,y−progλhx.Remark 3.
From Lemma3, we note that if x=progλhx, then(24)x∈argminhy:y∈C=x∈C:hx=miny∈Chy.Lemma 4 (see [26]).
Letan and cn be two sequences of nonnegative real numbers satisfying the condition(25)an+1≤an+cn,∀n∈ℕ.
If∑ncn<∞, then limn⟶∞an exists.


## 3. Main Results

In this section, letℕ denotes the set of all positive integers, N0=ℕ∪0, H be a real Hilbert space, and C be a nonempty closed convex subset of H. The notation “⇀” denotes the weak converge. Let f,g:H×H⟶ℝ be two bifunctions satisfying the following conditions:(A1)
f and g are pseudomonotone on H(A2)
for eachy∈H, limsupn⟶∞fxn,y≤fx,y and limsupn⟶∞gxn,y≤gx,y for every sequence xn⇀x(A3)
fx,⋅ and gx,⋅ are convex, lower semicontinuous, and subdifferentiable of H for each x∈H(A4)
g and f are Lipschitz-type continuous on H with the constants c1,c2 and d1,d2, respectively; that is, for all x,y,z∈H,(26)gx,z≤gx,y+gy,z+c1x−y2+c2y−z2,fx,z≤fx,y+fy,z+d1x−y2+d2y−z2.In this section, the solution set of the BEP (7) is denoted by Ω; that is, Ω=x∈Eg,C:fx¯,y≥0,∀y∈EPg,C, and assume that Ω≠∅.Now, we introduce the first algorithm for finding a pointx¯∈Ω.Algorithm 1: (Extragradient-like method without prior constants).
Initialization: Choose x0,y0,y−1∈C and the parameters β>0 and λ>0. Put n=0.Step 1. For given xn, solve the strongly convex problems: un=argminβgxn,y+1/2xn−y2:y∈C,tn=argminβgun,t+1/2xn−y2:t∈Cn,whereCn=v∈H:xn−βwn−un,v−un≤0withwn∈∂2gxn,un.Step 2. Solve the strongly convex problems: xn+1=argminλfyn,y+1/2xn−y2:y∈Hn,yn+1=argminλfyn,y+1/2xn+1−y2:y∈Tn,whereHn=z∈H:xn−λvn−yn,z−yn≤0withvn∈∂2fyn−1,yn,Tn=z∈H:z−tn≤z−xn.Step 3. If xn+1=yn=xn=un, then the algorithm stops, xn∈Ω; otherwise, set n=n+1 and return to Step 1.Remark 4.
By using the notation “prog” in Section2, un,tn,xn+1, and yn+1 may be rewritten as(27)un=progβgxn,⋅xn,tn=progβgun,⋅xn,xn+1=progλfyn,⋅xn,yn+1=progλfyn,⋅xn+1.
Note that sincefx,⋅ and gx,⋅ are convex and lower semicontinuous on H for each x∈H, for any given β>0, u∈H, and the closed convex subset D⊂H, from [27], Proposition 12.15, and Definition 12.23, it follows that both(28)argminβgu,y+12x−y2:y∈D,argminβfu,t+12x−t2:t∈D,are a singleton. Hence, un,tn,xn+1, and yn+1 in Algorithm 1 are obtained uniquely at each step.Remark 5.
From (A1)–(A4), it follows that (i)EPg,C and EPf,C are closed and convex; see [4]; (ii) gx,x=0 and fx,x=0 for all x∈C; see [28].
The following remark shows that the stop criterion in Step 3 is meaning.Remark 6.
Suppose thatxn+1=yn=xn=un for some n∈ℕ. By un=xn, the definition of un, and Lemma 3, we get(29)βgun,y−gxn,un=βgxn,y−gxn,xn≥0,∀y∈C,which with β>0 Remark 5 implies that xn∈EPg,C. Similarly, by xn+1=yn=xn, the definition of xn+1, and Lemma 3, we can prove that xn∈EPf,Hn. By the proof of Lemma 4, we see EPg,C⊂Hn for all n∈ℕ. So fxn,y≥0 for all y∈EPg,C. It follows that xn∈Ω.Lemma 5.
Assume thatβ∈0,min1/2c1,1/2c2. Then, C⊂Ck, EPg,C⊂Tn⊂Hn+1 for each n∈ℕ0.Proof.
We first show thatC⊂Ck for each n∈ℕ0. By Lemma 1 and the definition of uk, we have(30)0∈∂2βgxn,y+12xn−y2un+NCun.
Thus, forwn∈∂2gxn,un, there exists w¯n∈NCun such that(31)βwn+un−xn+w¯n=0.
So,(32)xn−un,y−un=βwn,y−un+w¯n,y−un,∀y∈C.
Sincew¯n∈NCun, we have w¯n,y−un≤0 for all y∈C. Hence, βwn,y−un≥xn−un,y−un for all y∈C, which implies that xn−βwn−un,y−un≤0 for all y∈C. This shows that C⊂Cn for each ℕ0.
Next, we show thatEPg,C⊂Tn for each n∈ℕ0. By Lemma 3 and the definition of tn in Remark 4, we have(33)βgun,y−gun,tn≥xn−tn,y−tn,∀y∈Cn,∀n∈ℕ0.
Note, we have proved thatC⊂Cn for each n∈ℕ0. So substituting any x′∈EPg,C⊂C into (33), we obtain(34)βgun,x′−gun,tn≥xn−tn,x′−tn,∀n∈ℕ0.
Sinceun∈C and g is pseudomonotone on H, we have gun,x′≤0. Then, (34) implies that(35)xn−tn,tn−x′≥βgun,tn,∀n∈ℕ0.
Now applying (A4) tog, we have(36)gun,tn≥gxn,tn−gxn,un−c1un−xn2−c2tn−un2,∀n∈ℕ0.
Combining (35) and (36), we get(37)xn−tn,tn−x′≥βgxn,tn−gxn,un−c1un−xn2−c2tn−un2,∀n∈ℕ0.
On the other hand, by the definition ofwn∈∂2gxn,un, we have(38)βgxn,y−gxn,un≥βwn,y−un,∀y∈H,∀n∈ℕ0.
Sincetn∈Cn, we have(39)xn−un,tn−un≤βwn,tn−un,which with (38) implies that(40)βgxn,tn−gxn,un≥xn−un,tn−un,∀n∈ℕ0.
From (37) and (40) and(41)2tn−xn,x′−tn=xn−x′2−tn−xn2−tn−x′2,it follows that(42)xn−x′2−tn−xn2−tn−x′2≥2xn−un,tn−un−2βc1xn−un2−2βc2un−tn2,∀n∈ℕ0.
Hence,(43)tn−x′2≤xn−x′2−tn−xn2−2xn−un,tn−un+2βc1xn−un2+c2un−tn2=xn−x′2−tn−un2−un−xn2+2βc1xn−un2+c2un−tn2=xn−x′2−1−2βc1xn−un2+1−2βc2un−tn2,∀n∈ℕ0.
In particular, from1−2βc1>0 and 1−2βc2>0, it follows that(44)tn−x′2≤xn−x′2,∀n∈ℕ0,which implies that x′∈Tn. Since x′∈EPg,C is arbitrary, it follows that EPg,C⊂Tn for each n∈ℕ0.
Finally, we prove thatTn⊂Hn+1 for each n∈ℕ0. By the definition of yn+1 in Remark 4 and Lemma 3, we have(45)0∈λ∂2fyn,yn+1+yn+1−xn+1+NTnyn+1,∀n∈ℕ0.
Thus, forvn∈∂2fyn−1,yn, there exists wn∈NTnyn+1 such that(46)λvn+yn+1−xn+1+wn=0,∀n∈ℕ0.
It follows that(47)xn+1−yn+1,y−yn+1=λvn,y−yn+1+wn,y−yn+1,∀y∈Tn,∀n∈ℕ0.
Sincewn∈NTnyn+1, we have wn,y−yn+1≤0 for all y∈Tn. Hence, λvn,y−yn+1≥xn+1−yn+1,y−yn+1 for all y∈Tn and n∈ℕ0, which with the definition of Hn+1 implies that Tn⊂Hn+1 for each n∈ℕ0. This completes the proof.Lemma 6.
Assume thatβ∈0,min1/2c1,1/2c2 and λ∈0,1/2d2+4d1. Let xn be the sequence generated by Algorithm 1. For all x∗∈Ω, the limit of x∗−xn2 exists, and(48)λfyn,y≥λxn−yn,xn+1−yn−c1yn−1−yn2−c2yn−xn+12+xn−xn+1,y−xn+1,∀y∈EPg,C,∀n∈ℕ.Proof.
Sincex∗−xn2, from the definition of Hn, it follows that(49)xn−λvn−yn,xn+1−yn≤0,∀n∈ℕ,that is,(50)λvn,xn+1−yn≥xn−yn,xn+1−yn,∀n∈ℕ.
Byvn∈∂2fyn−1,yn and the definition of subdifferential, we have(51)fyn−1,y−fyn−1,yn≥vn,y−yn,∀y∈H,∀n∈ℕ.
Replacingy in (51) with xn+1, we get(52)fyn−1,xn+1−fyn−1,yn≥vn,xn+1−yn,∀n∈ℕ.
Combining (50) and (52), we have(53)λfyn−1,xn+1−fyn−1,yn≥xn−yn,xn+1−yn,∀n∈ℕ.
By Lemma3 and the definition of xn+1, we have(54)λfyn,y−fyn,xn+1≥xn−xn+1,y−xn+1,∀y∈Hn,∀n∈ℕ.
Substitutingy=x∗∈Ω into (54), we obtain(55)λfyn,x∗−fyn,xn+1≥xn−xn+1,x∗−xn+1,∀n∈ℕ.
Note that (A1) implies thatfyn,x∗≤0, which with (55) leads to(56)λfyn,xn+1≤xn−xn+1,xn+1−x∗,∀n∈ℕ.
On the other hand, by the Lipschitz-type continuity off, we have(57)fyn,xn+1≥fyn−1,xn+1−fyn−1,yn−d1yn−yn−12−d2xn+1−yn2,∀n∈ℕ.
By (56) and (57), we obtain(58)xn−xn+1,xn+1−x∗≥λfyn−1,xn+1−fyn−1,yn−d1yn−yn−12−d2xn+1−yn2,which with (53) implies that(59)xn−xn+1,xn+1−x∗≥xn−yn,xn+1−yn−λd1yn−yn−12+d2xn+1−yn2=12yn−xn2+xn+1−yn2−xn+1−xn2−λd1yn−yn−12+d2xn+1−yn2,∀n∈ℕ.
Since(60)xn−xn+1,xn+1−x∗=12xn−x∗2−xn+1−xn2−xn+1−x∗2,by (59) we get(61)xn+1−x∗2≤xn−x∗22−yn−xn2−xn+1−yn2+2λd1yn−yn−12+2λd2xn+1−yn2≤xn−x∗22−yn−xn2−xn+1−yn2+2λd1yn−xn+xn−yn−12+2λd2xn+1−yn2≤xn−x∗22−yn−xn2−xn+1−yn2+4λd1yn−xn2+xn−yn−12+2λd2xn+1−yn2=xn−x∗22−1−4λd1yn−xn2−1−2λd2xn+1−yn2+4λd1xn−yn−12,∀n∈ℕ.
FixN∈ℕ. For all m∈ℕ with m>N, by (61) we have(62)x∗−xm+12≤x∗−xN2−1−4λd1+2λd2∑n=Nmxn+1−yn2−1−4λc1∑n=Nmyn−xn2+4λc1xN−yN−12.
Hence,(63)1−4λd1−2λd2∑n=Nmxn+1−yn2+1−4λd1∑n=Nmyn−xn2<x∗−xN2<∞,∀m>N,
which with4λd1+2λd2<1 leads to(64)∑n=1∞xn+1−yn2<∞,∑n=1∞yn−xn2<∞.
It follows that(65)limn⟶∞xn−yn2=0,limn⟶∞xn+1−yn2=0.
By (65) and the triangle inequality of norm, we obtain(66)xn−xn+1≤xn−yn+yn−xn+1⟶0,asn⟶∞,
(67)yn−yn+1≤yn−xn+xn−xn+1+xn+1−yn+1⟶0,asn⟶∞,
and(68)yn+1−xn≤yn+1−yn+yn−xn⟶0,asn⟶∞.
Note that (61) implies(69)xn+1−x∗2≤xn−x∗2+4λd1yn−1−xn2,∀n∈ℕ.
From (62) and (69) and Lemma 3, it follows that the limit of xn−x∗2 exists.
Finally, by (54), (56), and (52), we get(70)λfyn,y≥λfyn,xn+1+xn−xn+1,y−xn+1≥λfyn−1,xn+1−fyn−1,yn−d1yn−1−yn2−d2yn−xn+12+xn−xn+1,y−xn+1≥λxn−yn,xn+1−yn−d1yn−1−yn2−d2yn−xn+12+xn−xn+1,y−xn+1,∀y∈Hn,∀n∈ℕ.
Note that Lemma4 has shown that EPg,C⊂Tn⊂Hn+1 for each n∈ℕ0. So by (70), we have(71)λfyn,y≥λxn−yn,xn+1−yn−d1yn−1−yn2−d2yn−xn+12+xn−xn+1,y−xn+1,∀y∈EPg,C,∀n∈ℕ.
This completes the proof.Theorem 1.
If the parametersβ and λ satisfy the conditions:(72)β∈0,min12c1,12c2andλ∈0,12d2+4d1,then the sequence xn generated by Algorithm 1 converges weakly to the point x¯=limn⟶∞PΩxn.Proof.
Sinceyn+1∈Tn for each n∈ℕ0, by (66) we have(73)tn−yn+1≤yn+1−xn⟶0,asn⟶∞.
Furthermore, by (68) and (73), we get(74)tn−xn≤tn−yn+1+yn+1−xn⟶0,asn⟶∞.
From Lemma5, it follows that xn is bounded. This fact with (74) implies that tn is also bounded.
Takex′∈EPg,C and put M=supn∈ℕxn−x′+tn−x′. By (43) and (74), we have(75)1−2βc1xn−un2+1−2βc2un−tn2≤xn−x′2−tn−x′2≤xn−tnxn−x′+tn−x′≤Mxn−tn⟶0,asn⟶∞,
which with1−2βc1>0 and 1−2βc2>0 implies(76)xn−un2⟶0,un−tn2⟶0,asn⟶∞.
Sincexn is bounded, there exists a subsequence xnk of xn weakly converging to x¯∈H. By (73), we can conclude that unk also weakly converges to x¯. Since C is closed and un⊂C for all n∈ℕ, it follows that x¯∈C. We show that x¯∈EPg,C. In fact, by (33), (36), and (40), we get(77)βgunk,y≥βxnk−unk,tnk−unk−c1unk−xnk2−c2tnk−unk2+xnk−tnk,y−tnk,∀y∈C,∀k∈ℕ.
Lettingk⟶∞ in (77), by (74), (76), and (A2), we get(78)βgx¯,y≥limsupk⟶∞gunk,y≥0,∀y∈C,which with β>0 implies that x¯∈EPg,C.
Next, we prove thatx¯∈Ω. To end this, we need to show that(79)fx¯,y≥0,∀y∈EPg,C.
In fact, by (73), we have(80)λfynk,y≥λxnk−ynk,xnk+1−ynk−d1ynk−1−ynk2−d2ynk−xnk+12+xnk−xnk+1,y−xnk+1,∀y∈EPg,C,∀k∈ℕ0.
Lettingk⟶∞ in (80), by (65)–(67) and (A2), we have(81)λfx¯,y≥limsupk⟶∞fynk,y≥0,∀y∈EPg,C,
which withλ>0 implies that fx¯,y≥0 for all y∈EPg,C. So, x¯∈Ω.
Now, we prove that the whole sequencexn converges weakly to the point x¯. Indeed, assume that there exists a different subsequence xni of xn converging weakly to x† with x¯≠x†. By arguing similarly as above, it follows that x†∈Ω. Note that in the proof of Lemma 5, we have shown that the limits of xn−x† and xn−x¯ exist. So by Opial’s theorem [29], we have(82)limn⟶∞xn−x¯=liminfk⟶∞xnk−x¯<liminfk⟶∞xnk−x†=limn⟶∞xn−x†=liminfi⟶∞xni−x†<liminfi⟶∞xni−x¯=limn⟶∞xn−x¯.
It is a contradiction. Hence,x¯=x†. Therefore, the whole sequence xn converges weakly to the point x¯.
Finally, we provex¯=limn⟶∞PΩxn. Let wn=PΩxn for all n≥1. It is easy to see that wn is bounded from the boundedness of xn. We show that wn is a Cauchy sequence. By Lemma 1 and the definition of wn+1, we have(83)wn+1−xn+12≤wn−xn+12,∀n∈ℕ0.
Sincewn∈Ω, replacing x∗ in (69) with wn, we get(84)wn−xn+12≤xn−wn2+4λd1yn−1−xn2,∀n∈ℕ.
From (83) and (84), it follows that(85)wn+1−xn+12≤xn−wn2+4λd1yn−1−xn2,∀n∈ℕ.
From (64), (85), and Lemma 3, it follows that the limit of wn−xn2 exists. For all m,n∈ℕ with m>n, since wn∈Ω, by (69), we deduce(86)xm−wn2≤xm−1−wn2+4λd1ym−2−xm−12≤⋯≤xn−wn2+4λd1∑k=nm−1yk−1−xk2.
Fromwm=PΩxm and wn∈Ω, by Lemma 1 and (86), we have(87)wn−wm2≤wn−xm2−wm−xm2≤xn−wn2+4λd1∑k=nm−1yk−1−xk2−wm−xm2,∀m>n.
Sincelimn⟶∞xn−wn2 exists, letting m,n⟶∞ in (87), by (64), we get limn,m⟶∞wn−wm2=0. Consequently, wn is a Cauchy sequence. Since Ω is closed, wn converges strongly to some x′∈Ω. Now, we prove that x¯=x′. In fact, it follows from Lemma 1, wn=PΩxn and x¯∈Ω that x¯−wn,wn−xn≥0. Since wn⟶x′ and xn⇀x¯, we have x¯−x′,x′−x¯≥0. This shows that x¯=x′=limn⟶∞PΩxn. This completes the proof. □
In Algorithm 1,c1 and c2 need to be known as the input parameters. The following algorithm is a modification in which c1 and c2 do not need to be known.
Algorithm 2: (Extragradient-like method without prior constants).
Initialization: Choose x0,y−1,y0∈C, the parameters β0,λ0>0, and μ∈0,1/4. Put n=0.Step 1. For given xn, solve the strongly convex problems: un=argminβngxn,y+1/2xn−y2:y∈C,tn=argminβngun,t+1/2xn−y2:t∈Ck,whereCn=v∈H:xn−βnwn−un,v−un≤0withwn∈∂2gxn,un.Step 2. Solve the strongly convex problems: xn+1=argminλnfyn,y+1/2xn−y2:y∈Hn,yn+1=argminλn+1fyn,y+1/2xn+1−y2:y∈Tn,whereHn=z∈H:xn−λnvn−yn,z−yn≤0withvn∈∂2fyn−1,yn,Tn=z∈H:z−tn≤z−xn,λn+1=λn,fyn−1,xn+1−fyn−1,yn−fyn,xn+1≤0,minλn,μyn−yn−12+yn−xn+12/fyn−1,xn+1−fyn−1,yn−fyn,xn+1,otherwise.Step 3. Modify βn+1 by the following formula: βn+1=βn,gxn,tn−gxn,un−gun,tn≤0,minβn,μun−xn2+tn−un2/gxn,tn−gxn,un−gun,tn,otherwise.Step 4. If xn+1=yn+1=xn=yn, then the algorithm stops, xn∈Ω; otherwise, set n=n+1 and return to Step 1.Remark 7.
By (A4), we have(88)gxn,tn−gxn,un−gun,tn≤c1un−xn2+c2tn−un2≤cun−xn2+tn−un2,where c=maxc1,c2. If gxn,tn−gxn,un−gun,tn≤0, then(89)βn+1=minβn,μun−xn2+tn−un2gxn,tn−gxn,un−gun,tn≥minβn,μun−xn2+tn−un2cun−xn2+tn−un2=minβn,μc≥⋯≥minβ0,μc,
Note that from the definition ofβn+1, it follows that βn+1≥minβ0,μ/c still holds even if gxn,tn−gxn,un−gun,tn≤0. Since βn is nonincreasing and bounded from below by minβ0,μ/c, there exists β>0 such that(90)limn⟶∞βn=β.
Similarly, we can conclude that there existsλ>0 such that(91)limn⟶∞λn=λ>0.Theorem 2.
The sequencexn generated by Algorithm 2 converges weakly to the point x¯=limn⟶∞PΩxn.Proof.
Repeating the proof of (37) and (40), we can get, for all n∈ℕ,(92)λnfyn−1,xn+1−fyn−1,yn≥xn−yn,xn+1−yn,
and(93)λnfyn,xn+1≤xn−xn+1,xn+1−x∗.
By (92) and (93), we have(94)λnfyn−1,xn+1−fyn−1,yn−fyn,xn+1≥xn−yn,xn+1−yn−xn−xn+1,xn+1−x∗=12yn−xn2+xn+1−yn2−xn+1−xn2−xn−x∗2−xn+1−xn2−xn+1−x∗2,∀n∈ℕ.
By the definition ofλn+1, in the case when fyn−1,xn+1−fyn−1,yn−fyn,xn+1>0, we have(95)fyn−1,xn+1−fyn−1,yn−fyn,xn+1≤μyn−yn−12+yn−xn+12λn+1,∀n∈ℕ.
It is emphasized here that (95) still holds even if(96)fyn−1,xn+1−fyn−1,yn−fyn,xn+1≤0.
So, combining (94) with (95), we obtain(97)xn+1−x∗2≤xn−x∗2−xn−yn2+xn+1−yn2+2μλnλn+1yn−yn−12+yn−xn+12≤xn−x∗2−xn−yn2−1−2μλnλn+1xn+1−yn2+4μλnλn+1yn−xn2+xn−yn−12=xn−x∗2−1−4μλnλn+1xn−yn2−1−2μλnλn+1xn+1−yn2+4μλnλn+1xn−yn−12,∀n∈ℕ.
Sinceλn⟶λ>0, it follows that limn⟶∞4μλn/λn+1=4μ<1. Thus, for a fixed number ϵ∈4μ,1, there exists n0∈ℕ such that(98)4μλnλn+1<ϵ,∀n≥n0.
By (97) and (98), we have(99)xn+1−x∗2≤xn−x∗2−1−ϵxn−yn2−1−ϵ2xn+1−yn2+ϵxn−yn−12,∀n≥n0.
which is a similar result with (61).
On the other hand, for allx′∈EPg,C, repeating the proof of (35) and (38), we have(100)xn−un,tn−un+xn−tn,x′−tn≤βngxn,tn−gxn,un−gun,tn,∀n∈ℕ0.
By the definition ofβn+1, if gxn,tn−gxn,un−gun,tn>0, then(101)gxn,tn−gxn,un−gun,tn≤μun−xn2+tn−un2βn+1,∀n∈ℕ0.
Note that the definition ofβn+1 implies that (101) still holds even if gxn,tngxn,un−gun,tn≤0. So by (100) and (101), we obtain(102)xn−un,tn−un+xn−tn,x′−tn≤μβnun−xn2+tn−un2βn+1,∀n∈ℕ0.
Now, by (102) and 2tn−xn,tn−x′=xn−x′2−tn−xn2−tn−x′2, we have(103)tn−x′2≤xn−x′2−tn−xn2−2xn−un,tn−un+2μβnun−xn2+tn−un2βn+1=xn−x′2−tn−un2−un−xn2+2μβnun−xn2+tn−un2βn+1=xn−x′2−1−2μβnβn+1xn−un2+1−2μβnβn+1un−tn2,∀n∈ℕ0.
Sinceβn⟶β>0, it follows that limn⟶∞2μβn/βn+1=2μ<1. Thus, for a fixed number τ∈2μ,1, there exists m0∈ℕ such that(104)2μβnβn+1<τ,∀n≥m0.
By (103) and (104), we have(105)tn−x′2≤xn−x′2−1−τxn−un2+1−τun−tn2≤xn−x′2,∀n≥m0.
Finally, by arguing similarly to the proof of Lemma5 and Theorem 1, we can obtain the desired conclusion. This completes the proof.
As an application of the results above, we consider the following bilevel variational inequality problem (BVIP for short):(106)findx¯∈VIG,Csuch thatFx¯,y−x¯≥0,∀y∈VIG,C,where F and G be the mappings from H into itself. We denote the solution set of (106) by Γ, that is,(107)Γ=z∈VIG,C:Fz,y−z≥0,∀y∈VIG,C.Corollary 1.
LetH be a real Hilbert space and C be a nonempty closed and convex subset of H. Let F,G:H⟶H be the pseudomonotone and Lipschitz continuous mappings with the Lipschitz constants L1 and L2 satisfy the following conditions:(108)Blimsupn⟶∞Fxn,y−xn≤Fx^,y−x¯andlimsupn⟶∞Gxn,y−xn≤Gx^,y−x¯for every sequencexnconverging weakly tox^.
Assume thatΓ≠∅. Take the parameters β∈0,1/L1,λ∈0,1/3L2, the initial points x0,y0,y−1∈H and generate the sequence xn in the following manner:(109)un=PCxn−βGxn,tn=PCnxn−βGun,xn+1=PHnxn−λFyn,yn+1=PTnxn+1−λFyn,n≥0,where Cn=y∈H:xn−βGxn−un,y−un≤0, Hn=y∈H:xn−βFyn−1−yn,y−yn≤0, and Tn is defined as in Algorithm 1. Then, the sequence xn generated by (109) converges weakly to the point x¯=limn⟶∞PΓxn.Proof.
Letgx,y=Gx,y−x and fx,y=Fx,y−x for all x,y∈H. Since F is pseudomonotone on H, it follows that fx,y=Fx,y−x≥0⇒fy,x=Fy,x−y≤0. So f is pseudomonotone on H. It is obvious that f satisfies the condition (A3). In addition, if xn⇀x^, by (B), we have(110)limsupn⟶∞fxn,y=limsupn⟶∞Fxn,y−xn≤Fx^,y−x^=fx^,y.
Sof satisfies the condition (A2). Finally, since F is L1-Lipschitz continuous, f is Lipschitz-type continuous with the constant d1=d2=L1/2; see Remark 1. Thus, f satisfies the conditions (A1)–(A4). Similarly, g also satisfies the conditions (A1)–(A4). In particular, g satisfies (A4) with c1=c2=L2/2. So, the conditions on β and λ in Lemma 5 become the ones in Corollary 1. On the other hand, by Algorithm 1,(111)un=argminβgxn,y+12xn−y2:y∈Cis equivalent to un=PCxn−βGxn. Similarly, tn,xn+1, and yn+1 in Algorithm 1 are equivalent to tn,xn+1, and yn+1 in Corollary 1, respectively. By Theorem 1, the desired conclusion can be obtained. This completes the proof.
Since the proof process of the following corollary is similar to the one of Corollary 3.1, we give the following corollary and omit the proof process.Corollary 2.
LetH be a real Hilbert space and C be a nonempty closed and convex subset of H. Let F,G:H⟶H be the pseudomonotone and Lipschitz continuous mappings with the Lipschitz constants L1 and L2 satisfying the condition B in Corollary 3.1. Assume that Γ≠∅. The parameters β0>0,λ0>0, μ∈β0,1/4, the initial points x0,y0,y−1∈H are taken, and the sequence xn is generated by the following manner:(112)un=PCxn−βnGxn,tn=PCnxn−βnGun,xn+1=PHnxn−λnFyn,yn+1=PTnxn+1−λn+1Fyn,n≥0,where Cn,Hn, and Tn are defined as in Corollary 1,(113)λn+1=λn,Fyn−1−Fyn,xn+1−yn≤0,minλn,μyn−yn−12+yn−xn+12Fyn−1−Fyn,xn+1−yn,otherwise,and βn+1 is modified by(114)βn+1=βn,Gxn−Gun,tn−un≤0,minλn,μun−xn2+tn−un2Gxn−Gun,tn−un,otherwise.Then, the sequencexn generated by (112) converges weakly to the point x¯=limn⟶∞PΓxn.Remark 8.
SinceCn, Hn, and Tn are half-spaces, from Remark 2, it follows that tn, xn+1, and yn+1 in Corollary 1 and 2 can be computed explicitly.


## 4. Numerical Examples

In this section, we give two examples to illustrate the convergence of Algorithm 1 and 2. The programs are written in Matlab 2016b, and the examples are computed on a PC Intel(R) Core (TM) i5-4260U CPU, 2.00 GHz, Ram 4.00 GB.We first give the following example to illustrate the effectiveness of Algorithm 1 and 2.Example 1.
LetH=ℝm and C=x∈ℝm:x1≥0,xi≥1,∀i∈2,…,m. Let g:H×H⟶ℝ be defined by(115)gx,y=∑i=2myi−xix,∀x=x1,…,xm,y=y1,…,ym∈H.
It is known thatg satisfies the conditions (A1)–(A4). In particular, g is Lipschitz-type continuous with the constants c1=c2=2; see [30] for details. Let f:H×H⟶ℝ be defined by(116)fx,y=Ax,y−x,∀x,y∈H,where Ax=x1/2,x1−1/2,…,xm−1/2. It is easy to see that f satisfies the conditions (A1)–(A4). In particular, f is Lipschitz-type continuous with the constants d1=d2=1/4. The solution set of the bilevel equilibrium problem (7) in this example is found as Ω=0,1,…,1.
We choose the initial pointsx0,y0,y−1 randomly from the interval (0,5) for Algorithm 1 and 2, the input parameters λ=β=0.1 for Algorithm 1, and λ0=β0=μ=0.2 for Algorithm 2. The maximum iteration of 100 as the stop criterion is used for Algorithm 1 and 2. The numerical results with the different dimensions m are shown in Figure 1. In this figures, the x-axis represents the number of iterations while the y-axis is for the value of Dn generated by Algorithm 1 and 2, where(117)Dn=xn−0,1,…,1.
From the computed results, we see the effectiveness of Algorithm 1 and 2.
The next example was ever used in [20]. Here, we use this example to illustrate the convergence of Algorithm 1 and 2 and compare the computed results with Algorithm 2.1 in [20].Figure 1
Experiment in differentℝm.
(a)(b)(c)(d)Example 2.
LetC=x∈ℝ5:−1≤xi≤1,∀i=1,…,5 and f:ℝ5×ℝ5 be defined by(118)fx,y=Fx+Qy+q,y−x,∀x,y∈ℝ5,where Q=AAT+B+D with(119)A=−2101−1121020131201310201−13,B=0121−1−13202−2−211−3−10−1101−2302,D=5000003000001200000150000022,Fx=ξx1+ξx2+sinx1,−ξx1+ξx2+sinx2,ξ−1x3,ξ−1x4,ξ−1x5,and q is a vector in ℝ5.
Letf:ℝ5×ℝ5 be defined by(120)gx,y=Px+P¯y+p,y−x,∀x,y∈ℝ5,where p is a vector in ℝ5 and P=2P¯+I with(121)P¯=1200024000007010009000105.5.
It is known thatf and g satisfy all the conditions required in [20] and Section 3 of this paper. In particular, f is Lipschitz-type continuous with the constants d1=d2=1/222ξ2+2ξ+1+Q, where Q=58.9677 and g is Lipschitz-type continuous with the constants c1=c2=1/2P¯+I; see [20].
We choose the initial pointx0=y0=y−1=1,1,1,1,1 for Algorithm 1 and 2 and x0=1,0,0,1,1 for Algorithm 2.1 in [20]. The stop criterion is Dn≤10−3, where(122)Dn=maxxn−yn,xn+1−ynfor the three algorithms. The computed results are presented in Tables 1–3 for Algorithm 1, 2, and Algorithm 2.1 in [20], respectively. In Table 3, η=ξ−1−Q.
From the computed results, we see that Algorithm 2 needs more CPU times and iterations over Algorithm 1 and Algorithm 2.1 in [20]. The course may be that Algorithm 2 involves a self-adaptive process of computing the values of βn+1 and λn+1.Table 1
Computed results for Algorithm 3.1 with the different parameters.
Test prob.ξβλNo. iter.CPU-times (s)1651/3c11/7d181.534 52691/3c11/7d1171.711 33551/5c11/7d1222.023 44551/5c11/7d1131.743 15701/5c11/10d1151.711 36801/5c11/10d1241.988 57951/8c11/15d1352.233 18451/8c11/15d1211.993 591001/10c11/10d1192.100 3101501/10c11/10d1222.002 3Table 2
Computed results for Algorithm 3.2 with the different parameters.
Test prob.ξβ0λ0μNo. iterationCPU times (s)1651/3c11/7d10.2124.324 32691/3c11/7d10.2234.001 23551/5c11/7d10.15223.023 44551/5c11/7d10.15325.111 35701/5c11/10d10.1254.875 06801/5c11/10d10.1295.114 67951/8c11/15d10.1336.143 78451/8c11/15d10.12315.887 591001/10c11/10d10.09294.997 3101501/10c11/10d10.09315.880 3Table 3
Computed results for Algorithm 2.1 in [20] with the different parameters.
Test prob.ξβnλnNo. iterationCPU times (s)1652η/2d12n2+21/2c1+100n81.500 22692η/2d122n2+121/2c1+200n70.887 23552η/2d122n2+201/2c1+500n121.6874552η/2d122n2+151/2c1+600n131.400 35702η/2d122n2+201/2c1+1000n51.711 36802η/2d122n2+301/2c1+1000n51.422 27952η/2d12n2+1001/2c1+500n70.983 18452η/2d12n2+1501/2c1+500n90.800 591002η/2d12n2+2001/2c1+1000n70.965 9101502η/2d122n2+11/2c1+200n142.110 3


## 5. Conclusion

We have proposed two iterative algorithms for finding the solution of a bilevel equilibrium problem in a real Hilbert space. The sequence generated by our algorithms converges weakly to the solution. Furthermore, we reported some numerical results to support our algorithms. How to obtain the strong convergence of Algorithm 1 and 2 without the additional assumptions is our future investigation.



---

*Source: 2208280-2022-04-13.xml*