Lobachevskii Journal of Mathematics Vol. 13, 2003, 57 – 65

©Igor V. Konnov, Olga V. Pinyagina

Igor V. Konnov, Olga V. Pinyagina
D-GAP FUNCTIONS AND DESCENT METHODS FOR A CLASS OF MONOTONE EQUILIBRIUM PROBLEMS
(submitted by A. V. Lapin)

________________

This work is supported by RFBR (Grant 03-01-96012) and by the Academy of Sciences of Finland (Grant 77796).

ABSTRACT. We consider a general class of monotone equilibrium problems, which involve nonsmooth convex functions, in a real Banach space. We combine the D-gap function approach and regularization techniques and suggest a descent type algorithm to find solutions to the initial problem.

1. Introduction

Let U be a nonempty closed and convex subset of a real reflexive Banach space E, ψ : E × E → R an equilibrium bifunction, i.e. ψ(u,u) = 0 for every u ∈ U. In addition, we assume that ψ(u,⋅) is convex and lower semicontinuous for each u ∈ E.

We consider equilibrium problem (EP for short) of the form: Find a point u∗ ∈ U such that

ψ(u∗,v) ≥ 0∀v ∈ U. (1)

It is well known that equilibrium problems represent rather general and suitable format for the formulation and investigation of various complex problems arising in Economics, Mathematical Physics, Transportation, Operations Research and other fields. Moreover, they are closely related to other general problems of Nonlinear Analysis such as fixed point, optimization, complementarity and variational inequality ones. For this reason, various aspects of EPs were investigated by many researchers (see e.g. [1]–[4] and references therein).

One of the most popular approaches to solve various problems of Nonlinear Analysis is to convert them into a suitable optimization problem with the help of so-called gap functions. In particular, in [5] this approach was applied for smooth EPs in a Banach space setting, in [6],[7] we applied this approach to the problem (1) involving a non-smooth function, and we presented descent methods, converging strongly to a solution. However, these methods need additional strong monotonicity properties to ensure convergence. In [8], it was suggested to combine the descent methods with regularization technics for solving monotone variational inequalities. In this paper, combining so the descent and regularization techniques, we will construct a converging method for EPs in a common monotone case.

2. Regularization of equilibrium problems

First, we recall several well-known properties of EPs; see e.g. [1]–[3].

The equilibrium bifunction ψ is said to be

(i) monotone, if, for all u,v ∈ E, we have

ψ(u,v) + ψ(v,u) ≤ 0;

(ii) strictly monotone, if, for all u,v ∈ E,u ⁄= v, we have

ψ(u,v) + ψ(v,u) < 0;

(iii) strongly monotone with constant τ, if, for all u,v ∈ E, we have

ψ(u,v) + ψ(v,u) ≤−τ∥u − v∥2.

Proposition 2.1. (i) If ψ(⋅,v) is hemicontinuous for each u ∈ U and ψ is monotone, then the solutions set of EP(1) coincides with that of the dual problem

v∗ ∈ U : ψ(u,v∗) ≤ 0∀u ∈ U (2)

and it is convex and closed.

(ii) If ψ is strictly monotone, then EP(1) has at most one solution.

(iii) If ψ(⋅,v) is hemicontinuous for each v ∈ U and ψ is strongly monotone, then EP(1) has a unique solution.

In this section, in addition to the assumptions of Section 1, we shall suppose that ψ is monotone, and that ψ(⋅,v) is hemicontinuous for each v ∈ U. We denote by U∗ the solutions set of EP(1).

Suppose that there exists an equilibrium bifunction ϕ : E × E → R which possesses the following properties:

(a) ϕ is strongly monotone with constant τ > 0,

(b) for all u,v ∈ E it holds that ϕ(u,v) ≤∥u∥∥v − u∥;

(c) ϕ(⋅,v) is hemicontinuous for each v ∈ E and ϕ(u,⋅) is convex and lower semicontinuous for each u ∈ E.

For instance, if there exists a hemicontinuous strongly monotone operator B : E → E∗ such that ∥B∥≤ 1, we can set

ϕ(u,v) = 〈B(u),v − u〉. (3)

If E is a Hilbert space, the simplest choice for B is the identity map, i.e

ϕ(u,v) = 〈u,v − u〉.

We now consider the perturbed problem: Find a point uɛ ∈ U such that

ψ(uɛ,v) + ɛϕ(uɛ,v) ≥ 0∀v ∈ U, (4)

where ɛ is a positive parameter.

