Lobachevskii Journal of Mathematics Vol. 2, 1999, 3-9 \begin{matrix}c \\ ◯ \end{matrix}Igor V. Konnov

Igor V. Konnov

COMBINED RELAXATION METHODS FOR VARIATIONAL INEQUALITY PROBLEMS OVER PRODUCT SETS ^{1} (submitted by A.V.Lapin)

1. Introduction

The variational inequality problem (VI for short) is the problem of finding

u^{∗} ∈ U such that ⟨G(u^{∗}), u − u^{∗}⟩ ≥ 0 ∀u ∈ U,  (1.1)

where U is a nonempty closed convex set in the n-dimensional Euclidean space R^{n}, G is a mapping from U into R^{n}, ⟨·, ·⟩ denotes the scalar product. This problem has many applications in mathematical physics, economics and operations research. As a result, both theory and solution methods for VI’s are extensively investigated (e.g., see [1]– [3] and references therein).

There exist a number of solution methods for VI’s. However, most of them either require restrictive assumptions that G be strictly monotone or have low convergence. A few approaches to constructing rather simple and rapidly convergent methods which allow one to find a solution of VI under weaker assumptions have been designed. One approach is to make use of the double projection iterations, in other words, the extragradient method (see [4]). A second approach is to apply a descent method with respect to some artifical merit function (see [5]). A third general approach was proposed in [6]. Following this approach, each iteration involves an auxiliary procedure for computing iteration parameters in order to guarantee the monotone decrease of the Euclidean distance to all solutions. In [6], several auxiliary procedures for finding the parameters were proposed, they being based on an iteration of the projection method, the Frank-Wolfe type method, and the Newton method. All these procedures include an Armijo type linesearch, which requires no a priori knowledge about the problem under solution. Next, a general combined relaxation framework with various auxiliary procedures was proposed in [7, 8]. The methods from [6]–[8] are convergent if there exists a solution for the dual form of VI. This condition is weaker than the pseudomonotonicity of G.

The first purpose of this paper is to give a new general framework for constructing iterative methods for VI which modifies and combines ideas contained in the methods from [6] –[9].

The second purpose of this paper is to adjust the methods for VI’s over product sets. Namely, in this paper we consider the following general class of VI’s. Denote by M the set of indexes {1, …, m}. For every u ∈ R^{n}, let

1Key words: Variational inequalities, product sets, decomposition scheme, combined relaxation methods.

u = (u_{s} | s ∈ M)

where u_{s} ∈ R^{n_{s}} for s ∈ M, i.e. n = ∑_{s∈M} n_{s}. Accordingly, let

U = ∏_{s∈M} U_{s}  (1.2)

where U_{s} ⊆ R^{n_{s}} for s ∈ M. The problem is to find an element u^{∗} ∈ U such that

∑_{s∈M}⟨G_{s}(u^{∗}), u_{s} − u_{s}^{∗}⟩ ≥ 0 ∀u_{s} ∈ U_{s}, s ∈ M;  (1.3)

where G_{s} is a mapping from U into R^{n_{s}} for s ∈ M. It is clear that VI (1.3) is equivalent to VI (1.1) with U having the form (1.2), G having the form

G = (G_{s} | s ∈ M).  (1.4)

VI of the form (1.3) has a number of applications, including the Nash equilibrium problem of an m-person non-cooperative game, traffic equilibrium and spatial price equilibrium problems (e.g., see [2, 10, 11]). Note that there is no loss of generality in considering VI (1.3), since (1.3) reduces to (1.1) in case m = 1.

Typically, VI of the form (1.3) is quite large, hence a decomposition approach is suitable to find its solution. Thus, we intend to give a modification of the methods from [6] –[8], which essentially exploites the decomposable structure of VI and allows one to simplify its implementation.

In what follows, we denote by U^{∗} the solution set of VI (1.3). As usual, ∥u∥ denotes the Euclidean norm of a vector u, Z_{+} denotes the set of non-negative integers. We use superscripts to denote different vectors. Subscripts are used to denote different scalars or components of vectors. Also, set

(u∥v_{s}) = (u_{1}, …, u_{s−1}, v_{s}, u_{s+1}, …, u_{m}).

We denote by π_{V} (u) the projection of a point u onto a set V.

2. Description of the Method

First we give some definitions and the blanket assumptions of this paper.

