# Gap Functions and Algorithms for Variational Inequality Problems

Authors: Congjun Zhang; Baoqing Liu; Jun Wei
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We solve several kinds of variational inequality problems through gap functions, give algorithms for the corresponding problems, obtain global error bounds, and make the convergence analysis. By generalized gap functions and generalized D-gap functions, we give global bounds for the set-valued mixed variational inequality problems. And through gap function, we equivalently transform the generalized variational inequality problem into a constraint optimization problem, give the steepest descent method, and show the convergence of the method.


---

## Body

## 1. Introduction

Variational inequality problem (VIP) provides us with a simple, natural, unified, and general frame to study a wide class of equilibrium problems arising in transportation system analysis [1, 2], regional science [3, 4], elasticity [5], optimization [6], and economics [7]. Canonical VIP can be described as follows: find a point x∈K⊂ℝn such that
(1)〈T(x),y-x〉≥0,∀y∈K,
where K is a nonempty closed convex subset of ℝn, T is a mapping from ℝn into itself, and 〈·,·〉 denotes the inner product in ℝn.In recent years, considerable interest has been shown in developing various, useful, and important extensions and generalizations of VIP, both for its own sake and for its applications, such as general variational inequality problem (GVIP) [8] and set-valued (mixed) variational inequality problem (SMVIP) [9]. There are significant developments of these problems related to multivalued operators, nonconvex optimization, iterative methods, and structural analysis. More recently, much attention has been given to reformulate the VIP as an optimization problem. And gap functions, which can constitute an equivalent optimization problem, turn out to be very useful in designing new globally convergent algorithms and in analyzing the rate of convergence of some iterative methods. Various gap functions for VIP have been suggested and proposed by many authors in [8, 10–13] and  the  references therein. Error bounds are functions which provide a measure of the distance between a solution set and an arbitrary point. Therefore, error bounds play an important role in the analysis of global or local convergence analysis of algorithms for solving VIP.For the VIP defined in (1), the authors in [10] provided an equivalent optimization problem formulation through regularized gap function Gα:H→ℝ defined by
(2)Gα(x)=maxy∈K{〈F(x),x-y〉-α2∥x-y∥2},
where α is a parameter. The authors proved that x is the solution of problem (1) if and only if x is global minimizer of function Gα(x) in K and Gα(x)=0. In order to expand the definition of regularized gap function, the authors in [14] gave the definition of generalized regularized gap function defined by
(3)Gα(x)=maxy∈K{〈F(x),x-y〉-αϕ(x,y)},
where ϕ is an abstract function which satisfies conditions ranked as follows:(C1)
ϕ is continuous differentiable on H×H;(C2)
ϕ is nonnegative on H×H;(C3)
ϕ is uniformly strongly convex on H; that is, there exists a positive number λ such that
(4)ϕ(x,y1)-ϕ(x,y2)≥〈∇2ϕ(x,y2),y1-y2〉+λ∥y1-y2∥2,∀x,y1,y2∈H;(C4)
ϕ(x,y)=0⇔x=y;(C5)
∇2(x,y) is uniformly Lipschtiz continuous on H; that is, there exists a constant L′>0 such that
(5)∥∇2ϕ(x,y1)-∇2ϕ(x,y2)∥≤L′∥y1-y2∥,∀x,y1,y2∈H.Note that ∇2 is the partial of ϕ with respect to the second component and conditions (C1)–(C5) can make sense. One can refer to [10, 14] and so forth for more details.Many gap functions have been explored during the past two decades as it is shown in [10–16] and the references therein. Motivated by their work, in this paper, we solve some classes of VIP through gap functions, give algorithms for the corresponding problems, obtain global error bounds, and make the convergence analysis. We consider generalized gap functions and generalized D-gap functions for SMVIP and give global bounds for the problem through the two functions, respectively. And for GVIP, we equivalently transform it into a constraint optimization problem through gap function, introduce the steepest descent method, and show the convergence of the method.


## 2. Preliminaries

