A smooth dual gap function to a class of quasivariational inequalities

by Helmut Dietrich Martin-Luther-University Halle-Wittenberg Institute of Optimization and Stochastics 06099 Halle Germany

Abstract

The aim of this paper is to construct a regularization of a gap function to a quasivariational inequality problem. The regularization may happen for example by means of Toland’s and Singer’s duality theory for d.c. functions and lead then to an everywhere finite and smooth dual gap function. The corresponding Fréchet-derivative of the dual gap function is calculable from the data of the quasivariational inequality problem.

1 Introduction

By means of a favorable gap function to variational inequalities and complementarity problems one may derive practicable solution methods and numerical algorithms, see for instance Noor, Noor, Rassias [22], Fukushima & Pang [10], Luo & Tseng [17]. If in a variational inequality problem the convex set does depend upon the solution, then the variational inequality is called a quasivariational inequality. Here the difficulty is that one must solve a family of variational inequalities as well as a fixed point problem at the same time. For applications and mathematical formulations to quasivariational inequalities, see Baiocchi & Capelo [3] and Giannessi & Maugeri [12], [12] also for the use of gap functions for quasivariational inequalities. The aim of the paper is to define and to investigate suitable gap functions for quasivariational inequalities, compare [11]. In this connection computable and differentiable gap functions are wanted. The usual gap function to a quasivariational inequality problem require a regularization for its application. Generally such a gap function is a nonconvex and nonsmooth function. By certain convexity assumptions one can observe various duality results of variational inequalities, see Mosco(1972) [18], Auchmuty(1989) [2] and Chen, Goh and Yang(1997) [5]. Mosco [18] indeed associate to a given variational inequality a dual inequality. Beyond it Chen, Goh and Yang [5] shown how the associated gap functions for the primal and the dual are related by dual Fenchel optimization problems. Our duality is meant in a different way and similar but not equal to the view of duality of Auchmuty [2] and further Larsson & Patriksson [16]. These authors develop a primal and dual gap function based on a Lagrange function. They obtain a saddle point characterization of a solution to the variational inequality by means of the Lagrange duality. Contrary we use the duality theory of Toland and Singer ([26], [27],[25]) for d.c. functions. As a method for the regularization of gap functions one can use the regularization of convex functions, see Barbu & Precupanu [4] 2.2.4. This method is used by Fukushima[9] for variational inequality problems and is also applicable to quasivariational inequalities for a partly regularization. For the general quasivariational inequalities and variational inequalities of the mixed type this regularization is not applicable. One can use the auxiliary principle technique of Noor( [21],[22]) to find equivalent differentiable optimization problems for such problems. If the operator T from the quasivariational inequality is a convex and closed multifunction, then we may obtain a smooth dual gap function by means of the duality theory of Toland and Singer. It is well known that the duality theory of Toland and Singer for d.c. functions possesses a regularizations effect, compare for example Hiriart-Urruty [15], Dietrich [7]. This effect is based on the fact, that an uniformly convex function possesses a Fréchet differentiable conjugate function in reflexive Banach spaces, see [28]. Let X be a Hilbert space and X^{∗} its dual; we denote by ⟨·, ·⟩ the duality product between X and X^{∗}, by (·, ·) the scalar product of X. Moreover Λ : X → X^{∗} is the duality mapping ( i.e. here the canonical isomorphism ) and we recall that

⟨Λx, y⟩ = (x, y) ∀x, y ∈ X.

Furthermore let K : X ⇝ X and T : X ⇝ X^{∗} be two convex and closed multifunctions associated with the quasivariational inequality . All the previous assumptions are supposed to be ensured in the sequel of the paper. We summarize them as assumption (H). Consider in this paper a general quasivariational inequality problem of the form

F ind x ∈ K(x) and x^{∗} ∈ T x : ⟨x^{∗}, z − x⟩ ≥ 0 ∀z ∈ K(x).  (1.1)

Let F_{K} ⊂ X be the fixed point set of the multifunction K, then by (H) it follows that F_{K} is a convex and closed set. We say that a function h : F_{K} × X^{∗} → [0, +∞) is a gap (or a merit) function for the problem (1.1) provided that x ∈ K(x) and x^{∗} ∈ T (x) satisfies (1.1) if and only if h(x, x^{∗}) = 0. Because of the properties of the gap functions one can then reformulate problem (1.1) as the following constrained minimization problem

min { h(x, x^{∗}) | x^{∗} ∈ T x and x ∈ F_{K}} = 0,  (1.2)

