An equivalent formulation of a variational inequality

H.Dietrich Martin-Luther-University Halle-Wittenberg, Institute of Optimization and Stochastics, 06099 Halle Germany

In this paper, we prove a new equivalent formulation for a variational inequality and investigate their properties. The equivalent representation is transferable on implicit variational and quasivariational inequalities.

KEY WORDS: variational inequality, regularized gap function.

Mathematics Subject Classification 1991: Primary:49J40; Secondary: 35J85

Variational inequality theory has emerged as a powerful and effective technique to study a large number of problems arising in mechanics, optimization and control, equilibrium theory of transportation and economics, operations research, and other branches of mathematical and engineering sciences in a unified framework. The paper of Harker and Pang [4] provides an excellent survey in finitedimensional spaces. As known there exist under appropriate conditions various equivalent descriptions of variational inequalities by means of complementarity problems(Karamardian [10]), as optimality condition of an optimization problems with convex restrictions( Mancino and Stampacchia [13]), as a fixed point equation for a projection operator(Kinderlehrer and Stampacchia [11]), as a generalized equation with set-valued operators(Moré [14]) or as Wiener-Hopf equation ( Shi [17]) . In this paper, we show a new equivalent formulation of a variational inequality with beautiful properties. This is transferable on generalized and implicit variational as soon as quasivariational inequalities. Let Y be a Hilbert space, Y^{∗} its dual space, < ·, · > the duality pairing between the both spaces, (·, ·) the scalar product of Y, and ∥ · ∥, respectively ∥ · ∥_{∗}, the norm of Y, respectively Y^{∗}. We shall denote by F : Y → Y^{∗} the duality mapping on Y into Y^{∗}, with K ⊂ Y a nonempty closed and convex subset , by d_{K} : Y → IR the distance function of K and by P_{K} : Y → K the projection operator in Y on K, and by T : Y → Y^{∗} an operator.

Consider at first the following abstract variational inequality

find y ∈ K with < T y, z − y >≥ 0 ∀z ∈ K.  (1)

Define the function H : Y × Y^{∗} → IR

H(y, y^{∗}) := sup_{z∈K}[< y^{∗}, z − y > −\frac{1}{2}∥z − y∥^{2}],  (2)

which is related to a conjugate convex function, then we obtain the following representation

H(y, y^{∗}) = −\frac{1}{2} inf_{z∈K}[∥z − y∥^{2} − 2(F^{−1}y^{∗}, z − y) + ∥F^{−1}y^{∗}∥^{2} − ∥F^{−1}y^{∗}∥^{2}],

H(y, y^{∗}) = \frac{1}{2}∥y^{∗}∥_{∗}^{2} − \frac{1}{2}d_{K}^{2}(y + F^{−1}y^{∗}).  (3)

Remark 1 (i) By construction the function H is convex respectively y^{∗} for every y ∈ Y. (ii) The function H is continuously Fréchet differentiable for every (y, y^{∗}) ∈ Y × Y^{∗}, (iii) Always the inequality 0 ≤ H(y, y^{∗}) ≤ \frac{1}{2}∥y^{∗}∥_{∗}^{2} ∀y ∈ K, y^{∗} ∈ Y^{∗} holds.

Proof : The assertion (i) is obvious, (ii) compare Phelps [16] or Holmes [6]. The inequality (iii) we get on the one side from (2) with z = y ∈ K and on the other hand from (3).

Theorem 1 Let y ∈ K be a solution of the variational inequality

< T y, z − y >≥ 0 ∀z ∈ K,  (4)

if and only if y ∈ K is a solution of the equation

h(y) := H(y, −αT y) = 0  (5)

for some α > 0 when K is convex, while for K arbitrary, iff y is solution of (5) for any α > 0. A detailed description of (5) is

h(y) = \frac{α^{2}}{2} ∥T y∥_{∗}^{2} − \frac{1}{2}d_{K}^{2}(y − αF^{−1}T y).

