# On Penalty and Gap Function Methods for Bilevel Equilibrium Problems

Authors: Bui Van Dinh; Le Dung Muu
Journal: Journal of Applied Mathematics
 (2011)

---

## Abstract

We consider bilevel pseudomonotone equilibrium problems. We use a penalty function to convert a bilevel problem into one-level ones. We generalize a pseudo-∇-monotonicity concept from ∇-monotonicity and prove that under pseudo-∇-monotonicity property any stationary point of a regularized gap function is a solution of the penalized equilibrium problem. As an application, we discuss a special case that arises from the Tikhonov regularization method for pseudomonotone equilibrium problems.


---

## Body

## 1. Introduction

LetC be a nonempty closed-convex subset in ℝn, and let f,g:C×C→ℝ be two bifunctions satisfying f(x,x)=g(x,x)=0 for every x∈C. Such a bifunction is called an equilibrium bifunction. We consider the following bilevel equilibrium problem (BEP for short):(1.1)findx¯∈Sgsuchthatf(x¯,y)≥0,∀y∈Sg,
where Sg={u∈C:g(u,y)≥0,∀y∈C}, that is, Sg is the solution set of the equilibrium problems(1.2)findu∈Csuchthatg(u,y)≥0,∀y∈C.
As usual, we call problem (1.1) the upper problem and (1.2) the lower one. BEPs are special cases of mathematical programs with equilibrium constraints. Sources for such problems can be found in [1–3]. Bilevel monotone variational inequality, which is a special case of problem (1.1), was considered in [4, 5]. Moudafi in [6] suggested the use of the proximal point method for monotone BEPs. Recently, Ding in [7] used the auxiliary problem principle to BEPs. In both papers, the bifunctions f and g are required to be monotone on C. It should be noticed that under the pseudomonotonicity assumption on g the solution-set Sg of the lower problem (1.2) is a closed-convex set whenever g(x,·) is lower semicontinuous and convex on C for each x. However, the main difficulty is that, even the constrained set Sg is convex, it is not given explicitly as in a standard mathematical programming problem, and therefore the available methods (see, e.g., [8–14] and the references therein) cannot be applied directly.In this paper, first, we propose a penalty function method for problem (1.1). Next, we use a regularized gap function for solving the penalized problems. Under certain pseudo-∇-monotonicity properties of the regularized bifunction, we show that any stationary point of the gap function on the convex set C is a solution to the penalized subproblem. Finally, we apply the proposed method to the Tikhonov regularization method for pseudomonotone equilibrium problems.


## 2. A Penalty Function Method

