# On Gap Functions for Quasi-Variational Inequalities

Authors: Kouichi Taji
Journal: Abstract and Applied Analysis
 (2008)

---

## Abstract

For variational inequalities, various merit functions, such as the gap function, the regularized gap function, the D-gap function and so on, have been proposed. These functions lead to equivalent optimization formulations and are used to optimization-based methods for solving variational inequalities. In this paper, we extend the regularized gap function and the D-gap functions for a quasi-variational inequality, which is a generalization of the variational inequality and is used to formulate generalized equilibrium problems. These extensions are shown to formulate equivalent optimization problems for quasi-variational inequalities and are shown to be continuous and directionally differentiable.


---

## Body

## 1. Introduction

In this paper,
we consider merit functions for quasi-variational inequalities, denoted by
QVIP, to find a vectorx*∈S(x*) such
that
(1.1)〈F(x*),x−x*〉≥0∀x∈S(x*), where F:ℝn→ℝn is a mapping, the symbol 〈⋅,⋅〉 denotes the inner
product in ℝn, and S:ℝn→2ℝn is a set-valued
mapping of which S(x) is a closed
convex set in ℝn for each x. When the mapping S is a constant
closed convex set for all x∈ℝn, QVIP reduces to a well-known variational inequality
[1, 2]:
(1.2)〈F(x*),x−x*〉≥0∀x∈S.QVIP is used to study and formulate generalized
equilibrium problems, such as the generalized Nash equilibrium problem in which
a strategy set of each player varies according to the other players' strategies
[3, 4]. For variational
inequalities, various merit functions, such as the gap function, the
regularized gap function [5], the D-gap functions [6, 7], and so on, have been proposed. These functions are
used to make an equivalent optimization formulation for a variational
inequality, and based on these formulations, several optimization-based methods
are proposed for solving variational inequalities [8, 9].Fukushima [10] has proposed gap functions for QVIP, which lead to
equivalent optimization formulation for QVIP. In this paper, we extend the
results of Fukushima in two directions. One is to show the directional
differentiability under more general setting (Theorem 2.5) and to give one
sufficient condition for stationary point to be a solution (Proposition 2.7).
The other is to propose a so-called D-gap function for QVIP, which leads to an
unconstrained minimization optimization formulation for QVIP, and to show its
directional differentiability (Section 3).Notations used in this paper are summarized as
follows. The superscriptT denotes a
transpose of vector or matrix, and ∥⋅∥ denotes the Euclidean
norm in ℝn defined by ∥x∥=〈x,x〉.


## 2. Regularized Gap Function for Qvip

