# A New Gap Function for Vector Variational Inequalities with an Application

Authors: Hui-qiang Ma; Nan-jing Huang; Meng Wu; Donal O'Regan
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We consider a vector variational inequality in a finite-dimensional space. A new gap function is proposed, and an equivalent optimization problem for the vector variational inequality is also provided. Under some suitable conditions, we prove that the gap function is directionally differentiable and that any point satisfying the first-order necessary optimality condition for the equivalent optimization problem solves the vector variational inequality. As an application, we use the new gap function to reformulate a stochastic vector variational inequality as a deterministic optimization problem. We solve this optimization problem by employing the sample average approximation method. The convergence of optimal solutions of the approximation problems is also investigated.


---

## Body

## 1. Introduction

The vector variational inequality (VVI for short), which was first proposed by Giannessi [1], has been widely investigated by many authors (see [2–9] and the references therein). VVI can be used to model a range of vector equilibrium problems in economics, traffic networks, and migration equilibrium problems (see [1]).One approach for solving a VVI is to transform it into an equivalent optimization problem by using a gap function. A gap function was first introduced to study optimization problems and has become a powerful tool in the study of convex optimization problems. Also a gap function was introduced in the study of scalar variational inequalities. It can reformulate a scalar variational inequality as an equivalent optimization problem, and so some effective solution methods and algorithms for optimization problems can be used to find solutions of variational inequalities. Recently, many authors extended the theory of gap functions to VVI and vector equilibrium problems (see [2, 4, 6–9]). In this paper, we present a new gap function for VVI and reformulate it as an equivalent optimization problem. We also prove that the gap function is directionally differentiable and that any point satisfying the first-order necessary optimality condition for the equivalent optimization problem solves the VVI.In many practical problems, problem data will involve some uncertain factors. In order to reflect the uncertainties, stochastic vector variational inequalities are needed. Recently, stochastic scalar variational inequalities have received a lot of attention in the literature (see [10–20]). The ERM (expected residual minimization) method was proposed by Chen and Fukushima [11] in the study of stochastic complementarity problems. They formulated a stochastic linear complementarity problem (SLCP) as a minimization problem which minimizes the expectation of a NCP function (also called a residual function) of SLCP and regarded a solution of the minimization problem as a solution of SLCP. This method is the so-called expected residual minimization method. Following the ideas of Chen and Fukushima [11], Zhang and Chen [20] considered stochastic nonlinear complementary problems. Luo and Lin [18, 19] generalized the expected residual minimization method to solve a stochastic linear and/or nonlinear variational inequality problem. However, in comparison to stochastic scalar variational inequalities, there are very few results in the literature on stochastic vector variational inequalities. In this paper, we consider a deterministic reformulation for the stochastic vector variational inequality (SVVI). Our focus is on the expected residual minimization (ERM) method for the stochastic vector variational inequality. It is well known that VVI is more complicated than a variational inequality, and they model many practical problems. Therefore, it is meaningful and interesting to study stochastic vector variational inequalities.The rest of this paper is organized as follows. In Section2, some preliminaries are given. In Section 3, a new gap function for VVI is constructed and some suitable conditions are given to ensure that the new gap function is directionally differentiable and that any point satisfying the first-order necessary condition of optimality for the new optimization problem solves the vector variational inequality. In Section 4, the stochastic VVI is presented and the new gap function is used to reformulate SVVI as a deterministic optimization problem.


## 2. Preliminaries