Proof : 1) If y ∈ K is a solution of (4), then

0 ≥ α < −T y, z − y >  ∀z ∈ K, ∀α > 0
≥ H(y, −αT y) = sup_{z∈K}[< −αT y, z − y > −\frac{1}{2}∥z − y∥^{2}] ≥ 0,

also h(y) = 0, for an arbitrary set K.

2) If h(y) = 0 for y ∈ K and α > 0 is an arbitrary number, then we get

0 ≥< −αT y, z − y > −\frac{1}{2}∥z − y∥^{2} ∀z ∈ K.

With z = (1 − λ)y + λk, λ ∈ (0, 1], k ∈ K, we obtain

0 ≥ λ < −αT y, k − y > −\frac{λ^{2}}{2} ∥k − y∥^{2} ∀k ∈ K.

Dividing through λ and letting λ go to zero, we have for y ∈ K

< T y, k − y >≥ 0 ∀k ∈ K.

If h(y) = 0 for some y ∈ K and any α > 0, then the inequality

0 ≥< −T y, z − y > −\frac{1}{2α}∥z − y∥^{2} ∀z ∈ K

implies < T y, z − y >≥ 0 ∀z ∈ K, even for K arbitrary.

As an example we consider the following constrained minimizing problem

min_{z∈K} \frac{1}{2} ∫_{0}^{4}(z′)^{2}(x)dx = \frac{1}{2}∥w∥_{H_{0}^{1}}^{2} = 2.2091...  (6)

with the closed and convex set

K := {z ∈ H_{0}^{1}(0, 4) | z(x) ≤ Ψ(x) := x^{2} − 4x + 2 , x ∈ (0, 4)},

which is a convex obstacle problem. The cost function is strongly convex, consequently there exists a unique solution w of (6). By definition of the projection operator we have w(x) = P_{K}(0). How known