In this
section, we first generalize the regularized gap function for a variational
inequality to a quasi-variational inequality and show its properties.The (generalized) regularized gap functionsfα:ℝn→ℝ for QVIP
(1.1) are
defined as
(2.1)fα(x)=max⁡y{−〈F(x),y−x〉−αϕ(x,y)∣y∈S(x)}, where an α is a positive
constant and a function ϕ:ℝn×ℝn→ℝ satisfies the
following conditions.(C1)
ϕ is continuously
differentiable on ℝn×ℝn.(C2)
ϕ is nonnegative
on ℝn×ℝn and ϕ(x,y)=0 if and only if x=y.(C3)
ϕ is strongly
convex uniformly in x, that is, there is a μ>0 such
that(2.2)ϕ(x,y1)−ϕ(x,y2)≥〈∇yϕ(x,y2),y1−y2〉+μ∥y1−y2∥2∀y1,y2∈ℝn.Remark 2.1.
It is easy to
verify that a functionϕ(x,y)=〈x−y,G(x−y)〉 for a positive
definite symmetric matrix G satisfies the
above conditions (C1)∼(C3). In this
case, the function (2.1) reduces
to
(2.3)f(x)=max⁡y{−〈F(x),y−x〉−12〈y−x,G(y−x)〉∣y∈S(x)} with α=1/2. This is just a regularized gap function [5] originally proposed for
variational inequalities (1.2).
By the strong convexity ofϕ and the closed
convexity of S(x), the maximum in (2.1) is uniquely attained and is given by the unique
solution yα(x) of the
following mathematical programming problem:
(2.4)min⁡y〈F(x),y−x〉+αϕ(x,y)s.t.⁢y∈S(x), and the function (2.1) is written
as
(2.5)fα(x)=−〈F(x),yα(x)−x〉−αϕ(x,yα(x)).Lemma 2.2.
A pointx* is a solution
to QVIP (1.1)
if and only if yα(x*)=x*.Proof.
Since the optimization problem (2.4) is convex with respect to y, the point yα(x*) is a solution
to (2.4) if and
only if
(2.6)〈F(x*)+α∇yϕ(x*,y),y−yα(x*)〉≥0∀y∈S(x*), which is equivalent
to
(2.7)〈α∇yϕ(x*,y),y−yα(x*)〉≥〈F(x*),yα(x*)−y〉. Then by substituting a solution x* of QVIP
(1.1) to y, we have
(2.8)〈∇yϕ(x*,y),x*−yα(x*)〉≥0. On the other hand, from the
condition (C3) we have
(2.9)〈∇yϕ(x*,yα(x*)),x*−yα(x*)〉+μ∥x*−yα(x*)∥2≤ϕ(x*,x*)−ϕ(x*,yα(x*))≤0, where the last inequality
follows from the condition (C2). The above two inequalities lead to yα(x*)=x*.
Conversely, suppose thatyα(x*)=x*. Then the inequality (2.6) reduces
to
(2.10)〈F(x*),y−x*〉≥0∀y∈S(x*), which shows that x* is a solution
to (1.1).The next theorem shows that the function (2.1) or (2.5) leads to an
equivalent optimization problem for quasi-variational inequalities. The theorem
is inherently equivalent to [10, Theorem 2], but for completeness, we provide its
proof. We note that our proof is more elementary and simpler than that of
[10, Theorem 2].Theorem 2.3.
Letfα be the function
defined by (2.1) or (2.5). Then fα(x)≥0 for all x∈S(x). Furthermore, fα(x*)=0 and x*∈S(x*) if and only if x* is a solution
to QVIP (1.1).
Hence, problem (1.1) is equivalent to finding a global optimal solution to the problem:
(2.11)minimizefα(x)subject⁢tox∈S(x).Proof.
The first assertion is obvious from the definition
(2.1) and (C2).
To prove the last assertion, suppose that x* is a solution
to QVIP. Then, we have
(2.12)〈F(x*),x*−x〉−αϕ(x*,y)≤0∀y∈S(x*). Therefore, from the definition
(2.1), we have fα(x*)=0.
For the “only if” part, we consider the regularized gap
function for fixedx*,
(2.13)f^α(x)=max⁡y{−〈F(x),y−x〉−αϕ(x,y)∣y∈S(x*)}. Then, it follows from fα(x*)=0 and x*∈S(x*) that f^α(x*)=0, which implies that x* is a solution
to the variational inequality [11]
(2.14)〈F(x*),x−x*〉≥0∀x∈S(x*). This means that x* is a solution
to QVIP.The next theorem gives a sufficient condition for the
continuity of the function (2.1).Theorem 2.4.
Letfα be the function
defined by (2.1) or (2.5). If the set-valued mapping S
is continuous
with respect to x
in the sense of
set-valued mapping [12], then fα is also
continuous in x.Proof.
In a similar way to [13], yα is shown to be
continuous in x. Therefore, the function fα is also
continuous.When the set-valued mappingS is expressed as
a finite number of convex inequalities, such that
(2.15)S(x)={y∈ℝn∣gi(x,y)≤0,⁢i=1,…,m}, where the functions gi(x,y):ℝn×ℝn→ℝ are continuous
with respect to x and y, and gi(x,⋅) are convex for
each x, then one sufficient condition for the continuity of
the set-valued mapping S is that Slater's constraint qualification holds, that is, for each x, there exists a vector y^ (possibly
depending on x) such
that
(2.16)gi(x,y^)<0∀i=1,…,m. In this case, fα is also
continuous and yα(x) satisfies the
KKT condition:
(2.17)F(x)+α∇yϕ(x,yα(x))+∑i=1mλi∇ygi(x,yα(x))=0gi(x,yα(x))≤0,λi≥0,λigi(x,yα(x))=0,i=1,…,m.Unfortunately, the functionfα defined by
(2.1) or
(2.5) is not
necessarily differentiable. However, the next theorem gives one sufficient
condition of the directional differentiability of the function fα with the set S given by
(2.15).Theorem 2.5.
Let
the mappingF:ℝn→ℝn be continuously
differentiable. Let also the set-valued mapping S
be defined as
(2.15), where
the functions gi(x,y):ℝn×ℝn→ℝ
are continuous
with respect to x and y, and gi(x,⋅)
is convex for
each x. If Slater's constraint qualification (2.16) holds, then the
function fα defined by
(2.1) or
(2.5) is
directionally differentiable in any direction d∈ℝn, and its directional derivative fα′(x;d)
is given
by
(2.18)fα′(x;d)=min⁡λ∈M(x)(F(x)+∇F(x)(x−yα(x))−α∇xϕ(x,yα(x))−∑i=1mλi∇xgi(x,yα(x)))Td, where M(x) is defined
by
(2.19)M(x)={λ∈ℝm|F(x)+α∇yϕ(x,yα(x))+∑i=1mλi∇ygi(x,yα(x))=0λi≥0,λigi(x,yα(x))=0,i=1,…,m}.Proof.
This directly follows from [14, Theorem 2].Remark 2.6.
Fukushima
[10, Theorem 3] has
also proven the directional differentiability of fα for the
function (2.3)
with S(x) polyhedral
convex. This situation is a special case of this theorem.The next proposition gives a sufficient condition for
a stationary point of the equivalent optimization problem (2.11) to be a solution of
QVIP (1.1) with
the set S given by
(2.15).Proposition 2.7.
Suppose thatx∈S(x). Suppose also that ∇F(x) is positive
definite and λi〈∇xgi(x,yα(x)),yα(x)−x〉≥0 for all i and λ∈M(x). If the function ϕ used in the
regularized gap function (2.1) or (2.5) is ϕ(x,y)=ϕ˜(x−y), where ϕ˜:ℝn→ℝ is
differentiable strongly convex function, then a stationary point x of the problem
(2.11) is a
solution to QVIP (1.1).Proof.
It suffices to show thatx is a solution
to QVIP if the following inequality holds:
(2.20)f′(x;yα(x)−x)≥0.
It is easy to see thatϕ(x,y)=ϕ˜(x−y) satisfies the
conditions (C1)∼(C3) and that ∇xϕ(x−y)=−∇yϕ(x−y). Then from the definition of directional derivative
(2.18) and the
KKT condition (2.17) for yα(x), we have
(2.21)f′(x;yα(x)−x)=min⁡λ∈M(x)(F(x)+∇F(x)(x−yα(x))−α∇xϕ(x,yα(x))−∑i=1mλi∇xgi(x,yα(x)))T(yα(x)−x)=−(yα(x)−x)T∇F(x)(yα(x)−x)−(∑i=1mλi∇ygi(x,yα(x)))T(yα(x)−x)−max⁡λ∈M(x)(∑i=1mλi∇xgi(x,yα(x)))T(yα(x)−x). Since functions gi are convex with
respect to y, we have
(2.22)gi(x,x)−gi(x,yα(x))≥∇ygi(x,yα(x))T(x−yα(x)). Then we have from the fact x∈S and (2.17)
that
(2.23)−(∑i=1mλi∇ygi(x,yα(x)))T(yα(x)−x)≤∑i=1mλi(gi(x,x)−gi(x,yα(x))≤−∑i=1mλigi(x,yα(x))≤0. Therefore, it follows from
(2.21) and the
assumption λi〈∇xgi(x,yα(x)),yα(x)−x〉≥0 that
(2.24)0≤f′(x;yα(x)−x)≤−(yα(x)−x)T∇F(x)(yα(x)−x)−max⁡λ∈M(x)(∑i=1mλi∇xgi(x,yα(x)))T(yα(x)−x)≤−(yα(x)−x)T∇F(x)(yα(x)−x), which leads to yα(x)=x from the
positive definiteness of ∇F. This shows from Lemma 2.2 that x is a solution
to QVIP.Remark 2.8.
When the functionsgi are all defined
as linearized approximation of convex functions ci:ℝn→ℝ at x, that is, gi(x,y)=ci(x)+∇ci(x)T(y−x), then we have
(2.25)∇xgi(x,yα(x))=∇ci(x)+∇2ci(x)(yα(x)−x)−∇ci(x)=∇2ci(x)(yα(x)−x). Since the Hesse matrix ∇2ci(x) is positive
semidefinite from the convexity of ci, the assumption of Proposition 2.7 is satisfied. This
result has been already obtained by Taji and Fukushima [13] for this setting, and the
above proposition is considered as a generalization in some sense.


## 3. D-Gap Function for Qvip

For0<α<β, we consider the function gαβ defined
by
(3.1)Φαβ(x)=fα(x)−fβ(x). This is a so-called D-gap
function and is originally introduced for the variational inequality (1.2) by Peng [6]. D-gap functions are shown
to construct a differentiable equivalent unconstrained optimization formulation
for VIPs.We have the next proposition.Proposition 3.1.
For0<α<β, for the function Φαβ defined by
(3.1),
(3.2)(β−α)ϕ(x,yβ(x))≤Φαβ(x)≤(β−α)ϕ(x,yα(x)).Proof.
From the definition (3.1) and the fact that yα(x),yβ∈S(x), we have
(3.3)Φαβ(x)=max⁡y∈S(x){−〈F(x),y−x〉−αϕ(x,y)}−max⁡y∈S(x){−〈F(x),y−x〉−βϕ(x,y)}≥〈F(x),x−yβ(x)〉−αϕ(x,yβ(x))−〈F(x),x−yβ(x)〉+βϕ(x,yβ(x))=(β−α)ϕ(x,yβ(x)). This shows the left-side hand of
the inequality. The right-hand side is shown in a similar way.This proposition establishes the equivalence between a
QVIP and the unconstrained minimization of a D-gap functionΦαβ.Theorem 3.2.
Let
the functionΦαβ be defined as
(3.1). Then,
for 0<α<β, Φαβ(x)≥0 for all x∈ℝn. Moreover, Φαβ(x)=0 if and only if x is a solution
to QVIP. Hence, the problem (1.1) is equivalent to finding a global optimal solution to
the unconstrained minimization problem:
(3.4)minimizeΦαβ(x).Proof.
The first half follows directly from Proposition3.1. The last half also
follows from Lemma 2.2 and Proposition 3.1.The continuity and the directional differentiability
of the D-gap function (3.1) directly follow from those of the regularized gap
function (2.1).Theorem 3.3.
Suppose that the set-valued mappingS
is continuous
in x, then the D-gap function Φαβ defined by
(3.1) is
continuous in x. Moreover, if the set-valued mapping S
is defined by
(2.15) and if
Slater's constraint qualification (2.16) holds, then the D-gap function Φαβ is
directionally differentiable in all direction d.Proof.
These
results directly follow from the definition of the D-gap functionΦαβ and Theorems 2.4 and 2.5.



---

*Source: 531361-2008-02-24.xml*