LetH be a real Hilbert space whose inner product and norm are denoted by 〈·,·〉 and ∥·∥, respectively. Let K be a nonempty closed convex set in H and let 2H be the family of all nonempty compact subsets of H.LetF,f:H→H be nonlinear operators. The GVIP can be described as follows: Find x∈H, f(x)∈K such that
(6)〈F(x),f(y)-f(x)〉≥0,∀y∈H,f(y)∈K.For single-valued operatorf:H→ℝ∪{+∞}, which is proper convex and lower semicontinuous, and for given multivalued operator T:H→2H, the SMVIP can be described as follows: Find x∈K,w∈T(x) such that
(7)〈w,y-x〉+f(y)-f(x)≥0,∀y∈K.
Note that when f=0, the original problem (7) reduces to a set-valued variational inequality problem; when f=0 and T is a single-valued operator, problem (7) is the right problem discussed in (1).Recall that the multivalued operatorT:K⊂H→2H is said to be strongly monotone with modulus β>0 on K if
(8)〈w-w′,x-x′〉≥β∥x-x′∥2,d.∀(x,w),(x′,w′)∈graph(T).
And T is said to be Lipschtiz continuous on a nonempty bounded set B⊂K, if there exists a positive constant L such that
(9)H(T(x),T(y))≤L∥x-y∥,∀x,y∈B,
where H(·,·) is the Hausdorff metric on B defined by
(10)H(T(x),T(y))=max{supr∈T(x)infs∈T(y)∥r-s∥,sups∈T(y)infr∈T(x)∥r-s∥},ffffdddddddddddcddddddddddddf∀x,y∈B.LetF:ℝn→ℝn. Then F is a P0-function if max1≤i≤n,xi≠yi(xi-yi)(Fi(x)-Fi(y))≥0, for all x,y∈ℝn and x≠y. Assume Fμ(·):ℝn→ℝn(μ>0).  Fμ  is called smoothing approximation function of F, if there exists a positive constant k such that (11)∥Fμ(x)-F(x)∥≤ku,∀u>0,x∈ℝn.
And Fμ is a uniform approximation if k is independent of x.A matrixM∈ℝn×n is a P0-matrix if  each  of its principal minors is nonnegative.We need the following lemmas. The parameters involved in the lemmas can be found in the following sections.Lemma 1 (see [11]).
If abstract functionϕ satisfies condition (C1), then the following holds:
(12)〈∇2ϕ(x,y1)-∇2ϕ(x,y2),y1-y2〉≥2λ∥y1-y2∥2,dddddddddddddddddddddddddddddd∀y1,y2∈H;
that is, ∇2(x,·) is strong monotone in H, and by (C5), one obtains that 2λ≤L′.Lemma 2 (see [17]).
If abstract functionϕ satisfies conditions (C1)–(C4), then
(13)∇2ϕ(x,y)=0⟺x=y.Lemma 3 (see [18]).
If abstract functionϕ satisfies conditions (C1)–(C5) and λ and L′ are the corresponding coefficients defined above, then one has
(14)λ∥x-y∥2≤ϕ(x,y)≤(L′-λ)∥x-y∥2,∀x,y∈H.Lemma 4 (see [19]).
If abstract functionϕ satisfies conditions (C1)–(C4), then Gα(x)≥αλ∥x-πα(x)∥2. Moreover, when Gα(x)=0, x is a solution of SMVIP.Lemma 5 (see [10]).
If abstract functionϕ satisfies conditions (C1)–(C4), then gα(x) is differentiable and
(15)∇gα(x)=∇g(x)F(x)+∇F(x)(g(x)-yα(x))-α∇xϕ(g(x),yα(x)).Lemma 6 (see [10, 19]).
If abstract functionϕ satisfies conditions (C1)–(C4), then gα is nonnegative, and gα(x)=0⇔x is a solution of GVIP.Lemma 7 (see [10]).
Let abstract functionϕ satisfy conditions (C1)–(C4). If ∇gα(x)=0 and ∇F(x) is positive definite, then x is a solution of GVIP(F,f).


## 3. Gap Functions and Error Bounds for SMVIP