and apply for instance a feasible descent method to solve this minimization problem. There are many choices for a merit function. See Luo & Tseng [17] for complementarity problems, Fukushima [9] for a regularized gap function of variational inequalities and Fukushima & Pang [10] for a D-gap function of variational inequalities.

2 Gap functions for quasivariational inequalities

It is obvious to choose as a natural gap function

h(x, x^{∗}) = sup_{z∈K(x)} − ⟨x^{∗}, z − x⟩ , x^{∗} ∈ T x,  (2.1)

of the quasivariational inequality problem (1.1), compare for variational inequalities and complementarity problems Auslender [1], Hearn [13] and Shi [23]. The function h(x, ·) is convex and closed for every fixed x ∈ X as a supremum of a family of affine functions. On the other hand the function h(·, x^{∗}) is concave because of the convexity of the multifunction K, for every fixed x^{∗} ∈ X^{∗} as one can see immediately in the following. For

t ∈ [0, 1], ∀w_{i} ∈ (K − I)(x_{i}), i = 1, 2,

where I is the identity in the Hilbert space X, and

t(K − I)(x_{1}) + (1 − t)(K − I)(x_{2}) ⊂ (K − I)(tx_{1} + (1 − t)x_{2})

it follows namely that

h(tx_{1} + (1 − t)x_{2}, x^{∗}) = sup_{w∈(K−I)(tx_{1}+(1−t)x_{2})} − ⟨x^{∗}, w⟩
≥ − ⟨x^{∗}, tw_{1} + (1 − t)w_{2}⟩ ,

and therefore

h(tx_{1} + (1 − t)x_{2}, x^{∗}) ≥ th(x_{1}, x^{∗}) + (1 − t)h(x_{2}, x^{∗}).

The merit function h (2.1) is generally a nonsmooth function and possesses further the following required property

h(x, x^{∗}) ≥ 0 ∀x ∈ F_{K}, x^{∗} ∈ T (x),  (2.2)

and the following equivalence is true.

Theorem 2.1 The set of solutions of (1.1) is exact the set of solutions of the equation with the associated gap function, i.e.