Penalty function method is a fundamental tool widely used in optimization to convert a constrained problem into unconstrained (or easier constrained) ones. This method was used to monotone variational inequalities in [5] and equilibrium problems in [15]. In this section, we use the penalty function method in the bilevel problem (1.1). First, let us recall some well-known concepts on monotonicity and continuity (see, e.g., [16]) that will be used in the sequel.Definition 2.1.
The bifunctionϕ:C×C→ℝ is said to be as follows:(a)
strongly monotone onC with modulus β>0 if
(2.1)ϕ(x,y)+ϕ(y,x)≤-β‖x-y‖2,∀x,y∈C,(b)
monotone onC if
(2.2)ϕ(x,y)+ϕ(y,x)≤0,∀x,y∈C,(c)
pseudomonotone onC if
(2.3)∀x,y∈C:ϕ(x,y)≥0⟹ϕ(y,x)≤0,(d)
upper semicontinuous atx with respect to the first argument on C if
(2.4)lim⁡z→x̅ϕ(z,y)≤ϕ(x,y),∀y∈C,(e)
lower semicontinuous aty with respect to the second argument on C if
(2.5)lim⁡w→y̅⁡ϕ(x,w)≥ϕ(x,y),∀x∈C.Clearly, (a)⇒(b)⇒(c).Definition 2.2 (see [17]).
The bifunctionϕ:C×C→ℝ is said to be coercive on C if there exists a compact subset B⊂ℝn and a vector y0∈B∩C such that
(2.6)ϕ(x,y0)<0,∀x∈C∖B.Theorem 2.3 (see [18, Proposition 2.1.14]).
Letϕ:C×C→ℝ be a equilibrium bifunction such that  ϕ(·,y) is upper semicontinuous on  C for each  y∈C and  ϕ(x,·) is lower semicontnous, convex on  C for each  x∈C. Suppose that  C is compact or  ϕ is coercive on  C, then there exists at least one  x*∈C such that  ϕ(x*,y)≥0 for every  y∈C.The following proposition tells us about a relationship between the coercivity and the strong monotonicity.Proposition 2.4.
Suppose that the equilibrium bifunctionϕ is strongly monotone on C, and ϕ(x,·) is convex, lower semicontinuous with respect to the second argument for all x∈C, then for each y∈C, there exists a compact set B such that y∈B and ϕ(x,y)<0forallx∈C∖B.Proof.
Suppose by contradiction that the conclusion does not hold, then there exists an elementy0∈C such that for every compact set B there is an element xB∈C∖B such that ϕ(xB,y0)≥0. Take B:=Br as the closed ball centered at y0 with radius r>1. Then there exists xr∈C∖Br such that ϕ(xr,y0)≥0. Let x be the intersection of the line segment [y0,xr] with the unit sphere S(y0;1) centered at y0 and radius 1. Hence, xr=y0+t(r)(x-y0), where t(r)>r. By the strong monotonicity of ϕ, we have
(2.7)ϕ(y0,xr)≤-ϕ(xr,y0)-β‖xr-y0‖2≤-ϕ(xr,y0)-βt(r)2‖x-y0‖2.
Since ϕ(y0,·) is convex on C, it follows that
(2.8)ϕ(y0,x)≤1t(r)ϕ(y0,xr)+t(r)-1t(r)ϕ(y0,y0),
which implies that ϕ(y0,x)≤-βt(r)∥x-y0∥2≤-βr. Thus,
(2.9)ϕ(y0,x)⟶-∞asr⟶∞.
However, since ϕ(y0,·) is lower semicontinuous on C, by the well-known Weierstrass Theorem, ϕ(y0,·) attains its minimum on the compact set S(y0;1)∩C. This fact contradicts (2.9).From this proposition, we can derive the following corollaries.Corollary 2.5 (see [18]).
If the bifunctionϕ is strongly monotone on C, and ϕ(x,·) is convex, lower semicontinuous with respect to the second argument for all x∈C, then ϕ is coercive on C.Corollary 2.6.
Suppose that the bifunctionf is strongly monotone on C, and f(x,·) is convex, lower semicontinuous with respect to the second argument for all x∈C. If the bifunction g is coercive on C then, for every ϵ>0, the bifunction g+ϵf is uniformly coercive on C, for example, there exists a point y0∈C and a compact set B both independent of ϵ such that
(2.10)g(x,y0)+ϵf(x,y0)<0,∀x∈C∖B.Proof.
From the coercivity ofg, we conclude that there exists a compact B1 and y0∈C such that g(x,y0)<0forallx∈C∖B1. Since f is strongly monotone, convex, lower semicontinuous on C, by choosing y=y0, from Proposition 2.4, there exists a compact B2 such that f(x,y0)<0forallx∈C∖B2. Set B=B1∪B2, then B is compact and g(x,y0)+ϵf(x,y0)<0forallx∈C∖B.Remark 2.7.
It is worth to note that if bothf, g are coercive and pseudomonotone on C, then the function f+g is not necessary coercive or pseudomonotone on C.To see this, let us consider the following bifunctions.Example 2.8.
Letf(x,y):=(x1y2-x2y1)ex1,g(x,y):=(x2y1-x1y2)ex2, and C={(x1,x2):x1≥-1,(1/10)(x1-9)≤x2≤10x1+9} then we have(i)
f(x,y),g(x,y) are pseudomonotone and coercive on C,(ii)
for allϵ>0 the bifunctions fϵ(x,y)=g(x,y)+ϵf(x,y) are neither pseudomonotone nor coercive on C.
Indeed,(i)
iff(x,y)≤0, then f(y,x)≥0, thus f is pseudomonotone on C. By choosing y0=(y10,0),(0<y10≤1) and B={(x1,x2):x12+x22≤r}(r>1), we have f(x,y0)=-x2y10ex1<0forally∈C∖B, which means that f is coercive on C. Similarly, we can see that g is coercive on C,(ii)
by definition off, we have that(2.11)fϵ(x,y)=(x2y1-x1y2)(ex2-ϵex1),∀ϵ>0.Take x(t)=(t,2t),forally(t)=(2t,t), then fϵ(x(t),y(t))=3t2(e2t-ϵet)>0, whereas fϵ(y(t),x(t))=-3t2(et-ϵe2t)>0 for t is sufficiently large. So fϵ is not pseudomonotone on C.
Now, we show that the bifunctionfϵ(x,y)=(x2y1-x1y2)(ex2-ϵex1) is not coercive on C. Suppose, by contradiction, that there exist a compact set B and y0=(y10,y20)∈B∩C such that fϵ(x,y0)<0forallx∈C∖B, then, by coercivity of fϵ, it follows, y10,y20>0 and y10≠y02. With x(t)=(t,kt),(t>0), we have fϵ(x(t),y0)=t(ky10-y20)(ekt-ϵet). However(i)
ify10>y20, then from 1<k<10 it follows that x(t)∈C and fϵ(x(t),y0)>0 for t is sufficiently large, which contradicts with coercivity,(ii)
ify10<y20, then, by choosing 1/10<k<1, we obtain x(t)∈C and fϵ(x(t),y0)>0 for t is large enough. But this cannot happen because of the coercivity of fϵ.
Now, for each fixedϵ>0, we consider the penalized equilibrium problem PEP(C,fϵ) defined as
(2.12)findx¯ϵ∈Csuchthatfϵ(x¯ϵ,y):=g(x¯ϵ,y)+ϵf(x¯ϵ,y)≥0,∀y∈C.
By SOL(C,fϵ), we denote the solution set of PEP(C,fϵ).Theorem 2.9.
Suppose that the equilibrium bifunctionsf,g are pseudomonotone, upper semicontinuous with respect to the first argument and lower semicontinuous, convex with respect to the second argument on  C, then any cluster point of the sequence  {xk} with  xk∈SOL(C,fϵk),ϵk→0 is a solution to the original bilevel problem (1.1). In addition, if  f is strongly monotone and  g is coercive on  C, then for each  ϵk>0 the penalized problem  PEP(C,fϵk) is solvable, and any sequence  {xk} with  xk∈SOL(C,fϵk) converges to the unique solution of the bilevel problem (1.1) as  k→∞.Proof.
Let{xk} be any sequence with xk∈SOL(C,fϵk),  and let x¯ be any of its cluster points. Without lost of generality, we may assume that xk→x¯ask→∞. Since xk∈SOL(C,fϵk), one has
(2.13)g(xk,y)+ϵkf(xk,y)≥0,∀y∈C.
For any z∈Sg, we have g(z,y)≥0,forally∈C and in particular, g(z,xk)≥0. Then, by the pseudomonotonicity of g, we have g(xk,z)≤0. Replacing y by z in (2.13), we obtain
(2.14)g(xk,z)+ϵkf(xk,z)≥0,
which implies that
(2.15)ϵkf(xk,z)≥-g(xk,z)≥0⟹f(xk,z)≥0.
Let k→∞, by upper semicontinuity of f, we have f(x¯,z)≥0forallz∈Sg.
To complete the proof, we need only to show thatx¯∈Sg. Indeed, for any y∈C, we have
(2.16)g(xk,y)+ϵkf(xk,y)≥0,∀y∈C.
Again, by upper semicontinuity of f and g, we obtain in the limit, as ϵk→0, that g(x¯,y)≥0forally∈C. Hence, x¯∈Sg.
Now suppose, in addition, thatf is strongly monotone on C. By Corollary 2.6, fϵk is uniformly coercive on C. Thus, problem PEP(C,fϵk) is solvable and, for all ϵk>0, the solution sets of these problems are contained in a compact set B. So any infinite sequence {xk}  of the solutions has a cluster point, say, x¯. By the first part, x¯ is a solution of (1.1). Note that, from the assumption on g, the solution set Sg of the lower equilibrium (EP(C,g)) is a closed, convex, compact set. Since f is lower semicontinuous and convex with respect to the second argument and is strongly monotone on C, the upper equilibrium problem EP(Sg,f) has a unique solution. Using again the first part of the theorem, we can see that xk→x¯ask→∞Remark 2.10.
In a special case considered in [6], where both f and g are monotone, the penalized problem (PEP) is monotone too. In this case, (PEP) can be solved by some existing methods (see, e.g., [6, 11–14, 19]) and the references therein. However, when one of these two bifunctions is pseudomonotone, the penalized problem (PEP), in general, does not inherit any monotonicity property from f and g. In this case, problem (PEP) cannot be solved by the above-mentioned existing methods.