In this section, by introducing appropriate gap functions, we give global error bound for SMVIP. Firstly, we need the following propositions.Proposition 8.
LetC be a nonempty closed convex set in H and let f be strictly convex in C. Then f has only one  minimum  in C.Proof.
We use proof by contradiction to show the desired result. Letx1,x2∈C be two minimal points of f; that is, f(x1)=f(x2)=minf(x). Since f is strictly convex, one obtains that
(16)f(αx1+(1-α)x2)<αf(x1)+(1-α)f(x2)=f(x1),∀α∈(0,1).
This implies that there exists a point x3=αx1+(1-α)x2∈C, such that f(x3)<f(x1), which is a contradiction. This completes the proof.LetT, f, and ϕ be defined as above and let K be a nonempty closed convex set in H. Now, we can introduce generalized gap function Gα of SMVIP(T,K) defined as follows:
(17)Gα(x)=maxy∈HΨα(x,y)=maxy∈H{〈w,x-y〉+f(x)-f(y)-αϕ(x,y)},ddddddddddddddddddddd∀x,y∈H,α>0.
From uniform convex of ϕ(x,·), one obtains that -Ψα(x,·) is also uniform convex in H. By Proposition 8, there exists a minimal point πα(x) of ϕ(x,·) in H, such that
(18)Gα(x)=〈w,x-πα(x)〉+f(x)-f(πα(x))-αϕ(x,πα(x)).Proposition 9.
If abstract functionϕ satisfies conditions (C1)–(C4) and f:H→ℝ∪{+∞} is proper convex and lower  semicontinuous, then  for all α>0, x=πα(x)⇔x is a solution of SMVIP(T,K).Proof.
From the definition ofπα(x), one has
(19)0∈∂(-Ψ(x,πα(x)))=w+∂f(πα(x))+α∇2ϕ(x,πα(x)).
By the definition of subgradient, we have
(20)f(y)≥f(πα(x))-〈w+α∇2ϕ(x,πα),y-πα(x)〉,
which is equivalent to
(21)〈w,y-πα(x)〉+f(y)-f(πα(x))≥α〈-∇2ϕ(x,πα(x)),y-πα(x)〉.
On the one hand, ifx=πα(x), from Lemma 2, one obtains ∇2ϕ(x,πα(x))=0, and so does α〈-∇2ϕ(x,πα(x)),y-πα(x)〉=0. So, from (21), we have
(22)〈w,y-πα(x)〉+f(y)-f(πα(x))≥0,
which implies that x is a solution of SMVIP(T,K).
On the other hand, ifx is a solution of SMVIP(T,K), take y=πα(x) in (7), then we have
(23)〈w,πα(x)-x〉+f(πα(x))-f(x)≥0.
From condition (C3), one has
(24)ϕ(x,x)-ϕ(x,πα(x))≥〈∇2ϕ(x,ππα(x)),x-πα(x)〉+λ∥x-πα(x)∥2.
And by conditions (C2) and (C4),
(25)ϕ(x,x)-ϕ(x,πα(x))≤0.
So we have
(26)〈∇2ϕ(x,πα(x)),x-πα(x)〉+λ∥x-πα(x)∥2≤0.
Combining (23) with (26), we have x=πα(x). This completes the proof.Based on the above discussion, one can obtain the following global error bound.Theorem 10.
If abstract functionϕ satisfies conditions (C1)–(C5), f is closed convex, and T is strong monotone and Lipschtiz continuous with respect to the solution x- of SMVIP(T,K), then one has
(27)∥x-x-∥≤L+αL′β∥x-πα(x)∥,where L and L′ can be found in (5) and (9), respectively.Proof.
Sincex- is a solution of SMVIP(T,K), take w-∈T(x-), then we obtain
(28)〈w-,y-x-〉+f(y)-f(x)≥0.
Let y=πα(x), for all x∈H. Then inequality (28) reduces to
(29)〈w-,πα(x)-x-〉+f(πα(x))-f(x)≥0.
Take y=x-, w^∈T(x) in (21) such that ∥w^-w-∥≤H(T(x),T(x-)). Then inequality (21) changes to
(30)〈w^,x--πα(x)〉+f(x-)-f(πα(x))≥α〈-∇2ϕ(x,πα(x)),x--πα(x)〉.
Combining (29) and (30), we have
(31)〈w^-w-,πα(x)-x-〉≤α〈∇2ϕ(x,πα(x)),x--πα(x)〉.
And note that
(32)α〈∇2ϕ(x,πα(x)),x--πα(x)〉=α〈∇2ϕ(x,πα(x)),x--x〉+α〈∇2ϕ(x,πα(x)),x-πα(x)〉=α〈∇2ϕ(x,πα(x))-∇2ϕ(x,x),x--x〉-α〈∇2ϕ(x,x)-∇2ϕ(x,πα(x)),x-πα(x)〉≤α∥∇2ϕ(x,πα(x))-∇2ϕ(x,x)∥∥x--x∥-2αλ∥x-πα(x)∥2≤αL′∥x-πα(x)∥∥x--x∥-2αλ∥x-πα(x)∥2.
From (8), one has
(33)β∥x-x-∥2≤〈w^-w-,x-x-〉≤〈w^-w-,x-πα(x)〉+〈w^-w-,πα(x)-x-〉≤L∥x-x-∥∥x-πα(x)∥+αL′∥x-πα(x)∥∥x-x-∥≤(L+αL′)∥x-x-∥∥x-πα(x)∥,
so we have
(34)∥x-x-∥≤L+αL′β∥x-πα(x)∥.
This completes the proof.Theorem 11.
If abstract functionϕ satisfies conditions (C1)–(C5) and T is strong monotone for the solution x- of SMVIP and is Lipschtiz continuous with module L, then Gα has global error bound with respect to SMVIP; that is,
(35)∥x-x-∥≤L+L′βαλGα(x).Proof.
By Lemma4 and Theorem 10, one obtains
(36)Gα(x)≥αλ∥x-πα(x)∥2,∥x-x-∥≤L+αL′β∥x-πα(x)∥.
So we can obtain
(37)Gα(x)≥αλβ2(L+αL′)2∥x-x-∥2,
which implies that
(38)∥x-x-∥≤L+αL′βαλGα(x).
This completes the proof.Now, we introduce generalized D-gap functionHαγ for SMVIP which is defined by
(39)Hαγ(x)=Gα(x)-Gγ(x)=maxy∈HΨα(x,y)-maxy∈HΨγ(x,y)=〈w,πγ(x)-πα(x)〉+f(πγ(x))-f(πα(x))+βϕ(x,πγ(x))-αϕ(x,πα(x)),
where πα(x) and πγ(x) are minimal points for -Ψα(x,·) and -Ψγ(x,·) in H, respectively, and 0<α<γ. For Hαγ(x), we can conclude the following result.Proposition 12.
If abstract functionϕ satisfies condition (C3), then one has
(40)(γ-α)ϕ(x,πγ(x))≤Hαγ(x)≤(γ-α)ϕ(x,πα(x)).Proof.
From the definition ofHαγ(x), one obtains that
(41)Hαγ(x)=maxy∈HΨα(x,y)-maxy∈HΨγ(x,y)=Ψα(x,πα(x))-Ψγ(x,πγ(x))≥Ψα(x,πγ(x))-Ψγ(x,πγ(x))=〈w,x-πγ(x)〉-αϕ(x,πγ(x))-〈w,x-πγ(x)〉+γϕ(x,πγ(x))=(γ-α)ϕ(x,πγ(x)).Hαγ(x)≤(γ-α)ϕ(x,πα(x)) can be  proved  similarly. This completes the proof.From Proposition12, one has the following.Proposition 13.
Ifϕ satisfies conditions (C1)–(C4), then Hαγ(x) is nonnegative, and Hαγ(x)=0⇔x is a solution of SMVIP(T,K).Proof.
From Proposition12 and nonnegative property of ϕ(·,·), we have that Hαγ(x) is nonnegative.
On the one hand, ifHαγ(x)=0, then by conditions (C2) and (C4), one has x=πα(x). Then by Proposition 9, we conclude that x is a solution of SMVIP(T,K).
On the other hand, ifx is a solution of SMVIP(T,K), by Proposition 9, one obtains that x=πα(x). From condition (C4), one has ϕ(x,πα(x))=0. And since Hαγ(x) is nonnegative, we have Hαγ(x)=0. This completes the proof.By the generalized D-gap function, we have the following error bound forSMVIP(T,K).Theorem 14.
Letϕ satisfy conditions (C1)–(C5). T is strong monotone for the solution x- of SMVIP and is Lipschtiz continuous with module L; then Hαγ(x) has global error bound with respect to SMVIP; that is,
(42)∥x-x-∥≤L+L′βλ(γ-α)Hαγ(x).Proof.
From Lemma3, Theorem 10, and Proposition 13, we have
(43)Hαγ(x)≥(γ-α)ϕ(x-πγ(x))ddddd≥(γ-α)λ∥x-πγ(x)∥2ddddd≥λ(γ-α)(βL+αL′)2∥x-x-∥2,
which implies that
(44)∥x-x-∥≤L+L′βλ(γ-α)Hαγ(x).
This completes the proof.