Set Φ(u,v) = ψ(u,v) + ɛϕ(u,v), then Φ is an equilibrium bifunction, which is strongly monotone with constant ɛτ, moreover, Φ(⋅,v) is hemicontinuous for each v ∈ E and Φ(u,⋅) is convex and lower semicontinuous for each u ∈ E. Applying now Proposition 2.1 with ψ = Φ, we conclude that EP(4) has always a unique solution.

Theorem 2.1. If U∗ ⁄= ∅, then {uɛ}→un∗ as ɛ→0, where

un∗ ∈ U∗ : ϕ(u n∗,w) ≥ 0∀w ∈ U∗. (5)

Proof. First we note that EP(5) has the unique solution un ∗ due to Proposition 2.1. If u∗ ∈ U∗, then

ψ(u∗,u ɛ) ≥ 0andψ(uɛ,u∗) + ɛϕ(u ɛ,u∗) ≥ 0.

Adding these inequalities gives

ɛϕ(uɛ,u∗) ≥−[ψ(u∗,u ɛ) + ψ(uɛ,u∗)] ≥ 0.

Since ϕ is strongly monotone it follows that

−ɛϕ(u∗,u ɛ) = −ɛ[ϕ(uɛ,u∗) + ϕ(u∗,u ɛ)] + ɛϕ(uɛ,u∗) ≥ ɛτ∥u ɛ − u∗∥2, (6)

and

∥u∗∥≥ τ∥u ɛ − u∗∥.

So, the sequence {uɛ} is bounded, hence it has weak limit points. Note that in view of Proposition 2.1 (i),

Φ(u,uɛ) = ψ(u,uɛ) + ɛϕ(u,uɛ) ≤ 0∀u ∈ U.

Since Φ(u,⋅) is convex and lower semicontinuous, it is weakly lower semicontinuous and, for any limit point u′ of {uɛ}, we have

0 ≥ lim ɛ→0[ψ(u,uɛ) + ɛϕ(u,uɛ)] = lim ɛ→0ψ(u,uɛ) = ψ(u,u′)∀u ∈ U,

i.e. u′ solves problem (2), and, in view of Proposition 2.1 (i), it solves EP (1) too. So, all the weak limits of {uɛ} are contained in U∗. Using (6) with u∗ = u n∗, i.e.

−ϕ(un∗,u ɛ) ≥ τ∥uɛ − un∗∥2,

we have by setting ɛ → 0

0 ≥−ϕ(un∗,u′) ≥ τ∥u′− u n∗∥2 ≥ 0,

where u′ is any limit point of {uɛ}. Therefore, lim ɛ→0uɛ = un∗, as desired. □

The result above is clearly an extension of the known convergence properties of the Browder-Tikhonov approximations from variational inequalities; see e.g. [9].

3. Gap and D-gap functions

From now on, we shall consider EP(1) where

ψ(u,v) = h(u,v) + f(u) − f(v),

h : E × E → R is a differentiable equilibrium bifunction, h(u,⋅) is convex for each u ∈ E and f : E → R is a convex continuous, but not necessarily differentiable function. In other words, the problem is to find u∗ ∈ U such that

h(u∗,v) + f(u∗) − f(v) ≥ 0∀v ∈ U (7)

In what follows we shall consider the simplified variant (3) for the perturbation bifunction ϕ and we shall suppose that B : E → E∗ is a linear continuous operator which is strongly monotone with constant τ > 0 and ∥B∥≤ 1. Then, the perturbed EP is formulated as follows: Find uɛ ∈ U such that

h(uɛ,v) + f(uɛ) − f(v) + ɛ〈Buɛ,v − uɛ〉≥ 0∀v ∈ U, (8)

where ɛ > 0 is a given number.

We denote by U∗ the solutions sets of EP(7). From Proposition 2.1 it follows that EP(8) has always a unique solution. Moreover, in view of Theorem 2.1, if U∗ ⁄= ∅, then {uɛ}→un∗ as ɛ→0, where

un∗ ∈ U∗ : 〈Bu n∗,w − u n∗〉≥ 0∀w ∈ U∗.

For brevity, we set hɛ(u,v) = h(u,v) + ɛ〈Bu,v − u〉. Thus, hɛ is the cost bifunction in the regularized EP. Clearly, hɛ is strongly monotone. Therefore, in order to solve EP(8) with fixed ɛ, we can apply the D-gap function approach from [6].

Set

Φα(ɛ)(u,v) = −h ɛ(u,v) − f(v) + f(u) − 0.5α∥v − u∥2

and

μα(ɛ)(u) = sup v∈UΦα(ɛ)(u,v) = Φ α(ɛ)(u,v α(ɛ)(u)), (9)