w(x) = \{ \begin{matrix}2(\sqrt{2} − 2)x : & 0 < x < \sqrt{2} \\ x^{2} − 4x + 2 : & \sqrt{2} ≤ x ≤ 4 − \sqrt{2} \\ 2(2 − \sqrt{2})x − 16 + 8\sqrt{2} : & 4 − \sqrt{2} < x < 4. \end{matrix}

compare the picture.

[figure: 3; 2; 1; -1; -2; -3; -1; 4; x; y; Ψ −; ^{\sqrt{2}}; 4 − \sqrt{2}]

The element w ∈ H_{0}^{1}(0, 4) is also the unique solution of the following variational inequality

< −w′′, z − w >_{H_{0}^{1}(0,4)}= ∫_{0}^{4}(−w′′(x))(z(x) − w(x))dx ≥ 0 ∀z ∈ K, (7)

and the unique solution of the scalar equation

h(w) = \frac{1}{2}∥w∥^{2} − \frac{1}{2}∥(I − P_{K})(w + F^{−1}w′′)∥^{2} = 0,  (8)

how one can immediately confirm.

Remark 2 If T : Y → 2^{Y^{∗}} is a set-valued operator, then the problem of finding y ∈ K such that y^{∗} ∈ T y and

< y^{∗}, z − y >≥ 0 ∀z ∈ K

is called the generalized variational inequality problem, see Fang [3] for instance, and may be equivalently described by

find y ∈ K such that y^{∗} ∈ T y and α > 0

h(y) := \frac{α^{2}}{2} ∥y^{∗}∥^{2} − \frac{1}{2}d_{K}^{2}(y − αF^{−1}y^{∗}) = 0.

Definition 1 (Hearn [5]) The gap function g : Y → IR ∪ {+∞} associated with the variational inequality (1) is defined by

g(y) = sup_{y∈K} < T y, z − y > .  (9)

Note that g(y) ≥ 0 ∀y ∈ K and that g(y) = 0 iff x is a solution to (1). The gap function g is in general a nondifferentiable function. We may consequently consider our function h from theorem 1 as a regularized gap function for the variational inequality (1). Consider the function h (5) with α = 1 and T : Y → Y^{∗} is a continuously Fréchet-differentiable operator, then we get for the Fréchet-derivative of h

h′(y) = T^{′∗}(y)F^{−1}T y − (I − T^{′∗}(y)F^{−1})F (I − P_{K})(y − F^{−1}T y). (10)

If additional the operator T ∈ L(Y, Y^{∗}) is linear and continuous, then from (10) we obtain

h′(y) = T^{∗}F^{−1}T y − (I − T^{∗}F^{−1})F (I − P_{K})(y − F^{−1}T y).  (11)

With (11) we get

< h′(y) − h′(z), y − z >= ∥T (y − z)∥_{∗}^{2} −

((I − P_{K})(y − F^{−1}T y) − (I − P_{K})(z − F^{−1}T z), (I − F^{−1}T)(y − z))

∀y, z ∈ Y (12)

and it follows that on the one hand

< h′(y) − h′(z), y − z >≤ ∥T ∥^{2}∥y − z∥^{2} ∀y, z ∈ Y  (13)

is valid and on the other hand

< h′(y) − h′(z), y − z >≥ −M∥y − z∥^{2}, with M > 0 ∀y, z ∈ Y. (14)

We prove a further property of the regularized gap function h.

Lemma 1 If additional the operator T : Y → Y^{∗} is strongly continuous, then the function ϕ := h + \frac{1}{2}∥ · ∥^{2} is weakly lower semicontinuous(w.l.s.c.).

Proof : By

lim inf_{w⇀y} ϕ(w) = lim inf_{w⇀y} sup_{z∈K}[< −T w, z − w > −\frac{1}{2}∥z − w∥^{2}] + \frac{1}{2}∥w∥^{2}
≥ sup_{z∈K} lim inf_{w⇀y}[< −T w, z − w > −\frac{1}{2}∥z − w∥^{2} + \frac{1}{2}∥w∥^{2}]
= h(y) + \frac{1}{2}∥y∥^{2} = ϕ(y),

the function ϕ is w.l.s.c.. The above result is also valid for so-called implicit variational inequalities, which was first considered by Bensousson and Lions [1], compare also Mosco [15] and Isac [7]. Let S : K → K be an operator, then for the function

H_{S}(y, y^{∗}) := sup_{z∈K}[< y^{∗}, z − Sy > −\frac{1}{2}∥z − Sy∥^{2}]  (15)

we get similarly to (2)

H_{S}(y, y^{∗}) = \frac{1}{2}∥y^{∗}∥_{∗}^{2} − \frac{1}{2}d_{K}^{2}(Sy + F^{−1}y^{∗}) ∀y ∈ Y, ∀y^{∗} ∈ Y^{∗}.  (16)

Corollary 1 Under the assumptions above the following both assertions are equivalent

(i) The element y ∈ K is a solution of the implicit variational inequality

< T y, z − Sy >≥ 0  ∀z ∈ K.  (17)

(ii) The element y ∈ K is a solution of the following equation for every α > 0

h_{S}(y) := H_{S}(y, −αT y) = \frac{α^{2}}{2} ∥T y∥_{∗}^{2} − d_{K}^{2}(Sy − αF^{−1}T y) = 0.  (18)

The proof follows immediately from the proof of theorem 1 if we consider S : K → K.

The implicit variational inequality (17)( with a closed and convex cone K ) is equivalent to the implicit complementarity problem

find y ∈ K :  T y ∈ K^{∗} and < T y, Sy >= 0.  (19)

Here by K^{∗} we denote the dual cone of K, that is

K^{∗} = {y^{∗} ∈ Y^{∗} | < y^{∗}, y >≥ 0 ∀y ∈ K}.

For the proof, see Isac [7] or Isac and Nemeth [8]. The implicit complementarity problems have applications in stochastic optimal control, see Bensousson and Lions [1], Mosco [15], Isac [7],Isac and Nemeth [8].

We can prove the following theorem for an abstract variational inequality.

Theorem 2 If the function f : K ⊂ Y → IR is a convex function, y^{∗} ∈ Y^{∗} and α > 0, then y ∈ K is a solution of the variational inequality

f(z) − f(y)+ < αy^{∗}, z − y >≥ 0 ∀z ∈ K  (20)

iff y ∈ K is solution of the following equation ( η ≥ 0 fixed )

H̃(y, −αy^{∗}) := α < y^{∗}, y > +f(y) − \frac{η}{2}∥y∥^{2} + Φ^{∗}(ηy − αF^{−1}y^{∗}) = 0. (21)

Here the function Φ^{∗} is the conjugate function of

Φ(·) = f(·) + \frac{η}{2}∥ · ∥^{2} + δ_{K}(·),

with δ_{K} : Y → IR ∪ {+∞} as the indicator function of K.

Proof : 1) If (20) is valid, then it follows for y ∈ K