Let V be a subset of some Euclidean space E and let Q be a mapping defined on V. The mapping Q is said to be locally Lipschitz continuous on V if it is Lipschitz continuous on each bounded subset of V.

Recall that the mapping Q is said to be

(a) strongly monotone with constant τ > 0 if, for each pair of points u, v ∈ V, we have

⟨Q(u) − Q(v), u − v⟩ ≥ τ∥u − v∥^{2};

(b) monotone if, for each pair of points u, v ∈ V, we have

⟨Q(u) − Q(v), u − v⟩ ≥ 0;

(c) pseudomonotone if, for each pair of points u, v ∈ V, we have

⟨Q(v), u − v⟩ ≥ 0 implies ⟨Q(u), u − v⟩ ≥ 0.

It is clear that every strongly monotone mapping is monotone and that every monotone mapping is pseudomonotone, but the reverse assertions are not true.

So, we shall consider VI of the form (1.3) where the feasible set U is defined by (1.2). We assume throughout that, for each s ∈ M, U_{s} is a convex closed set in R^{n_{s}}, G_{s} is a locally Lipschitz continuous mapping from U into R^{n_{s}}. We also assume throughout that U^{∗} ≠ ∅ and that, for every u ∈ U,

∑_{s∈M}⟨G_{s}(u), u_{s} − u_{s}^{∗}⟩ ≥ 0 ∀u^{∗} ∈ U^{∗}.  (2.1)

Note that (2.1) holds if the mapping G, defined by (1.4), is monotone or pseudomonotone.

Now we describe a method for solving VI under these assumptions.

Method Step 0 (Initialization): Choose a point u^{0} ∈ U, a family of mappings {T_{k,s} : U_{s} × U_{s} → R^{n_{s}}} such that, for each s ∈ M and for each k = 0, 1, …,

(a) T_{k,s}(x, ·) is strongly monotone with constant τ′ > 0 and Lipschitz continuous with constant τ′′ < ∞ for every x ∈ U_{s};

(b) T_{k,s}(x, x) = 0 for every x ∈ U_{s}. Choose numbers α ∈ (0, 1), β ∈ (0, 1), γ ∈ (0, 2), θ̃ > 0, a sequence {ε_{l}} ↘ 0. Set k = 0, λ(k) = 1.

Step 1 (Auxiliary procedure):

Step 1.0 : Set s = 1, l = λ(k).

Step 1.1 : Find d(s) as the smallest number j in Z_{+} such that

⟨G_{s}(u^{k}∥z_{s}^{k,j}), z_{s}^{k,j} − u_{s}^{k}⟩ ≤ α⟨G_{s}(u^{k}), z_{s}^{k,j} − u_{s}^{k}⟩,  (2.2)

where z_{s}^{k,j} is a solution of the auxiliary problem of finding

z̄ ∈ U_{s} such that ⟨G_{s}(u^{k}) + (θ̃β^{j})^{−1}T_{k,s}(u_{s}^{k}, z̄), u_{s} − z̄⟩ ≥ 0 ∀u_{s} ∈ U_{s}. (2.3)

Step 1.2: Set θ_{k,s} = β^{d(s)}θ̃, v_{s}^{k} = z_{s}^{k,d(s)}. If ∥u_{s}^{k} − v_{s}^{k}∥ ≤ ε_{l}, then σ_{k,s} = 0. Otherwise set v^{k} = (u^{k}∥v_{s}^{k}), g_{s}^{k} = G_{s}(v^{k}), σ_{k,s} = ⟨g_{s}^{k}, u_{s}^{k} − v_{s}^{k}⟩ and go to Step 2.

Step 1.3: If s < m, set s = s + 1 and go to Step 1.1. Otherwise, set u^{k+1} = v^{k} = u^{k}, σ_{k} = σ_{k,m}, g^{k} = 0, λ(k + 1) = l + 1, go to Step 1. (The iteration has been completed.)

Step 2 (Main iteration): Compute

g_{i}^{k} ∈ G_{i}(v^{k}) for i ∈ M, i ≠ s.

Set σ_{k} = σ_{k,s}/∥g^{k}∥^{2}, λ(k + 1) = l,

u_{i}^{k+1} = π_{U_{i}}(u_{i}^{k} − γσ_{k}g_{i}^{k}), i ∈ M.  (2.4)

Go to Step 1. (The iteration has been completed.)