where α is a fixed number. The function μα(ɛ) can serve as a gap function for EP(8). Note that the inner maximization problem in (9) always has the unique solution vα (ɛ)(u), since Φα (ɛ)(u,⋅) is strongly concave and continuous.

The optimality condition for EP(8) and for the inner problem in (9) can be formulated in the form of the mixed variational inequalities.

Proposition 3.1. [6, Propositions 2.1 and 2.3] (i) An element uɛ solves EP(8) if and only if uɛ ∈ U and

〈∇vhɛ(uɛ,uɛ),v − uɛ〉 + f(v) − f(uɛ) ≥ 0∀v ∈ U. (10)

(ii) For all u′ ∈ U it holds that

〈∇vhɛ(u′,v α(u′)) + α(v α(u′) − u′),v − v α(u′)〉+ f(v) − f(vα(u′))≥0∀v ∈ U. (11)

The basic properties of the gap function μα (ɛ) can be obtained by using the similar results from [6, Proposition 2.4].

Proposition 3.2. (i) It holds that μα(ɛ)(u) ≥ 0 for every u ∈ U.

(ii) If μα(ɛ)(u) = 0 and u ∈ U, then u ∈ Uɛ∗.

(iii) The following properties are equivalent:

(a) u ∈ Uɛ∗; (b) u = vα(ɛ)(u); (c) μα(ɛ)(u) = 0 and u ∈ U.

Therefore, EP(8) can be in principle replaced with the constrained optimization problem:

min u∈U → μα(ɛ)(u).

The gap function μα(ɛ) is however non-smooth in general and this fact may create additional difficulties in developing a suitable descent method. In order to obtain a smooth problem we turn to so-called D-gap functions.

Let us now consider the function

ψαβ(ɛ)(u) = μ α(ɛ)(u) − μ β(ɛ)(u),

where 0 < α < β. In order to obtain the basic properties of ψαβ(ɛ) we need the following auxiliary assertion.

Proposition 3.3. For every u ∈ E, we have

∥u − vβ(ɛ)(u)∥2 ≤ 2ψ αβ(ɛ)(u)∕(β − α) ≤∥u − v α(ɛ)(u)∥2 (12)

Proof. By definition,

ψαβ(ɛ)(u)=Φ α(ɛ)(u,v α(ɛ)(u)) − Φ β(ɛ)(u,v β(ɛ)(u)) ≥Φα(ɛ)(u,v β(ɛ)(u)) − Φ β(ɛ)(u,v β(ɛ)(u)) ≥ (β − α)∥u − v β(ɛ)(u)∥2∕2,

i.e. the left inequality in (12) holds. Similarly, we obtain the right inequality in (12). □

The next proposition, which follows directly from Propositions 3.2 and 3.3, says that the D-gap function ψαβ(ɛ) possesses the gap properties not only on the feasible set U but over the whole space too.

Proposition 3.4. (i) It holds that ψαβ(ɛ)(u) ≥ 0 for every u ∈ E.

(ii) It is true that ψαβ(ɛ)(u) = 0⇔u ∈ U ɛ∗.

Thus, the perturbed EP(8) is equivalent to the unconstrained minimization problem

min u∈E → ψαβ(ɛ)(u). (13)

However, this problem can have in principle local minima which differ from the global ones. For this reason, it is more suitable to replace EP(8) with the problem of finding a stationary point of problem (13) that is

∇ψαβ(ɛ)(u) = 0.

This result needs certain additional assumptions.

(A1) The map ∇vh(⋅,⋅) is uniformly Lipschitz continuous with constant Lh .

(A2) The map ∇uh(⋅,⋅) is continuous.

(A3) The map ∇uh(u,⋅) is monotone for each fixed u ∈ E.

Note that it follows from (A1) that ∇vhɛ(⋅,⋅) is uniformly Lipschitz continuous with constant Lh ′ = L h + 1. Also, it follows from (A3) that ∇uhɛ(u,⋅) is strongly monotone for each fixed u ∈ E.

For each u ∈ U, we set

H(u) = ∇vh(u,v)∣v=u,

then

Hɛ(u) = ∇vhɛ(u,v)∣v=u = H(u) + ɛBu.

Since h is monotone, then so is H (see [11, Proposition 2.1.17]). Moreover, it follows that the bifunction hɛ is strongly monotone with constant ɛτ and so is the map Hɛ : E → E∗.

The following results are crucial for applying D-gap functions to nonsmooth EPs of form (7).

Proposition 3.5. (i) Let (A1) and (A2) hold. Then the function ψαβ(ɛ) is continuously differentiable and