In this section, we will introduce some basic notations and preliminary results.Throughout this paper, denote byxT the transpose of a vector or matrix x, by |·| the Euclidean norm of a vector or matrix, and by 〈·,·〉 the inner product in ℝn. Let K be a nonempty, closed, and convex set of ℝn,Fi:ℝn→ℝn (i=1,…,p) mappings, and F:=(F1,…,Fp)T. The vector variational inequality is to find a vector x*∈K such that
(1)(〈F1(x*),y-x*〉,…,〈Fp(x*),y-x*〉)T∉-intℝ+p,∀y∈K,
where ℝ+p is the nonnegative orthant of ℝp and intℝ+p denotes the interior of ℝ+p. Denote by S the solution set of VVI (1) and by Sξ the solution set of the following scalar variational inequality (VIξ): find a vector x*∈K, such that
(2)〈∑j=1p‍ξjFj(x*),y-x*〉≥0,∀y∈K,
where ξ∈B:={ξ∈ℝ+p:∑j=1p‍ξj=1}.Definition 1.
A functionφξ:K→ℝ is said to be a gap function for VIξ (2) if it satisfies the following properties: (i)
φξ(x)≥0,forallx∈K;(ii)
φξ(x*)=0 iff x* solves VIξ (2).Definition 2.
A functionψ:K→ℝ is said to be a gap function for VVI (1) if it satisfies the following properties: (i)
ψ(x)≥0,forallx∈K;(ii)
ψ(x*)=0 iff x* solves VVI (1).Suppose thatG is an n×n symmetric positive definite matrix. Let
(3)φξ(x):=maxy∈K{〈∑j=1p‍ξjFj(x),x-y〉-12|x-y|G2},
where |x|G2:=〈x,Gx〉. Note that
(4)λmin|x|≤|x|G≤λmax|x|,
where λmin and λmax are the smallest and largest eigenvalues of G, respectively. It was shown in [21] that the maximum in (3) is attained at
(5)Hξ(x):=ProjK,G(x-G-1∑j=1pξjFj(x)),
where ProjK,G(x) is the projection of the point x onto the closed convex set K with respect to the norm |·|G. Thus,
(6)φξ(x)=〈∑j=1p‍ξjFj(x),x-Hξ(x)〉-12|x-Hξ(x)|G2.Lemma 3.
The projection operatorProjK,G(·) is nonexpansive; that is,
(7)|ProjK,G(x)-ProjK,G(y)|G≤|x-y|G,∀x,y∈ℝn.Lemma 4.
The functionφξ is a gap function for VIξ (2) and x*∈K solves VIξ (2) iff it solves the following optimization problem:
(8)minx∈Kφξ(x).The gap functionφξ is also called the regularized gap function for VIξ. When Fj (j=1,…,p) are continuously differentiable, we have the following results.Lemma 5.
IfFj (j=1,…,p) are continuously differentiable, then φξ is also continuously differentiable in x, and its gradient is given by
(9)∇xφξ(x)=∑j=1p‍ξjFj(x)-(∑j=1p‍ξj∇xFj(x)-G)(Hξ(x)-x).Lemma 6.
Assume thatFj are continuously differentiable and that the Jacobian matrixes ∇xFj(x) are positive definite for all x∈K (j=1,…,p). If x is a stationary point of problem (8), that is,
(10)〈∇xφξ(x),y-x〉≥0,∀y∈K,
then it solves VIξ (2).


## 3. A New Gap Function for VVI and Its Properties