First we note that there exist a number of rules to choose the family {T_{k,s}} satisfying conditions (a), (b). For instance, we can set

T_{k,s}(x, y) = A_{k,s}(y − x)  (2.5)

where A_{k,s} is an n_{s} × n_{s} positive definite (but not necessarily symmetric) matrix. In particular, we can set A_{k,s} ≡ I_{(s)} where I_{(s)} is an n_{s} × n_{s} unit matrix or use an appropriate quasi-Newton update. If the set U_{s} is defined by linear constraints, the problem (2.3) with T_{k,s} being defined in (2.5) can be solved by finite algorithms (see [7] for more details).

It should be noted that the method above differs from those in [6]–[8] even in case m = 1 since it involves both serious and null steps. Indeed, in the case where σ_{k,s} > 0 for some s ∈ M, the method produces a serious step. Otherwise, we must have σ_{k,s} = 0 for all s ∈ M and the method produces a null step. Thus, λ(k) is a counter for null steps. Therefore, the method combines serious steps with tuning parameters.

Denote by k_{l} an iteration number such that

λ(k_{l}) = l, λ(k_{l} + 1) = l + 1

for l = 1, 2, …, k_{0} = 0. In what follows we also set

y^{l} = u^{k_{l}} for l = 1, 2, …; y^{0} = u^{0}.

Remark 2.1. The method above corresponds to a consequentive decomposition scheme, Steps 1 and 2 resembling the coordinate descent processes. However, the projection operations in (2.4) can be carried out in parallel in the spaces R^{n_{s}}. Moreover, after a slight modification, we can apply a parallel decomposition scheme for the auxiliary procedures in Step 1 as well.

3. Convergence

We first obtain some auxiliary results that will be used for proving convergence.

Lemma 3.1. (a) It holds that

(θ̃β^{j})⟨G_{s}(u^{k}), u_{s}^{k} − z_{s}^{k,j}⟩ ≥ ⟨T_{k,s}(u_{s}^{k}, z_{s}^{k,j}), z_{s}^{k,j} − u_{s}^{k}⟩ ≥ τ′∥u_{s}^{k} − z_{s}^{k,j}∥^{2} ∀j ∈ Z_{+}. (3.1)

(b) Problem (2.3) has a unique solution.

Proof. Since z_{s}^{k,j} is a solution of (2.3), we have

(θ̃β^{j})⟨G_{s}(u^{k}), u_{s}^{k} − z_{s}^{k,j}⟩ ≥ ⟨T_{k,s}(u_{s}^{k}, z_{s}^{k,j}), z_{s}^{k,j} − u_{s}^{k}⟩.

By the properties of T_{k,s}, we obtain

⟨T_{k,s}(u_{s}^{k}, z_{s}^{k,j}), z_{s}^{k,j} − u_{s}^{k}⟩ ≥ τ′∥u_{s}^{k} − z_{s}^{k,j}∥^{2}

and we see that the assertion of (a) is true. Assertion (b) follows, e.g., from [2, Corollary 3.2]. □

Lemma 3.2. Suppose that {u^{k}} is bounded, u^{k} ∈ U for k = 0, 1, … Then: (a) {v^{k}} is bounded. (b)

θ_{k,s} ≥ θ′ > 0, k = 0, 1, …  (3.2)

Proof. From (3.1) and the Cauchy - Schwarz inequality it follows that

θ̃∥G_{s}(u^{k})∥ ≥ τ′∥u_{s}^{k} − v_{s}^{k}∥.

Since {u^{k}} is bounded and G_{s} is locally Lipschitz continuous, the above inequality implies that {v^{k}} is also bounded. Therefore, part (a) holds. By analogy, we can conclude that there exists a convex bounded subset W of U such that {u^{k}} and {(u^{k}∥z_{s}^{k,j})} are contained in W. Then G_{s} is Lipschitz continuous on W. Therefore,

⟨G_{s}(u^{k}∥z_{s}^{k,j}), z_{s}^{k,j} − u_{s}^{k}⟩ = ⟨G_{s}(u^{k}), z_{s}^{k,j} − u_{s}^{k}⟩ + ⟨G_{s}(u^{k}∥z_{s}^{k,j}) − G_{s}(u^{k}), z_{s}^{k,j} − u_{s}^{k}⟩
≤ ⟨G_{s}(u^{k}), z_{s}^{k,j} − u_{s}^{k}⟩ + L_{s}∥z_{s}^{k,j} − u_{s}^{k}∥^{2}