∇ψαβ(ɛ)(u)=∇ uhɛ(u,vβ(ɛ)(u)) −∇ uhɛ(u,vα(ɛ)(u)) +β(u − vβ(ɛ)(u)) − α(u − v α(ɛ)(u)).

(ii) Let (A1),(A2) and (A3) hold. Then ∇ψαβ(ɛ)(u) = 0 implies that u ∈ Uɛ∗.

The proofs of this results follow directly from Theorems 4.1 and 5.1 in [6], respectively.

The smoothing property of D-gap functions for mixed variational inequalities was noticed by Konnov [10].

Assertion (ii) shows that the initial non-smooth and constrained problem (8) can be replaced with the problem of finding a stationary point of a continuously differentiable function ψαβ(ɛ). This problem can be solved with the help of the usual unconstrained optimization methods. We intend to describe such a method in the next section.

4. Solution method

We first establish an error bound with the help of the D-gap function. Let us introduce the additional condition.

(A4) The map ∇uh(⋅,⋅) is uniformly Lipschitz continuous on each bounded subset of E × E.

Lemma 4.1. Let (A1) and (A4) hold. Then

∥u′− u ɛ∥≤γ̂∥u′− v β(ɛ)(u′)∥∀u′ ∈ E, (14)

where γ̂ = (β + 2Lh′)∕(ɛτ), uɛ solves EP(8).

Proof. Take an arbitrary point u′ ∈ E. For brevity, set v′ = v β(ɛ)(u′). Adding (10) with v = v′ and (11) with α = β, v = uɛ gives

0≤〈∇vhɛ(uɛ,uɛ) −∇vhɛ(u′,v′),v′− u ɛ〉 + β〈v′− u′,u ɛ − v′〉 =〈∇vhɛ(uɛ,uɛ) −∇vhɛ(u′,u′),v′− u ɛ〉 +〈∇vhɛ(u′,u′) −∇ vhɛ(u′,v′),v′− u ɛ〉 + β〈v′− u′,u ɛ − v′〉.

Since H is monotone, we have

ɛτ∥uɛ − u′∥2≤〈∇ vhɛ(uɛ,uɛ) −∇vhɛ(u′,u′),u∗− u′〉 ≤〈∇vhɛ(uɛ,uɛ) −∇vhɛ(u′,u′),v′− u′〉 +〈∇vhɛ(u′,u′) −∇ vhɛ(u′,v′),u′− u ɛ〉 +〈∇vhɛ(u′,u′) −∇ vhɛ(u′,v′),v′− u′〉 +β〈v′− u′,u ɛ − u′〉 + β〈v′− u′,u′− v′〉.

Since ∇vhɛ(u′,⋅) is monotone, it follows that

〈∇vhɛ(u′,u′) −∇ vhɛ(u′,v′),v′− u′〉≤ 0.

Besides, it is clear that β〈v′− u′,u′− v′〉≤ 0. Taking into account both the inequalities and (A1),(A4), we obtain

ɛτ∥u∗− u′∥2≤L h′∥u∗− u′∥∥v′− u′∥ +Lh′∥u∗− u′∥∥v′− u′∥ + β∥u∗− u′∥∥v′− u′∥,

i.e. (14) holds with γ̂ = (β + 2Lh′)∕(ɛτ). □

From this proposition, we can get the following global error result for EP(8).

Theorem 4.1. Let (A1) and (A4) hold. Then there exists a constant γ ˜ > 0 which is independent of ɛ and such that

ɛ2∥u − u ɛ∥2 ≤γ˜ψ αβ(ɛ)(u)∀u ∈ U,

where uɛ solves EP(8).

Proof. Combining Proposition 3.3 and Lemma 4.1, we have