0 ≥< −αy^{∗}, z − y > −f(z) + f(y) − \frac{η}{2}∥z − y∥^{2} ∀z ∈ K

and we allways obtain for an arbitrary finite function f on the set K

0 ≥ H̃(y, −αy^{∗}) = α < y^{∗}, y > +f(y) − \frac{η}{2}∥y∥^{2} +

+ sup_{z∈K}[(ηy − αF^{−1}y^{∗}, z) − f(z) − \frac{η}{2}∥z∥^{2}] ≥^{z=y∈K} 0,

also the equation (21).

2) Suppose y ∈ K and H̃(y, −αy^{∗}) = 0 for α > 0 and y^{∗} ∈ Y^{∗}, then with z = (1 − λ)y + λk ∈ K and k ∈ K, λ ∈ (0, 1] we get

0 ≥ λ < −αy^{∗}, k − y > −f(λk + (1 − λ)y) + f(y) − \frac{η}{2}λ^{2}∥k − y∥^{2} ∀k ∈ K,

further for convex functions f

0 ≥< −αy^{∗}, k − y > −f(k) + f(y) − \frac{η}{2}λ∥k − y∥^{2} ∀k ∈ K,

and by λ → +0 the variational inequality (20). For η > 0 the function Φ is strongly convex and consequently Φ^{∗} Fréchet-differentiable.

Consider now the generalized strong nonlinear quasivariational inequality problem,see Ding [2]. Given a set-valued mapping K : Y → 2^{Y} with the property that K(y) ⊂ Y is a nonempty, closed and convex subset of Y for every y ∈ Y and the mapping T : Y → 2^{Y^{∗}}. To find is y ∈ K(y) with y^{∗} ∈ T y such that

< y^{∗}, z − y > ≥ 0 ∀z ∈ K(y).  (22)

As application of theorem 1 on this case we get that (22) is equivalent to : find y ∈ K(y) such that the equation

ĥ(y) := \frac{α^{2}}{2} ∥y^{∗}∥_{∗}^{2} − \frac{1}{2}d_{K(y)}^{2}(y − αF^{−1}y^{∗}) = 0 and y^{∗} ∈ T y  (23)

is valid. In many important applications K(y) has the form

K(y) = G(y) + K

with a point-to-point mapping G : Y → Y and a fixed nonempty, closed and convex set K ⊂ Y. By Leichtnam [12] one get for the projection on the set K(y)

P_{K(y})(v) = G(y) + P_{K}(v − G(y)) ∀v ∈ Y.  (24)

From (24) we obtain by (23) for y^{∗} ∈ T y

ĥ(y) = \frac{α^{2}}{2} ∥y^{∗}∥_{∗}^{2}− \frac{1}{2}∥y−αF^{−1}y^{∗}−G(y)−P_{K}(y−αF^{−1}y^{∗}−G(y))∥^{2} = 0. (25)

The gap function g (9) and consequently also our regularized gap function h (5) provides a minimax formulation of the variational inequality problem, compare [5] and remark 1 (iii).