## 3. Gap Function and Descent Direction

A well-known tool for solving equilibrium problem is the gap function. The regularized gap function has been introduced by Taji and Fukushima in [20] for variational inequalities, and extended by Mastroeni in [11] to equilibrium problems. In this section, we use the regularized gap function for the penalized equilibrium problem (PEP). As we have mentioned above, this problem, even when g is pseudomonotone and f is strongly monotone, is still difficult to solve.Throughout this section, we suppose that bothf and g are lower semicontinuous, convex on C with respect to the second argument. First, we recall (see, e.g., [11]) the definition of a gap function for the equilibrium problem.Definition 3.1.
A functionφ:C→ℝ∪{+∞} is said to be a gap function for (PEP) if(i)
φ(x)≥0,forallx∈C,(ii)
φ(x¯)=0 if and only if  x¯ is a solution for (PEP).A gap function for (PEP) isφ(x)=-miny∈Cfϵ(x,y). This gap function may not be finite and, in general, is not differentiable. To obtain a finite, differentiable gap function, we use the regularized gap function introduced in [20] and recently used by Mastroeni in [11] to equilibrium problems. From Proposition 2.2 and Theorem 2.1 in [11], the following proposition is immediate.Proposition 3.2.
Suppose thatl:C×C→ℝ is a nonnegative differentiable, strongly convex bifunction on C with respect to the second argument and satisfies(a)
l(x,x)=0forallx∈C,(b)
∇yl(x,x)=0forallx∈C.
Then the function(3.1)φϵ(x)=-min⁡y∈C[g(x,y)+ϵ[f(x,y)+l(x,y)]]
is a finite gap function for (PEP). In addition, if f and g are differentiable with respect to the first argument and ∇xf(x,y),∇xg(x,y) are continuous on C, then φϵ(x) is continuously differentiable on C and
(3.2)∇φϵ(x)=-∇xg(x,yϵ(x))-ϵ∇x[f(x,yϵ(x))+l(x,yϵ(x))]=-∇xgϵ(x,yϵ(x)),
where
(3.3)gϵ(x,y)=g(x,y)+ϵ[f(x,y)+l(x,y)],yϵ(x)=argmin⁡y∈C{gϵ(x,y)}.Note that the functionl(x,y):=(1/2)〈M(y-x),y-x〉, where M is a symmetric positive definite matrix of order n that satisfies the assumptions on l.We need some definitions on∇-monotonicity.Definition 3.3.
A differentiable bifunctionh:C×C→ℝ is called as follows:(a)
strongly∇-monotone on C if there exists a constant τ>0 such that,
(3.4)〈∇xh(x,y)+∇yh(x,y),y-x〉≥τ‖y-x‖2,∀x,y∈C,(b)
strictly∇-monotone on C if
(3.5)〈∇xh(x,y)+∇yh(x,y),y-x〉>0,∀x,y∈C,x≠y,(c)
∇-monotone on C if
(3.6)〈∇xh(x,y)+∇yh(x,y),y-x〉≥0,∀x,y∈C,(d)
strictly  pseudo-∇-monotone on C if
(3.7)〈∇xh(x,y),y-x〉≤0⟹〈∇yh(x,y),y-x〉>0,∀x,y∈C,x≠y,(e)
pseudo-∇-monotone on C if
(3.8)〈∇xh(x,y),y-x〉≤0⟹〈∇yh(x,y),y-x〉≥0,∀x,y∈C.Remark 3.4.
The definitions (a), (b), and (c) can be found, for example, in [8, 11]. The definitions (d) and (e), to our best knowledge, are not used before. From the definitions, we have
(3.9)(a)⟹(b)⟹(c)⟹(e),(a)⟹(b)⟹(d)⟹(e).
However, (c) may not imply (d) and vice versa as shown by the following simple examples.Example 3.5.
Consider the bifunctionh(x,y)=ex2(y2-x2) defined on C×CwithC=ℝ. This bifunction is not ∇-monotone on C, because
(3.10)〈∇xh(x,y)+∇yh(x,y),y-x〉=2ex2(y-x)2(x2+xy+1)
is negative for x=-1,y=3. However, h(x,y) is strictly pseudo-∇-monotone. Indeed, we have
(3.11)〈∇xh(x,y),y-x〉=2xex2(y2-x2-1)(y-x)≤0⟺x(y2-x2-1)(y-x)≤0,〈∇yh(x,y),y-x〉=2yex2(y-x)>0⟺y(y-x)>0.
It is not difficult to verify that
(3.12)x(y2-x2-1)(y-x)≤0⟹y(y-x)>0,asx≠y.
Hence this function is strictly pseudo-∇-monotone but is not ∇-monotone.
Vice versa, considering the bifunctionh(x,y)=(y-x)TM(y-x) defined on ℝn×ℝn, where M is a matrix of order n×n, we have the following:(i)
h is ∇-monotone, because
(3.13)〈∇xh(x,y)+∇yh(x,y),y-x〉=〈-(y-x)T(M+MT)+(y-x)T(M+MT),y-x〉=0,∀x,y.
Clearly, h is not strictly-∇-monotone,(ii)
h is strictly pseudo ∇-monotone if and only if
(3.14)〈∇xh(x,y),y-x〉=-〈(y-x)T(M+MT),y-x〉≤0
implies(3.15)〈∇yh(x,y),y-x〉=(y-x)T(M+MT),y-x〉>0,∀x,y,x≠y.
The latter inequality equivalent to M+MT is a positive definite matrix of order n×n.Remark 3.6.
As shown in [8] when h(x,y)=〈T(x),y-x〉 with T a differentiable monotone operator on C, h is monotone on C if and only if T is monotone on C, and in this case, monotonicity of h on C coincides with ∇-monotonicity of h on C.The following example shows that pseudomonotonicity may not imply pseudo-∇-monotonicity.Example 3.7.
Leth(x,y)=-ax(y-x), defined on ℝ+×ℝ+, (a>0). It is easy to see that
(3.16)h(x,y)≥0⟹h(y,x)≤0,∀x,y≥0.
Thus, h is pseudomonotone on ℝ+.
We have(3.17)〈∇xh(x,y),y-x〉=-a(y-x)(y-2x)<0,∀y>2x>0.
But(3.18)〈∇yh(x,y),y-x〉=-ax(y-x)<0,∀y>2x>0.
Soh is not pseudo-∇-monotone on ℝ+.From the definition of the gap functionφϵ, a global minimal point of this function over C is a solution to problem (PEP). Since φϵ is not convex, its global minimum is extremely difficult to compute. In [8], the authors have shown that under the strict ∇-monotonicity a stationary point is also a global minimum of gap function. By a counterexample, the authors in [8] also pointed out that the strict ∇-monotonicity assumption cannot be relaxed to ∇-monotonicity. The following theorem shows that the stationary property is still guaranteed under the strict pseudo-∇-monotonicity.Theorem 3.8.
Suppose thatgϵ is strictly pseudo- ∇-monotone on  C. If  x¯ is a stationary point of  φϵ over  C, that is,
(3.19)〈∇φϵ(x¯),y-x¯〉≥0,∀y∈C.
then x¯ solves (PEP).Proof.
Suppose thatx¯ does not solve (PEP), then yϵ(x¯)≠x¯.
Sincex¯ is a stationary point of φϵ on C, from the definition of φϵ, we have
(3.20)〈∇φϵ(x¯),y-x¯〉=-〈∇xgϵ(x,yϵ(x)),yϵ(x)-x〉≥0.
By strict pseudo-∇-monotonicity of gϵ, it follows that
(3.21)〈∇ygϵ(x¯,yϵ(x¯)),yϵ(x¯)-x¯〉>0.
On the other hand, since yϵ(x¯) minimizes gϵ(x,·) over C, we have
(3.22)〈∇ygϵ(x¯,yϵ(x¯)),yϵ(x¯)-x¯〉≤0,
which is in contradiction with (3.21).To compute a stationary point of a differentiable function over a closed-convex set, we can use the existing descent direction algorithms in mathematical programming (see, e.g., [8, 21]). The next proposition shows that if y(x) is a solution of the problem miny∈Cgϵ(x,y), then y(x)-x is a descent direction on C of φϵ at x. Namely, we have the following proposition.Proposition 3.9.
Suppose thatgϵ is strictly pseudo-∇-monotone on C and x is not a solution to Problem (PEP), then
(3.23)〈∇φϵ(x),yϵ(x)-x〉<0.Proof.
Letdϵ(x)=yϵ(x)-x. Since x is not a solution to (PEP), then dϵ(x)≠0. Suppose that, by contradiction, dϵ(x) is not a descent direction on C of φϵ at x, then
(3.24)〈∇φϵ(x),yϵ(x)-x〉≥0⟺-〈∇xgϵ(x,yϵ(x)),yϵ(x)-x〉≥0,
which, by strict pseudo-∇-monotonicity of gϵ, implies
(3.25)〈∇ygϵ(x,yϵ(x)),yϵ(x)-x〉>0.
On the other hand, since yϵ(x) minimizes gϵ(x,·) over C, by the well-known optimality condition, we have
(3.26)〈∇ygϵ(x,yϵ(x)),yϵ(x)-x〉≤0,
which contradicts (3.25).Proposition 3.10.
Suppose thatg(x,·) is strictly convex on C for every x∈C and g is strictly pseudo-∇-monotone on C. If x∈C is not a solution of (PEP), then there exists ϵ¯>0 such that yϵ(x)-x is a descent direction of φϵ on C at x for all 0<ϵ≤ϵ¯.Proof.
By contradiction, suppose that the statement of the proposition does not hold, then there existϵk↘0 and x∈C such that
(3.27)〈∇φϵk(x),yϵk(x)-x〉≥0⟺-〈∇xgϵk(x,yϵk(x)),yϵk(x)-x〉≥0.
Since gϵ(x,·) is strictly convex differentiable on C, by Theorem 2.1 in [9], the function ϵ↦yϵ(x) is continuous with respect to ϵ, thus yϵk(x) tends to y0(x) as ϵk→0, where y0(x)=argminy∈Cg(x,y). Since gϵk(x,y)=g(x,y)+ϵkf(x,y) is continuously differentiable, letting ϵk→0 in (3.27), we obtain
(3.28)-〈∇xg(x,y0(x)),y0(x)-x〉≥0.
By strict pseudo-∇-monotonicity of g, it follows that
(3.29)〈∇yg(x,y0(x)),y0(x)-x〉>0.
On the other hand, since yϵk(x) minimizes gϵk(x,·) over C, we have
(3.30)〈∇ygϵk(x,yϵk(x)),yϵk(x)-x〉≤0.
Taking the limit, we obtain
(3.31)〈∇yg(x,y0(x)),y0(x)-x〉≤0,
which contradicts (3.29).To illustrate Theorem3.8, let us consider the following examples.Example 3.11.
Consider the bifunctionsg(x,y)=ex2(y2-x2) and f(x,y)=10x2(y2-x2) defined on ℝ×ℝ. It is not hard to verify that,(i)
g(x,y),f(x,y) are monotone, strictly pseudo-∇-monotone on ℝ,(ii)
for allϵ>0 the bifunction g(x,y)+ϵf(x,y) is monotone and strictly pseudo-∇-monotone on ℝ and satisfying all of the assumptions of Theorem 3.8.Example 3.12.
Letf(x,y)=-x2-xy+2y2 and g(x,y)=-3x2y+xy2+2y3 defined on ℝ+×ℝ+ it is easy to see that,(i)
g,f are pseudomonotone, strictly ∇-monotone on ℝ+,(ii)
for allϵ>0 the bifunction g(x,y)+ϵf(x,y) is pseudomonotone and strictly ∇-monotosne on ℝ+ and satisfying all of the assumptions of Theorem 3.8.