ɛ2∥u − u ɛ∥2 ≤ [2(β + L h′)2∕(τ2(β − α)]ψ αβ(u) = γ˜ψαβ(u)∀u ∈ E,

as desired. □

Set

r(u) = vα(ɛ)(u) − v β(ɛ)(u),

s(u) = α[u − vα(ɛ)(u)] − β[u − v β(ɛ)(u)].

Now we state an algorithm for EP(8), which can be viewed as an application of the algorithm from [6].

Algorithm.

Step 0: Select an initial point u0 ∈ E and parameters ρ > 0,θ ∈ (0, 1),γ > 0. Set k = 0.

Step 1: If ψαβ(ɛ)(uk) = 0, then stop, uk is a solution of EP.

Step 2: Set dk = r(uk) + ρs(uk).

Step 3: Compute m as the smallest nonnegative integer such that

ψαβ(ɛ)(uk + θmdk) − ψ αβ(ɛ)(uk) ≤−θmγ(∥r(uk)∥ + ρ∥s(uk)∥)2.

Step 4: Set λk = θm,uk+1 = uk + λ kdk,k = k + 1 and go to Step 1.

A convergence result for this algorithm follows directly from Theorem 6.2 in [6].

Theorem 4.2. Let (A1), (A3) and (A4) hold. Then the sequence {uk}, generated by the algorithm with ρ ∈ (0,ρ˜) and γ ≤ ɛτ∕2, converges strongly to a unique solution of EP(8).

Now we can describe a solution method for monotone EP(7).

Choose a number θ > 0, a positive sequence {ɛl}↘ 0 and a point z0 ∈ E. For each l = 1, 2,… we have a point zl−1 ∈ E and set ɛ = ɛl and u0 = zl−1. Afterwards we apply the algorithm above and obtain a point

uk ∈{u ∈ E∣ψ αβ(ɛ)(u) ≤ ψ αβ(ɛ)(u0)}

such that

ψαβ(ɛ)(uk) ≤ ɛ(2+θ). (15)

Then we set zl = uk and l = l + 1.

Theorem 4.3. Let all the assumptions of Theorem 4.2 hold. If EP(7) is solvable, then

lim l→∞zl = u n∗.

Proof. Using Theorem 4.1, we have

ɛl2∥zl − u ɛl∥2 ≤γ˜ψ αβ(ɛ)(zl).

In view of (15) we now obtain

ɛl2∥zl − u ɛl∥2 ≤γ˜2ɛ l2+θ.

It follows that

∥zl − u n∗∥≤∥zl − u ɛl∥ + ∥uɛl − un∗∥≤∥u ɛl − un∗∥ + γ˜ɛ lθ,

Due to Theorem 2.1 {uɛl}→un∗, hence we obtain lim l→∞zl = u n∗, as desired. □

Note that many problems in Mathematical Physics and various saddle point problems involve non strictly monotone bifunctions; see e.g. [1], [12], [13]. Hence, our approach can be applied for rather broad classes of problems.

References

[1]   C. Baiocchi and A. Capelo, Variational and Quasivariational Inequalities: Applications to Free Boundary Problems, John Wiley and Sons, New York, 1984.

[2]   M. Bianchi and S. Schaible, Generalized monotone bifunctions and equilibrium problems, J. Optim. Theory Appl. 90 (1996), pp. 31–43.

[3]   E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems, The Mathem. Student 63 (1994), pp. 123–145.

[4]   I.V. Konnov and S. Schaible, Duality for equilibrium problems under generalized monotonicity, J. Optim. Theory Appl. 104 (2000), pp. 395–408.

[5]   O.Chadli, I.V.Konnov, and J.C.Yao, Descent method for equilibrium problems in a Banach space, Comp. and Mathem. Appl., to appear.

[6]   I.V.Konnov and O.V.Pinyagina, D-gap functions for a class of equilibrium problems in Banach spaces, Computational Methods in Applied Mathematics 3 (2003), No.2, pp. 274–286.

[7]   I.V.Konnov and O.V.Pinyagina, Descent method with respect to the gap function for nonsmooth equilibrium problems, Russ. Math.(Iz. VUZ), to appear.

[8]   I.V. Konnov and S. Kum, Descent methods for mixed variational inequalities in a Hilbert space, Nonlinear Analysis: Theory, Methods and Applications 47 (2001), pp. 561–572.

[9]   A.B. Bakushinskii and A.V. Goncharskii, Iterative Solution Methods for Ill-Posed Problems, Nauka, Moscow, 1989 (in Russian).

[10]   I.V. Konnov, On a class of D-gap functions for mixed variational inequalities, Russ. Math.(Iz. VUZ) 43 (1999), No.12, pp. 60–64.

[11]   I.V. Konnov, Combined Relaxation Methods for Variational Inequalities, Springer-Verlag, Berlin, 2001.

[12]   T. Parthasarathy and T.E.S. Raghavan, Some Topics in Two-person Games, Elsevier, New York, 1977.

[13]   B.T. Polyak, Introduction to Optimization, Optimization Software, New York, 1987.

KAZAN STATE UNIVERSITY, DEPARTMENT OF APPLIED MATHEMATICS, 18, KREMLEVSKAYA ST., KAZAN, RUSSIA, 420008

E-mail address: ikonnov@ksu.ru

KAZAN STATE UNIVERSITY, DEPARTMENT OF ECONOMIC CYBERNETICS, 18, KREMLEVSKAYA ST., KAZAN, RUSSIA, 420008

E-mail address: Olga.Piniaguina@ksu.ru