where L_{s} is the corresponding Lipschitz constant. Using (3.1) gives

⟨G_{s}(u^{k}∥z_{s}^{k,j}), z_{s}^{k,j} − u_{s}^{k}⟩ ≤ (1 − θ̃β^{j}L_{s}/τ′)⟨G_{s}(u^{k}), z_{s}^{k,j} − u_{s}^{k}⟩
≤ α⟨G_{s}(u^{k}), z_{s}^{k,j} − u_{s}^{k}⟩

if 1 − θ̃β^{j}L_{s}/τ′ ≥ α or θ̃β^{j} ≤ (1 − α)τ′/L_{s}. Taking into account (2.2) we see that (3.2) holds with θ′ = min{θ̃, (1 − α)τ′/L̃}, where L̃ = max_{s∈M}{L_{s}}. The proof is complete. □

Lemma 3.3. In Step 2 we have σ_{k,s} > 0 and g^{k} ≠ 0.

Proof. From (2.2), (3.1) it follows that

α^{−1}θ̃⟨G_{s}(v^{k}), u_{s}^{k} − v_{s}^{k}⟩ ≥ θ̃⟨G_{s}(u^{k}), u_{s}^{k} − v_{s}^{k}⟩ ≥ τ′∥u_{s}^{k} − v_{s}^{k}∥^{2} ≥ τ′ε_{l}^{2}

at Step 2. Hence, σ_{k,s} > 0 and g_{s}^{k} = G_{s}(v^{k}) ≠ 0. Therefore, g^{k} ≠ 0 either. □

Thus, in accordance with Lemma 3.3, each iteration of the method is well-defined.

Lemma 3.4. It holds that

∥u^{k+1} − u^{∗}∥^{2} ≤ ∥u^{k} − u^{∗}∥^{2} − γ(2 − γ)(σ_{k}∥g^{k}∥)^{2} ∀u^{∗} ∈ U^{∗}.  (3.3)

Proof. It is clear that (3.3) holds in the case of a null step. Let us consider the case of a serious step at the kth iteration. Then σ_{k} > 0 and there exists s ∈ M such that σ_{k} = σ_{k,s}/∥g^{k}∥^{2}. Applying (2.1) gives

⟨g^{k}, v^{k} − u^{∗}⟩ ≥ 0 ∀u^{∗} ∈ U^{∗}.

By the definition of σ_{k,s}, for all u^{∗} ∈ U^{∗}, we now obtain

⟨g^{k}, u^{k} − u^{∗}⟩ = ⟨g^{k}, v^{k} − u^{∗}⟩ + ⟨g^{k}, u^{k} − v^{k}⟩
≥ ∑_{i∈M}⟨g_{i}^{k}, u_{i}^{k} − v_{i}^{k}⟩ = ⟨g_{s}^{k}, u_{s}^{k} − v_{s}^{k}⟩
= σ_{k,s} > 0

due to Lemma 3.3. By using the projection properties we now obtain

∥u^{k+1} − u^{∗}∥^{2} ≤ ∥u^{k} − γσ_{k}g^{k} − u^{∗}∥^{2}
= ∥u^{k} − u^{∗}∥^{2} − 2γσ_{k}⟨g^{k}, u^{k} − u^{∗}⟩ + (γσ_{k}∥g^{k}∥)^{2}
≤ ∥u^{k} − u^{∗}∥^{2} − 2γ(σ_{k}∥g^{k}∥)^{2} + (γσ_{k}∥g^{k}∥)^{2}
= ∥u^{k} − u^{∗}∥^{2} − γ(2 − γ)(σ_{k}∥g^{k}∥)^{2},

and the result follows. □

We are now in a position to establish the convergence of the method.

Theorem 3.1. Let a sequence {u^{k}} be constructed by the method of Section 2. Then,

lim_{k→∞} u^{k} = u^{∗} ∈ U^{∗}.  (3.4)

Proof. First we note that {u^{k}} is bounded due to (3.3), i.e. the assertions of Lemma 3.2 hold. We will show that a sequence {y^{l}} is infinite. Indeed, otherwise l ≤ d < ∞ and there exists an integer k̄ such that λ(k + 1) = λ(k) when k ≥ k̄. From definitions of σ_{k} and g^{k} it follows that