Corollary 2 The element ȳ ∈ K is a solution to the variational inequality (4) iff ȳ ∈ K solves

min_{y∈K} h(y) = min_{y∈K} max_{z∈K}[< T y, z − y > −\frac{1}{2}∥z − y∥^{2}]

and h(ȳ) = 0.

In analogous way we get for implicit variational and quasivariational inequalities a minimax formulation.

The optimal control problem for a variational inequality is to find an optimal control ū ∈ U_{ad} and an optimal state ȳ ∈ K for

min{J(y, u) | < T (y, u), z − y >≥ 0 ∀z ∈ K, y ∈ K, u ∈ U_{ad}}.

The problem is equivalent to

min{J(y, u) | h(y, u) = 0, y ∈ K, u ∈ U_{ad}},  (26)

where h is the associate regularized gap function of the variational inequality

h(y, u) = \frac{1}{2}∥T (y, u)∥_{∗}^{2} − \frac{1}{2}d_{K}^{2}(y − F^{−1}T (y, u)).

Unfortunately, it is impossible to apply the Lagrange multiplier rule, compare Jahn [9], on (26), since the regularity condition for the function h is just not fulfilled. But an application of the penalty technique is possible, similarly ( but more simple ) to Shi [18]. This we consider in a further paper. Acknowledgment The author wish to express his thanks to Prof.A.Göpfert and Prof.C.Zălinescu for many helpful comments and interesting remarks.

References

[1] A.Bensousson et J.L.Lions (1973) Nouvelle formulation de problèmes de contrôle impulsionnel et applications,C.R.Acad.Sci.Paris Sér.A-B 276,1189-1192.

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

[3] S.C.Fang and E.L.Peterson (1982) Generalized variational inequalities, J.Optim. Theory Appl. 38, 363-383.

[4] P.T.Harker and J.-S.Pang (1990) Finite-dimensional variational inequality and nonlinear complementarityproblems: A survey of theory, algorithms and applications, Mathem.Programming 48,161-220.

[5] D.W.Hearn (1982) The gap function of a convex program, Operations Research Letters 1, 67-71.

[6] R.Holmes (1972) A course on optimization and best approximation. Lecture Notes in Mathematics 257, Springer.

[7] G.Isac (1990) A special variational inequality and the implicit complementarity problem, J.Fac.Sci.Univ.Tokyo, Sect.IA,Math.37,109-127.

[8] G.Isac and A.B.Németh (1990) Projection methods, isotone projection cones, and the complementarity problem, J.Math.Anal.Appl. 153, 258-275.

[9] J.Jahn (1994) Introduction to the theory of nonlinear optimization, Springer- Verlag, Berlin.

[10] S.Karamardian (1971) Generalized complementarity problem, J.Optim. Theory Appl.8, 161-168.

[11] D.Kinderlehrer and G.Stampacchia (1980) An introduction to variational inequalities and their applications, Academic Press, New York.

[12] E.Leichtnam (1985) Interactions de singularités pour une classe d’équations á caractéristiques doubles, Ann.Inst.Fourier(Grenoble)35, 151-161.

[13] O.Mancino and G.Stampacchia (1972) Convex programming and variational inequalities, J.Optim.Theory and Appl.9, 3-23.

[14] J.J.Moré (1974) Coecivity conditions in nonlinear complementarity problems, SIAM Review 17, 1-16.

[15] U.Mosco (1980) On some nonlinear quasi-variational inequalities and implicit complementarity problems in stochastic control theory, Variational Inequalities and Complementarity Problems, Theory and Applications, (Eds. R.W.Cottle, F.Giannessi and J.L.Lions) Wiley & Sons, Chichester, 75-87.

[16] R.R.Phelps (1993) Convex functions, monotone operators and differentiability. Lecture Notes in Mathematics 1364, Springer.

[17] P.Shi (1991) Equivalence of variational inequalities with Wiener-Hopf equations, Proceedings Amer.Math.Soc.111, 339-346.

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