\begin{matrix}x ∈ K(x) with x^{∗} ∈ T x \\ satisfies ⟨x^{∗}, z − x⟩ ≥ 0 ∀z ∈ K(x) \end{matrix} \} ⟺ \{ \begin{matrix}x ∈ K(x) satisfies h(x, x^{∗}) = 0 \\ and x^{∗} ∈ T x \end{matrix} (2.3)

Proof : (1.1) implies 0 ≥ h(x, x^{∗}) and we have h(x, x^{∗}) ≥ 0 by (2.1). From h(x, x^{∗}) = 0 with x ∈ K(x) and x^{∗} ∈ T x we infer immediately (1.1).

In analogous way to Fukushima [9] for variational inequalities we define a regularized gap function with the parameter α > 0 of the quasivariational inequality problem (1.1) by

h_{α}(x, x^{∗}) = sup_{z∈K(x)} [−α ⟨x^{∗}, z − x⟩ − \frac{1}{2}∥z − x∥^{2}] , x^{∗} ∈ X^{∗}, x ∈ X  (2.4)

This gap function for the quasivariational inequality represents a first regularization of the original gap function (1.1). How one can easily see, the gap function (2.4) is convex and everywhere partially Fréchet-differentiable in respect to the variable x^{∗} ∈ X^{∗} for every x ∈ X, whereas the function h_{α}(·, x^{∗}) is generally nonsmooth. The properties of this gap function we summarize in the sequel.

Theorem 2.2 Assume (H) and α > 0. Then

(i) h_{α}(x, x^{∗}) = \frac{α^{2}}{2} ∥x^{∗}∥_{∗}^{2} − \frac{1}{2}∥(I − P_{(K−I)(x)}(−αΛ^{−1}x^{∗})∥^{2}, x ∈ X, x^{∗} ∈ X^{∗}.(2.5)

( here, P_{(K−I)(x)}(·) is the projection in X onto the convex and closed set (K − I)(x) )

(ii) the gap function h_{α}(x, ·) is everywhere partially continuously Fréchet-differentiable in respect to x^{∗} ∈ X^{∗} for each x ∈ X with the Fréchet-derivative

\frac{∂h_{α}}{∂x^{∗}} = −αP_{(K−I)(x)}(−αΛ^{−1}x^{∗}).

(iii) h_{α}(x, x^{∗}) ≥ 0 ∀x ∈ F_{K}, x^{∗} ∈ T x.

(iv) h_{α}(x, x^{∗}) = 0, x ∈ F_{K}, x^{∗} ∈ T x\} ⟺ \{ \begin{matrix}x ∈ K(x), x^{∗} ∈ T x : \\ ⟨x^{∗}, z − x⟩ ≥ 0 ∀z ∈ K(x). \end{matrix}

Proof : The assertions (i)-(iii) and (iv) ’⟸’ are easily to prove. For the convenience of the reader we prove (iv) ’⟹’, compare also the attached proof of Fukushima [9] for the gap function of a variational inequality. From h_{α}(x, x^{∗}) = 0 for x ∈ K(x) and x^{∗} ∈ T x we obtain

0 ≥ −α ⟨x^{∗}, z − x⟩ − \frac{1}{2}∥z − x∥^{2} ∀z ∈ K(x),

and from that with z = tv + (1 − t)x,∀t ∈ (0, 1] and ∀v ∈ K(x)

0 ≥ −αt ⟨x^{∗}, v − x⟩ − \frac{t^{2}}{2} ∥v − x∥^{2}.

If we dividing the last inequality by t > 0 and letting go t to zero, then we get

x ∈ K(x), x^{∗} ∈ T x : ⟨x^{∗}, v − x⟩ ≥ 0 ∀v ∈ K(x).

Example 2.1

Consider a simple example for it that the gap function h_{α}(·, x^{∗}) is not differentiable. Put as quasivariational inequality problem:

find x ∈ K(x) with y ∈ T x and y(z − x) ≥ 0 ∀z ∈ K(x).

We define a convex and closed multifunction K : ℝ ⇝ ℝ by

K(x) = {y ∈ ℝ : k(x, y) := |x| + y − 1 ≤ 0} = (−∞, 1 − |x|], x ∈ ℝ.

The multifunction possesses the fixed point set F_{K} = (−∞, \frac{1}{2}] and for the gap function we get

h_{1}(x, y) = \{ \begin{matrix}\frac{1}{2}y^{2} & for & −y ≤ 1 − |x| − x \\ \frac{1}{2}y^{2} − \frac{1}{2}(|x| + x − y − 1)^{2} & for & 1 − |x| − x < −y \end{matrix} .

This function is not differentiable for example at the point (0, −2), for the right-side and the left-side derivative in respect to the variable x one get

\frac{∂h_{1}}{∂x} (+0, −2) = −2 and \frac{∂h_{1}}{∂x} (−0, −2) = 0.

In many important applications K(x) has the form

K(x) = g(x) + K,  (2.6)

with a mapping g : X → X and a convex and closed set K ⊂ X . Then the multifunction K(x) = g(x) + K is not necessary convex because the operator g can be nonlinear. In this case we have the following known result, which follows directly from the definition of the projection.

Lemma 2.1 ( [19]) If K(x) is of the type (2.6), then for any x, y ∈ X

P_{K(x)}(y) = g(x) + P_{K}(y − g(x)).  (2.7)

Assume additional that the mapping g is Fréchet-differentiable and consider (2.7) then we obtain from (2.5)

h_{α}(x, x^{∗}) = \frac{α^{2}}{2} ∥x^{∗}∥_{∗}^{2} − \frac{1}{2}∥(I − P_{K})(x − g(x) − αΛ^{−1}x^{∗})∥^{2} x ∈ X, x^{∗} ∈ T x. (2.8)

The gap function h_{α} is in this case everywhere Fréchet-differentiable and its Fréchetderivative is

hα^{′}(x, x^{∗}) = ( \begin{matrix}(g′^{∗}(x) − I)Λ(I − P_{K})(x − g(x) − αΛ^{−1}x^{∗}) \\ α [x − g(x) − P_{K}(x − g(x) − αΛ^{−1}x^{∗})] \end{matrix} ) .  (2.9)

In this case the gap function (2.8) is in fact completely regularized and is as well used for the investigation of quasivariational inequalities, see for example Noor [19],[20], Ding [8], Siddiqi and Ansari [24], Dietrich [6]. In the following we but investigate further the general case of an arbitrary convex and closed multifunction K : X ⇝ X. Then one can see from theorem 2.2 in the sequel that the gap function is a d.c. function, i.e. a difference of two convex functions. Define the following function Φ_{K} : X × X → ℝ by

Φ_{K}(x, y) = \frac{1}{2} min_{z∈K(x)} ∥y − z∥^{2} = \frac{1}{2}∥y − P_{K(x)}(y)∥^{2}.  (2.10)

This function is as the essential part of the gap function (2.5) a generally nonsmooth function. More precisely, Φ_{K}(x, ·) is everywhere Fréchet-differentiable for fixed x ∈ X and Φ_{K}(·, y) is in general nonsmooth for fixed y ∈ X, compare theorem 2.2.

Lemma 2.2 Suppose (H), then

(i) the function Φ_{K} is a convex and continuous function and satisfies

Φ_{K}(tx_{1} + (1 − t)x_{2}, ty_{1} + (1 − t)y_{2}) ≤ tΦ_{K}(x_{1}, y_{1}) + (1 − t)Φ_{K}(x_{2}, y_{2})

−\frac{t}{2}(1 − t)∥(y_{1} − P_{K(x_{1})}y_{1}) − (y_{2} − P_{K(x_{2})}y_{2})∥^{2}  (2.11)

for all t ∈ [0, 1], y_{1}, y_{2} ∈ X and x_{1}, x_{2} ∈ X, (ii) if (x^{∗}, y^{∗}) ∈ ∂Φ_{K}(x, y) is fulfilled, then

Φ_{K}(ξ, η) − Φ_{K}(x, y) ≥< x^{∗}, ξ − x > + < y^{∗}, η − y >

+\frac{1}{2} ∥(η − P_{K(ξ)}(η)) − (y − P_{K(x)}(y))∥^{2}  (2.12)

for all ξ ∈ X,η ∈ X and y^{∗} = Λ(y − P_{K(x)}y), Proof : Since K is a convex multifunction we may infer

tK(x_{1}) + (1 − t)K(x_{2}) ⊂ K(tx_{1} + (1 − t)x_{2})

for all t ∈ [0, 1] and x_{1}, x_{2} ∈ X. Consequently we can put z = tz_{1} + (1 − t)z_{2} ∈ K(tx_{1} + (1 − t)x_{2}) with z_{i} ∈ K(x_{i}), i = 1, 2. We obtain

Φ_{K}(tx_{1} + (1 − t)x_{2}, ty_{1} + (1 − t)y_{2}) ≤ \frac{1}{2}∥t(y_{1} − z_{1}) + (1 − t)(y_{2} − z_{2})∥^{2}
≤ \frac{t}{2}∥y_{1} − z_{1}∥^{2} + \frac{1 − t}{2}∥y_{2} − z_{2}∥^{2}

−\frac{t}{2}(1 − t)∥(y_{1} − z_{1}) − (y_{2} − z_{2})∥^{2}.

In the last inequality we set z_{i} = P_{K(x_{i})}, i = 1, 2, then we obtain (2.11). To prove (2.12) we put in (2.11) x_{1} = ξ, y_{1} = η, x_{2} = x, y_{2} = y and have

Φ_{K}(x + t(ξ − x), y + t(η − y)) ≤ tΦ_{k}(ξ, η) + (1 − t)Φ_{K}(x, y)
− \frac{t}{2}(1 − t) ∥(η − P_{K(ξ)}(η)) − (y − P_{K(x)}(y))∥^{2} ,

ΦK^{′}(x, y; ξ − x, η − y) ≤ Φ_{K}(ξ, η) − Φ_{K}(x, y) − \frac{1}{2} ∥(η − P_{K(ξ)}(η)) − (y − P_{K(x)}(y))∥^{2} .

Here ΦK^{′} is the directional derivative of Φ_{K}. If (x^{∗}, y^{∗}) is a subgradient of Φ_{K} at (x, y), then

Φ_{K}(ξ, η) − Φ_{K}(x, y) ≥< x^{∗}, ξ − x > + < y^{∗}, η − y >

+\frac{1}{2} ∥(η − P_{K(ξ)}(η)) − (y − P_{K(x)}(y))∥^{2} ,

thus (2.12) is true and y^{∗} = Λ(y − P_{K(x)}y) because of the Fréchet-differentiability of Φ_{K}(x, ·).

Remark 2.1 The gap function (2.4) possesses the representation

h_{α}(x, x^{∗}) = \frac{α^{2}}{2} ∥x^{∗}∥_{∗}^{2} − Φ_{(K−I)}(x, −αΛ^{−1}x^{∗})),  (2.13)

compare (2.5). h_{α}(·, x^{∗}) is a nonsmooth and concave function on X for every fixed x^{∗} ∈ X^{∗} and h_{α}(x, ·) is a smooth and convex function on X^{∗} for every fixed x ∈ X, see theorem 2.2.

3 Application of the duality theory of Toland and Singer

Solving the quasivariational inequality problem (1.1) is equivalent to solving the global minimization problem

min_{x^{∗}∈T x,x∈F_{K}} h_{α}(x, x^{∗}) = 0  (3.1)

with the gap function h_{α}. This is a nonsmooth, nonconvex and constrained minimization problem. The nature of the nonconvexity of the problem (3.1) is essential determined by the set-valued operator T. We can (3.1) interpret as a d.c. minimization after the statements above, if T : X → X^{∗} is a linear and continuous or affine operator or T : X ⇝ X^{∗} is more general a convex multifunction. For minimization problems of a d.c. function one may conduct a regularization by means of Toland’s and Singer’s duality theory, Toland [26], Singer [25]. If the d.c. function is representable by a suitable difference of two strongly ( at least uniformly ) convex functions (this is always possible), then the attached conjugate functions are Fréchet-differentiable such that the dual problem is a smooth d.c. minimization problem on the whole space, see Zălinescu [28]. The problem is just the possibility of the exact calculation of the associated conjugate functions. Let now T : X ⇝ X^{∗} be a convex and closed multifunction. Consider beside T : X ⇝ X^{∗} the multifunction T_{F_{K}} : F_{K} ⇝ X^{∗} with T_{F_{K}}(x) = T (x) ∀x ∈ F_{K}. Then T_{F_{K}} is also a convex and closed multifunction, because F_{K} is convex and closed. Introduce the functions f : X × X^{∗} → ℝ ∪ {+∞} and g : X × X^{∗} → ℝ by

f(x, x^{∗}) = \frac{1}{2}∥x∥^{2} + \frac{1 + α^{2}}{2} ∥x^{∗}∥_{∗}^{2} + δ_{GraphT_{F}_{K}}(x, x^{∗})  (3.2)

and

g(x, x^{∗}) = \frac{1}{2}∥x∥^{2} + \frac{1}{2}∥x^{∗}∥_{∗}^{2} + Φ_{(K−I)}(x, −αΛ^{−1}x^{∗})  (3.3)

with the domains domf = Graph T_{F}_{K} and domg = X × X^{∗}. Both functions are strongly convex on X × X^{∗}, f is a closed and g a continuous function and

h_{α}(x, x^{∗}) = f(x, x^{∗}) − g(x, x^{∗}),

with the convention (+∞) − (+∞) = +∞, compare Hiriart-Urruty [14], such that (3.1) is equivalent to

min_{x^{∗},x} [f(x, x^{∗}) − g(x, x^{∗})] .  (3.4)

Lemma 3.1 Let T : X ⇝ X^{∗} be a convex and closed multifunction. Then the conjugate function to f (3.2) is

f^{∗}(y^{∗}, y) = \frac{1}{2(1 + α^{2})}∥y∥^{2} + \frac{1}{2}∥y^{∗}∥_{∗}^{2} − \frac{1}{2} ∥(I − P_{GraphT_{F}_{K}})(Λ^{−1}y^{∗}, \frac{Λy}{1 + α^{2}} )∥_{1}^{2} (3.5)

with domf^{∗} = X^{∗} × X and

∥(a, b^{∗})∥_{1}^{2} := ∥a∥^{2} + (1 + α^{2})∥b^{∗}∥_{∗}^{2} ∀a ∈ X, b^{∗} ∈ X^{∗}.

The conjugate function f^{∗} is everywhere continuously Fréchet-differentiable with the derivative

f^{∗}′(y^{∗}, y) = P_{GraphT_{F}_{K}}(Λ^{−1}y^{∗}, \frac{Λy}{1 + α^{2}} ).  (3.6)

Proof : By definition, we get

f^{∗}(y^{∗}, y) = sup_{x∈F_{K},x^{∗}∈T x} [⟨x^{∗}, y⟩ + ⟨y^{∗}, x⟩ − \frac{1}{2}∥x∥^{2} − \frac{1 + α^{2}}{2} ∥x^{∗}∥_{∗}^{2}]

and further

f^{∗}(y^{∗}, y) = \frac{1}{2(1 + α^{2})}∥y∥^{2} + \frac{1}{2}∥y^{∗}∥_{∗}^{2} − \frac{1}{2} inf_{(x,x^{∗})∈GraphT_{F_{K}}} ∥(x, x^{∗}) − (Λ^{−1}y^{∗}, \frac{Λy}{1 + α^{2}} )∥_{1}^{2}

hereby (3.5) and immediately (3.6).

Lemma 3.2 For the conjugate function of g (3.3) one get

g^{∗}(y^{∗}, y) = \frac{1}{2}∥y∥^{2} + \frac{1}{2}∥y^{∗}∥_{∗}^{2} − \frac{1}{2} ∥(I − P_{Graph(K−I)})(Λ^{−1}y^{∗}, −αy)∥_{2}^{2}  (3.7)

with

∥(a, b)∥_{2}^{2} := ∥a∥^{2} + \frac{1}{1 + α^{2}} ∥b∥^{2} ∀a, b ∈ X,

where domg^{∗} = X × X^{∗} and g^{∗} is also everywhere continuously Fréchet-differentiable with the derivative

g^{∗}′(y^{∗}, y) = ( 0_{\frac{Λy}{1+α^{2}}} ) + ( −I_{\frac{αΛ}{1+α^{2}}} ) P_{Graph(K−I)}(Λ^{−1}y^{∗}, −αy).  (3.8)

Proof : We determine the conjugate function and get

g^{∗}(y^{∗}, y) = sup ; \begin{matrix}x^{∗} ∈ X^{∗} \\ (x, w) ∈ Graph(K − I) \end{matrix} [⟨x^{∗}, y⟩ + ⟨y^{∗}, x⟩ − \frac{1}{2}∥x∥^{2} − \frac{1}{2}∥x^{∗}∥_{∗}^{2} − \frac{1}{2}∥w + αΛ^{−1}x^{∗}∥^{2}] ,

further

g^{∗}(y^{∗}, y) = \frac{1}{2}∥y∥^{2} + \frac{1}{2}∥y^{∗}∥_{∗}^{2} − \frac{1}{2} inf_{(x,w)∈Graph(K−I)} ∥( x_{\frac{w}{\sqrt{1+α^{2}}}} ) − ( Λ^{−1}y^{∗}_{\frac{−αy}{\sqrt{1+α^{2}}}} )∥^{2} .

If we use the above new definition of the norm on the product space, we obtain the equation (3.7) and therefore (3.8).

We recall that for proper functions F, G : X → ℝ ∪ {+∞} with G = G^{∗∗} by Toland’s and Singer’s duality theory the following formula

inf_{x∈X}[F (x) − G(x)] = inf_{x^{∗}∈X^{∗}}[G^{∗}(x^{∗}) − F^{∗}(x^{∗})]

is valid with the convention ∞ − ∞ = +∞, see Toland [27].

Theorem 3.1 Suppose (H), then

inf_{x∈F_{K},x^{∗}∈T x} h_{α}(x, x^{∗}) = inf_{(y,y^{∗})∈X×X^{∗}}[g^{∗} − f^{∗}]  (3.9)

with

g^{∗} − f^{∗} = \frac{α^{2}}{2(1 + α^{2})}∥y∥^{2} − \frac{1}{2} ∥(I − P_{Graph(K−I)})(Λ^{−1}y^{∗}, −αy)∥_{2}^{2}
+ \frac{1}{2} ∥(I − P_{GraphT_{F_{K}}})(Λ^{−1}y^{∗}, \frac{Λy}{1 + α^{2}} )∥_{1}^{2} .

Further we conclude

(i) if (\underline{x}, \underline{x}^{∗}) with \underline{x} ∈ K(\underline{x}) and \underline{x}^{∗} ∈ T \underline{x} is a solution of the quasivariational inequality problem (1.1), then

min_{GraphT_{F_{K}}} h_{α}(x, x^{∗}) = h_{α}(\underline{x}, \underline{x}^{∗}) = min_{y^{∗},y} [g^{∗} − f^{∗}] = g^{∗}(\underline{y}^{∗}, \underline{y}) − f^{∗}(\underline{y}^{∗}, \underline{y}) = 0 (3.10)

and (\underline{y}^{∗}, \underline{y}) solves the dual problem provided that (\underline{y}^{∗}, \underline{y}) ∈ ∂g(\underline{x}, \underline{x}^{∗}). (ii) if (\underline{y}^{∗}, \underline{y}) is a solution of the dual problem

min_{y^{∗},y} [g^{∗} − f^{∗}] = g^{∗}(\underline{y}^{∗}, \underline{y}) − f^{∗}(\underline{y}^{∗}, \underline{y}) = 0,

then the equality (3.10) is true and (\underline{x}, \underline{x}^{∗}) = f^{∗}′(\underline{y}^{∗}, \underline{y}) solves the quasivariational inequality (1.1).

Proof : From the application of Toland and Singer’s duality theory and by the consideration of lemma 3.1 and lemma 3.2 it follows immediately the duality relation (3.9). The assertion (i) one obtain from [27] theorem 2.3. Finally we prove (ii). If (\underline{y}^{∗}, \underline{y}) is a solution of the dual problem, then we denote with (\underline{x}, \underline{x}^{∗}) = f^{∗}′(\underline{y}^{∗}, \underline{y}), see (3.6), and we have by (3.9)

inf_{(x,x^{∗})∈Graph T_{F_{K}}} h_{α}(x, x^{∗}) = g^{∗}(\underline{y}^{∗}, \underline{y}) − f^{∗}(\underline{y}^{∗}, \underline{y}) = 0.

Since

g^{∗}(y^{∗}, y) − f^{∗}(y^{∗}, y) ≥ g^{∗}(\underline{y}^{∗}, \underline{y}) − f^{∗}(\underline{y}^{∗}, \underline{y})

for all (y^{∗}, y) ∈ X^{∗} × X, it follows (\underline{x}, \underline{x}^{∗}) ∈ ∂g^{∗}(\underline{y}^{∗}, \underline{y}). Hence

f(\underline{x}, \underline{x}^{∗}) − g(\underline{x}, \underline{x}^{∗}) = g^{∗}(\underline{y}^{∗}, \underline{y}) − f^{∗}(\underline{y}^{∗}, \underline{y}),

and therefore (\underline{x}, \underline{x}^{∗}) is a solution of (1.1) by theorem 2.2 (iii) and (iv).

Example 3.1

Consider example 2.1 for the special case

find x ∈ K(x) = (−∞, 1 − |x|] such that (x − 2)(z − x) ≥ 0 ∀z ∈ K(x).

Here the fixed point set of the convex multifunction K is F_{K} = (−∞, \frac{1}{2}], the operator T x = x−2 and the unique solution of the quasivariational inequality problem is \underline{x} = \frac{1}{2} with \underline{x}^{∗} = T \underline{x} = −\frac{3}{2} . We define the functions(α := 1 )

F (z, y) := \frac{1}{2} ∥(I − P_{Graph(K−I)}(z, −y)∥_{2}^{2}

and

G(z, y) := \frac{1}{2} ∥(I − P_{Graph T_{F_{K}}})(z, \frac{y}{2})∥_{1}^{2} .

Then we obtain the following representations

F (z, y) = \{ \begin{matrix}0 & for & \begin{matrix}\{z ≤ 0 ∧ −y ≤ 1\}∨ \\ \{z > 0 ∧ −y ≤ −2z + 1\} \end{matrix} \\ \frac{1}{4}(y + 1)^{2} & for & z ≤ 0 ∧ −y > 1 \\ \frac{1}{2}z^{2} + \frac{1}{4}(y + 1)^{2} & for & z > 0 ∧ −y ≥ z + 1 \\ \frac{1}{12}(2z − y − 1)^{2} & for & z > 0 ∧ −y < z + 1 ∧ −y > −2z + 1 \end{matrix}

and

G(z, y) = \{ \begin{matrix}0 & for & z ≤ \frac{1}{2} ∧ y = 2z − 4 \\ \frac{1}{2}(z − \frac{1}{2})^{2} + \frac{1}{4}(y + 3)^{2} & for & y ≥ −z − \frac{5}{2} \\ \frac{1}{12}(2z − y − 4)^{2} & for & y ≠ 2z − 4 ∧ y < −z − \frac{5}{2}. \end{matrix}

One can easily observe that the associated function g (3.3) is differentiable at the point (\underline{x}, \underline{x}^{∗}) = (\frac{1}{2}, \frac{−3}{2}) with the derivative g′(\frac{1}{2}, \frac{−3}{2}) = (\frac{7}{2}, −3). By theorem 3.1(i) (\underline{y}^{∗}, \underline{y}) = (\frac{7}{2}, −3) is the solution of the dual problem by Toland and Singer. The dual cost function we denote with Ψ := g^{∗} − f^{∗} and obtain for it

Ψ(z, y) = \frac{1}{4}y^{2} − F (z, y) + G(z, y),

Ψ(z, y) ≥ 0 ∀(z, y) ∈ ℝ^{2} and Ψ(\frac{7}{2}, −3) = 0. The dual gap function Ψ is an everywhere differentiable and nonnegative function.

References

[1] A.Auslender,”Optimisation: Méthodes Numériques”, Masson, Paris, 1976.

[2] G.Auchmuty: Variational principles for variational inequalities,Numer. Funct.Anal. and Optim. 10 (1989),863-874.

[3] C.Baiocchi and A.Capelo:”Variational and quasivariational inequalities”, Wiley & Sons, NewYork, 1984.

[4] V.Barbu and Th.Precupanu:”Convexity and Optimization in Banach Spaces”, Sijthoff & Nordhoff, 1978.

[5] G.Y.Chen, C.J.Goh and X.Q.Yang: On gap functions and duality of variational inequality problems, J.Math.Anal.Appl. 214 (1997), 658-673.

[6] H.Dietrich: Optimal control problems for certain quasivariational inequalities, submitted by Optimization.

[7] H.Dietrich: An application of the duality theory of Toland to a problem of optimal control,J.Math.Anal.Appl. 153 (1990),301-308.

[8] X.P.Ding: Generalized strongly nonlinear quasivariational inequalities, J.Math.Anal.Appl. 173 (1993),577-587.

[9] M.Fukushima: Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,Mathematical Programming 53 (1992), 99-110.

[10] M.Fukushima and J.-S.Pang: Minimzing and stationary sequences of merit functions for complementarity problems and variational inequalities, ”Complementarity and variational problems, State of the art”, Ed.by M.C.Ferris and J.-S. Pang,p.204-225, Proceedings of the International Conference on Complementarity Problems, Baltimore, Maryland, Nov.1-4, 1995, SIAM Philadelphia, 1997.

[11] F.Giannessi: Separation of sets and gap functions for quasi variational inequalities,in [12], 101-121.

[12] F.Giannessi and A.Maugeri(Eds.): ”Variational Inequalities and Network Equilibrium Problems”, Plenum Press, New York, 1995.

[13] D.W.Hearn: The gap function of a convex program,Oper.Res.Lett., 1 (1982), 67-71.

[14] J.-B.Hiriart-Urruty: A general formula on the conjugate of the difference of functions,Canad. Math.Bull. 29 (4)(1986),482-485.

[15] J.-B.Hiriart-Urruty: Generalized differentiability, duality and optimization for problems dealing with differences of convex functions, ”Lecture Notes in Econ. and Mathem.Systems” 256 (1985), 37-70.

[16] T.Larsson and M.Patriksson: A class of gap functions for variational inequalities, Math.Program. 64 (1994), 53-79.

[17] Z.-Q.Luo and P.Tseng: A new class of merit functions for the nonlinear complementarity problem,”Complementarity and variational problems, State of the art”, Ed.by M.C.Ferris and J.-S. Pang, p. 204-225, Proceedings of the International Conference on Complementarity Problems, Baltimore, Maryland, Nov.1-4, 1995, SIAM Philadelphia, 1997.

[18] U.Mosco: Dual variational inequalities,J.Math.Anal.Appl. 40 (1972),202-206.

[19] M.A.Noor: An iterative scheme for a class of quasivariational inequalities, J.Math.Anal.Appl. 110 (1985),463-468.

[20] M.A.Noor: Iterative algorithms for quasivariational inequalities, Panamerican Mathematical J. 2 (1992),17-26.

[21] M.A.Noor : Equivalence of differentiable optimization problems for variational inequalities, J.Natural Geometry 8 (1995),117-128.

[22] M.A.Noor, K.I.Noor and Th.M.Rassias : Some aspects of variational inequalities,J.Comput.Appl.Math. 47 (1993),285-312.

[23] S.Shi: Optimal control of strongly monotone variational inequalities, SIAM J.Control and Optim. 25 (1988),274-290.

[24] A.H.Siddiqi and Q.H.Ansari: Strongly nonlinear quasivariational inequalities, J.Math.Anal.Appl. 149 (1990),444-450.

[25] I.Singer: A Fenchel-Rockafellar type duality theorem for maximization, Bull.Australian Math.Soc. 20 (1979),193-198.

[26] J.F.Toland: Duality in non-convex optimization, J.Math.Anal.Appl. 66 (1978),399-415.

[27] J.F.Toland: A duality principle for non-convex optimisation and the calculus of variations,Arch.Rat.Mech.Anal. 71 /1(1979),41-61.

[28] C.Zălinescu: On uniformly convex functions,J.Math.Anal.Appl. 95( 1983), 344-374.