In this section, based on the regularized gap functionφξ for VIξ (2), we construct a new gap function for VVI (1) and establish some properties under some mild conditions.Let(11)ψ(x):=minξ∈Bφξ(x).
Before showing that ψ is a gap function for VVI, we first present a useful result.Lemma 7.
The following assertion is true:(12)S=∪ξ∈BSξ.Proof.
Suppose thatx*∈∪ξ∈BSξ. Then, there exists a ξ¯∈B such that x*∈Sξ¯ and
(13)∑j=1p‍ξ¯j〈Fj(x*),y-x*〉=〈∑j=1p‍ξ¯jFj(x*),y-x*〉≥0,∀y∈K.
For any fixed y∈K, since ξ¯∈B, there exists a j∈{1,…,p} such that
(14)〈Fj(x*),y-x*〉≥0,
and so
(15)(〈F1(x*),y-x*〉,…,〈Fp(x*),y-x*〉)T∉-intℝ+p.
Thus, we have
(16)(〈F1(x*),y-x*〉,…,〈Fp(x*),y-x*〉)T∉-intℝ+p,∀y∈K.
This implies that x*∈S and ∪ξ∈BSξ⊂S.
Conversely, suppose thatx*∈S. Then, we have
(17)(〈F1(x*),y-x*〉,…,〈Fp(x*),y-x*〉)T∉-intℝ+p,∀y∈K,
and so
(18){(〈F1(x*),y-x*〉,…,〈Fp(x*),y-x*〉)T:∀y∈K}∩(-intℝ+p)=∅.
Since K is convex, from Theorems 11.1 and 11.3 of [22], it follows that
(19)infy∈K{∑j=1p‍bj〈Fj(x*),y-x*〉}≥supy∈(-intℝ+p)〈b,y〉,
where b=(b1,…,bp)≠0. Moreover, we have b>0. In fact, if bj<0 for some j∈{1,…,p}, then we have
(20)supy∈(-intℝ+p)〈b,y〉=+∞.
On the other hand,
(21)infy∈K{∑j=1p‍bj〈Fj(x*),y-x*〉}≤{∑j=1p‍bj〈Fj(x*),x*-x*〉}=0<supy∈(-intℝ+p)〈b,y〉,
which is a contradiction. Thus, b>0. This implies that, for any z∈K,
(22)∑j=1p‍bj〈Fj(x*),z-x*〉≥infy∈K{∑j=1p‍bj〈Fj(x*),y-x*〉}≥supy∈(-intℝ+p)〈b,y〉=0.
Taking ξ=b/(∑j=1pbj), then ξ∈B and
(23)〈∑j=1p‍ξjFj(x*),z-x*〉≥0,∀z∈K,
which implies that x*∈Sξ and S⊂∪ξ∈BSξ.
This completes the proof.Now, we can prove thatψ is a gap function for VVI (1).Theorem 8.
The functionψ given by (11) is a gap function for VVI (1). Hence, x*∈K solves VVI (1) iff it solves the following optimization problem:
(24)minx∈Kψ(x).Proof.
Note that for anyξ∈B, φξ(x) given by (3) is a gap function for VIξ (2). It follows from Definition 1 that φξ(x)≥0 for all x∈K and hence ψ(x)=minξ∈Bφξ(x)≥0 for all x∈K.
Assume thatψ(x*)=0 for some x*∈K. From (6), it is easy to see that φξ(x*) is continuous in ξ. Since B is a closed and bounded set, there exists a vector ξ¯∈B such that ψ(x*)=φξ¯(x*), which implies that φξ¯(x*)=0 and x*∈Sξ¯. It follows from Lemma 7 that x* solves VVI (1).
Suppose thatx* solves VVI (1). From Lemma 7, it follows that there exists a vector ξ¯∈B such that x*∈Sξ¯ and so φξ¯(x*)=0. Since, for all ξ∈B, φξ(x*)≥0, we have ψ(x*)=minξ∈Bφξ(x*)=0.
Thus, (11) is a gap function for VVI (1). The last assertion is obvious from the definition of gap function.
This completes the proof.Sinceψ is constructed based on the regularized gap function for VIξ, we wish to call it a regularized gap function for VVI (1). Theorem 8 indicates that in order to get a solution of VVI (1), we only need to solve problem (24). In what follows, we will discuss some properties of the regularized gap function ψ.Theorem 9.
IfFj (j=1,…,p) are continuously differentiable, then the regularized gap function ψ is directionally differentiable in any direction d∈ℝn, and its directional derivative ψ′(x;d) is given by
(25)ψ′(x;d)=infξ∈B(x)〈∇xφξ(x),d〉,
where B(x):={ξ¯∈B:φξ¯(x)=minξ∈Bφξ(x)}.Proof.
It follows since the projection operator is nonexpansive thatφξ(x) is continuous in (ξ,x). Thus, B(x) is nonempty for any x∈K. From Lemma 5, it follows that φξ(x) is continuously differentiable in x and that
(26)∇xφξ(x)=∑j=1p‍ξjFj(x)-(∑j=1p‍ξj∇xFj(x)-G)(Hξ(x)-x)
is continuous in (ξ,x). It follows from Theorem 1 of [23] that ψ is directionally differentiable in any direction d∈ℝn, and its directional derivative ψ′(x;d) is given by
(27)ψ′(x;d)=infξ∈B(x)〈∇xφξ(x),d〉.
This completes the proof.By the directional differentiability ofψ shown in Theorem 9, the first-order necessary condition of optimality for problem (24) can be stated as
(28)ψ′(x;y-x)≥0,∀y∈K.
If one wishes to solve VVI (1) via the optimization problem (24), we need to obtain its global optimal solution. However, since the function ψ is in general nonconvex, it is difficult to find a global optimal solution. Fortunately, we can prove that any point satisfying the first-order condition of optimality becomes a solution of VVI (1). Thus, existing optimization algorithms can be used to find a solution of VVI (1).Theorem 10.
Assume thatFj are continuously differentiable and that the Jacobian matrixes ∇xFj(x) are positive definite for all x∈K (j=1,…,p). If x*∈K satisfies the first-order condition of optimality (28), then x* solves VVI (1).Proof.
It follows from Theorem9 and (28) that, for some ξ∈B(x*),
(29)〈∇x*φξ(x*),y-x*〉≥0
holds for any y∈K. This implies that x* is a stationary point of problem (8). It follows from Lemma 6 that x* solves VIξ. From Lemma 7, we see that x* solves VVI. This completes the proof.From Theorems8 and 10, it is easy to get the following corollary.Corollary 11.
Assume that the conditions in Theorem10 are all satisfied. If x*∈K satisfies the first-order condition of optimality (28), then x* is a global optimal solution of problem (24).