## 4. Application to the Tikhonov Regularization Method

The Tikhonov method [22] is commonly used for handling ill-posed problems. Recently, in [23] the Tikhonov method has been extended to the pseudomonotone equilibrium problem (EP⁡(C,g))Findx*∈Csuchthatg(x*,y)≥0,∀y∈C,
where, as before, C is a closed-convex set in ℝn and g:C→ℝ is a pseudomonotone bifunction satisfying g(x,x)=0 for every x∈C.In the Tikhonov regularization method considered in [23], problem (EP(C,g)) is regularized by the problems (EP⁡(C,gϵ))findx*∈Csuchthatgϵ(x*,y):=g(x*,y)+ϵf(x*,y)≥0,∀y∈C,
where f is an equilibrium bifunction on C and ϵ>0 and play the role of the regularization bifunction and regularization parameter, respectively.In [23], the following theorem has been proved.Theorem 4.1.
Suppose thatf(·,y),g(·,y) are upper semicontinuous and  f(x,·),g(x,·) are lower semicontinuous convex on  C for each  x,y∈C and that  g is pseudomonotone on  C. Suppose further that  f is strongly monotone on  C satisfying the condition
(4.1)∃δ>0:|f(x,y)|≤δ‖x-xg‖‖y-x‖,∀x,y∈C,
where xg∈C (plays the role of a guess solution) is given.
Then the following three statements are equivalent:(a)
the solution set of (EP(C,gϵ)) is nonempty for each ɛ>0 and limɛ→0+x(ɛ) exists, where x(ɛ) is arbitrarily chosen in the solution set of (EP(C,gϵ)),(b)
the solution set of (EP(C,gϵ)) is nonempty for each ɛ>0 and limɛ→0+sup∥x(ɛ)∥<∞, where x(ɛ) is arbitrarily chosen in the solution set of (EP(C,gϵ)),(c)
the solution set of (EP(C,g)) is nonempty.
Moreover, if any one of these statements holds, thenlimɛ→0+x(ɛ) is equal to the unique solution of the strongly monotone equilibrium problem EP(Sg,f), where Sg denotes the solution set of the original problem (EP(C,g)).Note that, wheng is monotone on C, the regularized subproblems are strongly monotone and therefore, they can be solved by some existing methods. When g is pseudomonotone, the subproblems, in general, are no longer strongly monotone, even not pseudomonotone. So solving them becomes a difficult task. However, the problem of finding the limit point of the sequences of iterates leads to the unique solution of problem EP(Sg,f).In order to apply the penalty and gap function methods described in the preceding sections, let us take, for instant,(4.2)f(x,y)=〈x-xg,y-x〉.
Clearly, f is both strongly monotone and strongly ∇-monotone with the same modulus 1. Moreover, f satisfies the condition (4.1). Therefore, the problem of finding the limit point in the above Tikhonov regularization method can be formulated as the bilevel equilibrium problem(4.3)findx∈Sgsuchthatf(x*,y)≥0,∀y∈Sg,
which is of the form (1.1). Now, for each fixed ϵk>0, we consider the penalized equilibrium problem PEP(C,fϵk) defined as(4.4)findx¯k∈Csuchthatfϵk(x¯k,y):=g(x¯k,y)+ϵkf(x¯k,y)≥0,∀y∈C.
As before, by SOL(C,fϵk), we denote the solution set of PEP(C,fϵk).Applying Theorems2.9 and 3.8, we obtain the following result.Theorem 4.2.
Suppose that the bifunctiong satisfies the following conditions:(i)
g(x,·) is convex, lower semicontinuous for all x∈C,(ii)
g is pseudomonotone and coercive on C. Then for any ϵk>0, the penalized problem PEP(C,fϵk) is solvable, and any sequence {xk} with xk∈SOL(C,fϵk) for all k converges to the unique solution of the problem (4.3) as k→∞.(iii)
In addition, ifg(x,y)+ϵkf(x,y) is strictly pseudo- ∇-monotone onC (in particular,g(x,y) is∇-monotone), andx¯k is any stationary point of the mathematical programminx∈Cφk(x) with
(4.5)φk(x):=min⁡y∈C{g(x,y)+ϵkf(x,y)},
then{x¯k} converges to the unique solution of the problem (4.3) ask→∞.


## 5. Conclusion

We have considered a class of bilevel pseudomonotone equilibrium problems. The main difficulty of this problem is that its feasible domain is not given explicitly as in a standard mathematical programming problem. We have proposed a penalty function method to convert the bilevel problem into one-level ones. Then we have applied the regularized gap function method to solve the penalized equilibrium subproblems. We have generalized the pseudo-∇-monotonicity concept from ∇-monotonicity. Under the pseudo-∇-monotonicity property, we have proved that any stationary point of the gap function is a solution to the original bilevel problem. As an application, we have shown how to apply the proposed method to the Tikhonov regularization method for pseudomonotone equilibrium problems.



---

*Source: 646452-2011-11-03.xml*