σ_{k}∥g^{k}∥ = ⟨g_{s}^{k}, u_{s}^{k} − v_{s}^{k}⟩/∥g^{k}∥ ≥ ατ′ε_{d}^{2}/(θ̃∥g^{k}∥) ≥ δ > 0,

which contradicts (3.3).

Thus, {y^{l}} is infinite. Since {u^{k}} is bounded, so is {y^{l}}. Hence, there exists a subsequence of {y^{l}} that converges to some point u^{∗} ∈ U. Without loss of generality we suppose that

lim_{l→∞} y^{l} = u^{∗}.

At the k_{l}th iteration, for each s ∈ M, we have ∥u_{s}^{k_{l}} − v_{s}^{k_{l}}∥ ≤ ε_{l}. Fix u ∈ U. By the definition of v_{s}^{k_{l}}, for each s ∈ M, we have

⟨G_{s}(u^{k_{l}}), u_{s} − v_{s}^{k_{l}}⟩ ≥ θ_{k_{l},s}^{−1}⟨T_{k_{l},s}(u_{s}^{k_{l}}, v_{s}^{k_{l}}), v_{s}^{k_{l}} − u_{s}⟩.

By Lemma 3.2 and properties of T_{k,s}, we obtain

⟨G_{s}(y^{l}), u_{s} − u_{s}^{k_{l}}⟩ ≥ −θ_{k_{l},s}^{−1}τ′′∥u_{s}^{k_{l}} − v_{s}^{k_{l}}∥∥u_{s} − v_{s}^{k_{l}}∥ − ∥G_{s}(y^{l})∥∥u_{s}^{k_{l}} − v_{s}^{k_{l}}∥
≥ −τ′′ε_{l}∥u_{s} − v_{s}^{k_{l}}∥/θ′ − ∥G_{s}(y^{l})∥ε_{l}.

Taking the limit l → ∞ in this inequality gives

⟨G_{s}(u^{∗}), u_{s} − u_{s}^{∗}⟩ ≥ 0 ∀s ∈ M.

It follows that

∑_{s∈M}⟨G_{s}(u^{∗}), u_{s} − u_{s}^{∗}⟩ ≥ 0 ∀u_{s} ∈ U_{s}, s ∈ M;

i.e. u^{∗} ∈ U^{∗}. Then (3.3) implies (3.4) and the proof is complete. □

4. Conclusions

In this paper, a general iterative framework for solving VI over product sets has been developed. We have proved convergence of the corresponding method under weak assumptions. The method make use of decomposition techniques which allow one to solve high-dimensional problems.

References

[1] D. Kinderlerer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, 1980.

[2] P.T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. Progr., 48 (1990), pp.161–220.

[3] M. Fukushima, Merit functions for variational inequality and complementarity problems, In: Nonlinear Optimization and Applications, Edited by G. Di Pillo and F. Giannessi, Plenum Press, New York, 1996.

[4] G.M. Korpelevich, The extragradient method for finding saddle points and other problems, Matecon, 12 (1976), pp.35–49.

[5] P. Marcotte and D.L. Zhu, Global convergence of descent processes for solving non strictly monotone variational inequalities, Comp. Optimiz. and Appl., 4 (1995), pp.127–138.

[6] I.V. Konnov, Combined relaxation methods for finding equilibrium points and solving related problems, Russian Math. (Iz. VUZ), 37 (1993), No.2, pp.44–51.

I.KONNOV 9

[7] I.V. Konnov, A class of combined iterative methods for solving variational inequalities, J. of Optimiz. Theory and Appl., 94 (1997), pp.677–693.

[8] I.V. Konnov, Linearly convergent combined relaxation methods, News-Letter of MPA, Issue 7 (1997), pp.135–137 (in Russian).

[9] I.V. Konnov, A general approach to finding stationary points and the solution of related problems, Comput. Maths and Math. Phys., 36 (1996), 585–593.

[10] T. Takayama and G.G. Judge, Spatial and Temporal Price and Allocation Models, North-Holland, Amsterdam, 1971.

[11] J.-S. Pang, Asymmetric variational inequality problems over product sets: applications and iterative methods, Math. Progr., 31 (1985), pp.206–219.

Kazan State University, Department of Applied Mathematics, Kremlevskaya, 18, Kazan, 4200008, Russia E-mail address: igor.konnov@ksu.ru

Received November 16, 1998