## 4. Stochastic Vector Variational Inequality

In this section, we consider the stochastic vector variational inequality (SVVI). First, we present a deterministic reformulation for SVVI by employing the ERM method and the regularized gap function. Second, we solve this reformulation by the SAA method.In most important practical applications, the functionsFj (j=1,…,p) always involve some random factors or uncertainties. Let (Ω,ℱ,P) be a probability space. Taking the randomness into account, we get a stochastic vector variational inequality problem (SVVI): find a vector x*∈K such that
(30)(〈F1(x*,ω),y-x*〉,…,〈Fp(x*,ω),y-x*〉)T∉-intℝ+p,∀y∈K,a.s.,
where Fj:ℝn×Ω→ℝn are mappings and a.s. is the abbreviation for “almost surely" under the given probability measure P.Because of the random elementω, we cannot generally find a vector x*∈K such that (30) holds almost surely. That is, (30) is not well defined if we think of solving (30) before knowing the realization ω. Therefore, in order to get a reasonable resolution, an appropriate deterministic reformulation for SVVI becomes an important issue in the study of the considered problem. In this section, we will employ the ERM method to solve (30).Define(31)ψ(x,ω):=minξ∈Bφξ(x,ω),
where
(32)φξ(x,ω):=maxy∈K{〈∑j=1p‍ξjFj(x,ω),x-y〉-12|x-y|G2}.
The maximum in (32) is attained at
(33)Hξ(x,ω):=ProjK,G(x-G-1∑j=1p‍ξjFj(x,ω)),(34)φξ(x,ω)=〈∑j=1p‍ξjFj(x,ω),x-Hξ(x,ω)〉-12|x-Hξ(x,ω)|G2.
The ERM reformulation is given as follows:
(35)minx∈KΘ(x):=𝔼[ψ(x,ω)],
where 𝔼 is the expectation operator.Note that the objective functionΘ(x) contains the mathematical expectation. In practical applications, it is in general very difficult to calculate 𝔼[ψ(x,ω)] in a closed form. Thus, we will have to approximate it through discretization. One of the most popular discretization approaches is the sample average approximation method. In general, for an integrable function ϕ:Ω→ℝ, we approximate the expected value 𝔼[ϕ(ω)] with the sample average (1/Nk)∑ωi∈Ωk‍ϕ(ωi), where ω1,…,ωNk are independently and identically distributed random samples of ω and Ωk:={ω1,…,ωNk}. By the strong law of large numbers, we get the following lemma.Lemma 12.
Ifϕ(ω) is integrable, then
(36)limk→∞1Nk∑ωi∈Ωk‍ϕ(ωi)=𝔼[ϕ(ω)]
holds with probability one.LetΘk(x):=(1/Nk)∑ωi∈Ωk‍ψ(x,ωi). Applying the above technique, we get the following approximation of (35):
(37)minx∈KΘk(x).
In the rest of this section, we focus on the case
(38)Fj(x,ω):=Mj(ω)x+Qj(ω)
(j=1,…,p), where Mj:Ω→ℝn×n and Qj:Ω→ℝn are measurable functions such that
(39)𝔼[|Mj(ω)|2]<+∞,𝔼[|Q(ω)j|2]<+∞,j=1,…,p.
This condition implies that
(40)𝔼[∑j=1p‍Mj(ω)]2<+∞,𝔼[(∑j=1p‍|Mj(ω)|)(∑j=1p‍|Qj(ω)|)]<+∞,
and, for any scalar c,
(41)𝔼[∑j=1p‍(|Mj(ω)|c+|Qj(ω)|)]<+∞.The following results will be useful in the proof of the convergence result.Lemma 13.
Letf,g:ℝp→ℝ+ be continuous. If minξ∈Bf(ξ)<+∞ and minξ∈Bg(ξ)<+∞, then
(42)|minξ∈Bf(ξ)-minξ∈Bg(ξ)|≤maxξ∈B|f(ξ)-g(ξ)|.Proof.
Without loss of generality, we assume thatminξ∈Bf(ξ)≤minξ∈Bg(ξ). Let ξ¯ minimize f and ξ^ minimize g, respectively. Hence, f(ξ¯)≤g(ξ^) and g(ξ^)≤g(ξ¯). Thus
(43)|minξ∈Bf(ξ)-minξ∈Bg(ξ)|=g(ξ^)-f(ξ¯)≤g(ξ¯)-f(ξ¯)≤maxξ∈B|f(ξ)-g(ξ)|.
This completes the proof.Lemma 14.
WhenFj(x,ω)=Mj(ω)x+Qj(ω) (j=1,…,p), the function φξ(x,ω) is continuously differentiable in x almost surely, and its gradient is given by
(44)∇xφξ(x,ω)=∑j=1p‍ξjFj(x,ω)-(∑j=1p‍ξjMj(ω)-G)(Hξ(x,ω)-x).Proof.
The proof is the same as that of Theorem  3.2 in [21], so we omit it here.Lemma 15.
For anyx∈K, one has
(45)|x-Hξ(x,ω)|≤2λmin∑j=1p‍|Fj(x,ω)|.Proof.
For any fixedω∈Ω,  φξ(x,ω) is the gap function of the following scalar variational inequality: find a vector x*∈K, such that
(46)〈∑j=1p‍ξjFj(x*,ω),y-x*〉≥0,∀y∈K.
Hence, φξ(x,ω)≥0 for all x∈K. From (4) and (34), we have
(47)12|x-Hξ(x,ω)|G2≤〈∑j=1p‍ξjFj(x,ω),x-Hξ(x,ω)〉≤|∑j=1p‍ξjFj(x,ω)||x-Hξ(x,ω)|≤1λmin∑j=1p‍|Fj(x,ω)||x-Hξ(x,ω)|G,
and so
(48)|x-Hξ(x,ω)|G≤2λmin∑j=1p‍|Fj(x,ω)|.
It follows from (4) that
(49)|x-Hξ(x,ω)|≤1λmin|x-Hξ(x,ω)|G≤2λmin∑j=1p‍|Fj(x,ω)|.
This completes the proof.Now, we obtain the convergence of optimal solutions of problem (37) in the following theorem.Theorem 16.
Let{xk} be a sequence of optimal solutions of problem (37). Then, any accumulation point of {xk} is an optimal solution of problem (35).Proof.
Letx* be an accumulation point of {xk}. Without loss of generality, we assume that xk itself converges to x* as k tends to infinity. It is obvious that x*∈K. At first, we will show that
(50)limk→∞1Nk∑ωi∈Ωk‍ψ(xk,ωi)=𝔼[ψ(x*,ω)].
From Lemma 12, it suffices to show that
(51)limk→∞|1Nk∑ωi∈Ωk‍ψ(xk,ωi)-1Nk∑ωi∈Ωk‍ψ(x*,ωi)|=0.
It follows from Lemma 13 and the mean-value theorem that
(52)|1Nk∑ωi∈Ωk‍ψ(xk,ωi)-1Nk∑ωi∈Ωk‍ψ(x*,ωi)|≤1Nk∑ωi∈Ωk‍|ψ(xk,ωi)-ψ(x*,ωi)|=1Nk∑ωi∈Ωk‍|minξ∈Bφξ(xk,ωi)-minξ∈Bφξ(x*,ωi)|≤1Nk∑ωi∈Ωk‍maxξ∈B|φξ(xk,ωi)-φξ(x*,ωi)|≤1Nk∑ωi∈Ωk‍maxξ∈B|∇xφξ(yk,i,ωi)||xk-x*|,
where yk,i=λk,ixk+(1-λk,i)x* with λk,i∈[0,1]. Because limk→+∞xk=x*, there exists a constant C such that |xk|≤C for each k. By the definition of yk,i, we have |yk,i|≤C. Hence, for any ξ∈B and ωi∈Ωk,
(53)|∇xφξ(yk,i,ωi)|=|∑j=1p‍ξjFj(yk,i,ωi)-(∑j=1p‍ξj∇xFj(yk,i,ωi)-G)×(Hξ(yk,i,ωi)-yk,i)∑j=1p‍|≤∑j=1p‍|ξj||Fj(yk,i,ωi)|+(∑j=1p‍|ξj||∇xFj(yk,i,ωi)|+|G|)×|Hξ(yk,i,ωi)-yk,i|≤∑j=1p‍|Fj(yk,i,ωi)|+2λmin(∑j=1p‍|∇xFj(yk,i,ωi)|+|G|)×∑j=1p‍|Fj(yk,i,ωi)|≤(2λmin∑j=1p‍|Mj(ωi)|+2λmin|G|+1)×∑j=1p‍(|Mj(ωi)|C+|Qj(ωi)|)=2Cλmin(∑j=1p‍|Mj(ωi)|)2+∑j=1p‍(|Mj(ωi)|C+|Qj(ωi)|)(2λmin|G|+1)+2λmin(∑j=1p‍|Mj(ωi)|)(∑j=1p‍|Qj(ωi)|),
where the second inequality is from Lemma 15. Thus,
(54)|1Nk∑ωi∈Ωk‍ψ(xk,ωi)-1Nk∑ωi∈Ωk‍ψ(x*,ωi)|≤1Nk∑ωi∈Ωk‍maxξ∈B|∇xφξ(yk,i,ωi)||xk-x*|≤2Cλmin|xk-x*|1Nk∑ωi∈Ωk‍(∑j=1p‍|Mj(ωi)|)2+|xk-x*|1Nk∑ωi∈Ωk‍∑j=1p‍(|Mj(ωi)|C+|Qj(ωi)|)×(2λmin|G|+1)+2λmin|xk-x*|1Nk∑ωi∈Ωk‍(∑j=1p‍|Mj(ωi)|)×(∑j=1p‍|Qj(ωi)|).
From (40) and (41), each term in the last inequality above converges to zero, and so
(55)limk→∞|1Nk∑ωi∈Ωk‍ψ(xk,ωi)-1Nk∑ωi∈Ωk‍ψ(x*,ωi)|=0.
Since
(56)limk→∞1Nk∑ωi∈Ωk‍ψ(x*,ωi)=𝔼[ψ(x*,ω)],
(50) is true.
Now, we are in the position to show thatx* is a solution of problem (35).
Sincexk solves problem (37) for each k, we have that, for any x∈K,
(57)1Nk∑ωi∈Ωk‍ψ(xk,ωi)≤1Nk∑ωi∈Ωk‍ψ(x,ωi).
Letting k→∞ above, we get from Lemma 12 and (50) that
(58)𝔼[ψ(x*,ω)]≤𝔼[ψ(x,ω)],
which means that x* is an optimal solution of problem (35). This completes the proof.



---

*Source: 423040-2013-06-19.xml*