## 4. Steepest Descent Method for GVIP

In this section, by introducing appropriate generalized gap function, the originalGVIP(F,f) in (6) can be changed into an optimization problem with restrictions. When one designs algorithms to solve the optimization problem, the gradient of objective function is unavoidable. We try to design a new algorithm, constructing a class of descent direction, to solve the optimization problem. In the following, we set H to be ℝn. And we introduce the following generalized gap function for GVIP(F,f):
(45)gα(x)=maxg(y)∈KΨα(x,y).dddd=maxg(y)∈K{〈F(x),f(x)-f(y)〉-αϕ(f(x),f(y))}ddd.d={〈F(x),f(x)-yα(x)〉-αϕ(f(x),yα(x))},
where yα(x) is a minimal point for -Ψα(x,·), α is a positive parameter, and ϕ satisfies conditions (C1)–(C5) stated above. For gα, we have the following useful results [14]:(A1)
gα(x) is nonnegative in K;(A2)
gα(x)=0 for some x∈K⇔x is a solution of VIP;(A3)
yα(x) is the only minimizer of Ψα(x,·) in K.And similar to the discussion in [10, 11], we also give the following two assumptions:(a)
∇F(x) is positive definite for all x∈K;(b)
∇xϕ(x,y)=-∇yϕ(x,y).From Lemmas5–7, we obtain that the original GVIP (6) is equivalent to the following optimization problem:
(46)mins.t.x∈Kgα(x).
For problem (46), we give the following algorithm.Algorithm 15.
Step  0. Choose an initial value x0∈K, ε,t∈(0,1), and put k=0.
Step  1. If gα(x)≤ε, then we can end the circulation.
Step  2. Compute yα(xk), and let
(47)dk=yα(xk)-f(xk).
Step  3. Let mk be the minimal nonnegative integer m, such that
(48)gα(xk+tmdk)≤gα(xk)-t2m∥dk∥2.
Step  4. Let f(xk+1)=f(xk)+tmkdk, k=k+1; go to Step 1.Proposition 16.
Let{xk} be a sequence generated by Algorithm 15. If {xk} are not the solutions of GVIP(F,f), then
(49)∇gα(xk)Tdk<0;
that is, dk is the descent direction of gα at xk, where dk is defined in (47).Proof.
To begin, we show thatf(xk)∈K, for all positive integer k. From Algorithm 15, one obtains that f(x0)∈K. We prove this result by induction. Assume f(xk)∈K; we only need to show that f(xk+1)∈K. Since xk,yα(xk)∈K, tk∈(0,1), and K is convex, we have
(50)f(xk+1)=f(xk)+tkdk=(1-tk)f(xk)+tkyα(xk)∈K.
For simplicity, yα(xk), xk are replaced by yα, x, respectively. From Lemma 5, one has
(51)∇gα(x)Td={yαF(x)+∇F(x)(g(x)-yα)-α∇xϕ(g(x),yα)}Td=(g(x)-yα)T∇F(x)(yα-g(x))+{∇g(x)F(x)-α∇xϕ(g(x),yα)}T(yα-g(x)).
Since (g(x)-yα)T∇F(x)(yα-g(x))<0, we only need to show that {∇g(x)F(x)-α∇xϕ(g(x),yα)}T(yα-g(x))≤0. Since yα is the unique minimizer of -Ψ(x,·) in K, we have
(52)〈-∇yΨ(x,yα),u-yα〉=〈∇g(x)F(x)+α∇yϕ(x,yα),u-yα〉≥0,∀u∈K.
Let u=x∈K in (52). One has
(53){∇g(x)F(x)+α∇yϕ(x,yα)}T(yα-x)≤0.
From assumption (b), we have
(54){∇g(x)F(x)-α∇xϕ(x,yα)}T(yα-x)≤0.
This completes the proof.Now, we are in a position to show the global convergence result for Algorithm15.Theorem 17.
Let{xk} be a sequence generated by Algorithm 15, and let x⋆ be the cluster point of {xk}. Then x⋆ is a solution of GVIP(F,f).Proof.
Let{xk}K be a subsequence which converges to x⋆. If gα(x⋆)=0, then from Lemma 6, x⋆ is a solution of GVIP. If gα(x⋆)≠0, from the continuous property, one obtains that {yα(xk)}K→yα(x⋆) which implies that
(55){dk}⟶yα(x⋆)-f(x⋆).
Now, we begin to show that the cluster point dx⋆ of {dk}K is zero. We  use  proof by contradiction. Assume d⋆=yα(x⋆)-x⋆≠0. On the one hand, from Proposition 16, one has that
(56)∇gα(x⋆)T<0.
On the other hand, from Proposition 16, we obtain that {gα(xk)} is monotonically decreasing and bounded; that is, the sequence {gα(xk)} is convergent. From step 3 of Algorithm 15, one has
(57)0≤t2mk∥dk∥2≤gα(xk)-gα(xk+1)⟶0,ask⟶∞.
Hence, we have limk→∞t2mk∥dk∥2=0; that is,
(58)limk→∞t2mk=0(d⋆≠0).
Without loss of generality, we assume tk∈(0,1), for all k. Then one cannot find the minimal nonnegative integer mk; that is,
(59)gα(xk+tmk-1dk)>gα(xk)-(tmk)2∥dk∥2,∀k,
Or, equally,
(60)gα(xk+tmk-1dk)-gα(xk)tmk>-tmk∥dk∥2,∀k.
Let k→∞, from (58), and gα  be  continuous and differentiable; we can obtain
(61)∇gα(x⋆)T≥0.
Inequalities (56) and (61) are at odds. This completes the proof.



---

*Source: 965640-2013-11-11.xml*