On the Convergence of Descent Methods

for Monotone Variational Inequalities

M. Patriksson^{1}

Abstract. Recently, Zhu and Marcotte [15] established the convergence of a modified descent algorithm for monotone variational inequalities. Using algorithmic equivalence results due to Patriksson [10, 11] and Larsson and Patriksson [7], we show that this convergence result may be used to establish the convergence of slightly modified versions of the classical successive approximation algorithms of Dafermos [2] and Cohen [1], and of the descent algorithms of Wu et al. [14], Patriksson [10, 11], and Larsson and Patriksson [7], under assumptions that are both much milder and much easier to verify than those for their original statements.

Key Words. Monotone variational inequalities, successive approximation algorithms, merit functions, descent methods, algorithmic equivalence, convergence

1 Introduction

Let X be a nonempty, closed and convex set in ℜ^{n}, and F : X ↦ ℜ^{n} a continuous and monotone mapping on X. Consider the variational inequality problem of finding an x^{∗} ∈ X such that

[VIP(F, X)]  F (x^{∗})^{T}(x − x^{∗}) ≥ 0,  ∀x ∈ X.

The variational inequality problem (and its special cases) has a large variety of applications in the mathematical and engineering sciences, for example in partial differential equations, equilibrium problems in games, economics and transportation analysis, and nonlinear programming.

It is a well-known fact that the problem [VIP(F, X)] describes the first-order optimality conditions of a convex optimization problem if F is the gradient of a convex function f : X ↦ ℜ, and of a convex-concave saddle point problem if F (z, y)^{T} = [∇_{z}L(z, y)^{T}, −∇_{y}L(z, y)^{T}] for some convex-concave function L : Z × Y ↦ ℜ. (Here, x^{T} = (z^{T}, y^{T}) and X = Z × Y.) In these cases, many iterative algorithms are immediately available for the solution of [VIP(F, X)] where, in each iteration, a sufficient decrease in a merit function is obtained through a line search in a feasible descent direction; natural choices of merit functions are f and f(·) = sup_{y∈Y} L(·, y), respectively. In other cases (in which the term asymmetric variational inequality is frequently used) there is no merit function immediately available for monitoring the convergence of an iterative algorithm.

1Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden.

The classical approach to solving an asymmetric variational inequality is to replace the mapping F with a sequence {F^{k}} of simpler mappings, and define the iterate x^{k+1} by the solution to [VIP(F^{k}, X)]. Such successive approximation approaches include linear approximation methods [F^{k}(x) = F (x^{k}) + A^{k}(x − x^{k}), where A^{k} is a positive definite matrix], among which we find Newton-type approaches, linearized Jacobi methods and the projection algorithm, and nonlinear approximation algorithms, such as the Jacobi method [F_{i}^{k}(x_{i}) = F_{i}(x_{i_{−}}^{k}, x_{i}, x_{i_{+}}^{k}), i ∈ {1, …, n}, where x_{i_{−}} denotes the subvector of x with indices lower than i, and x_{i_{+}}, correspondingly, the subvector with higher indices], the Gauss–Seidel approach [F_{i}^{k}(x_{i}) = F_{i}(x_{i_{−}}, x_{i}, x_{i_{+}}^{k}), i ∈ {1, …, n}], and regularization methods [F^{k}(x) = F (x) + γ_{k}R(x, x^{k}), where {γ_{k}} is a sequence of positive parameters and x ↦ R(x, x^{k}) is a strongly monotone mapping]; see [9, 4] for surveys of successive approximation methods for [VIP(F, X)].

The convergence of such classical approaches is often based on a guaranteed monotone decrease of a merit function which is artificial in the sense that it is not possible to evaluate and therefore possible to utilize neither to monitor the convergence of the algorithm nor in line searches for accelerating its convergence. One example of an artificial merit function is the (unknown) Euclidean distance from a given iterate to the solution set Ω of [VIP(F, X)].

Recently, reformulations of asymmetric variational inequalities as, in general nonconvex, optimization problems have been shown to naturally lead to convergent descent algorithms (e.g., [3, 7]). In such reformulations, the problem [VIP(F, X)] is supplied with a specially constructed (calculable) merit function, ψ, whose (local) minima coincide with the solution set Ω of [VIP(F, X)]. In algorithms based on the direct minimization of ψ, the solution y^{k} to an approximate variational inequality [VIP(F^{k}, X)] defines a descent direction, d^{k} =^{def} y^{k} − x^{k}, for ψ; the next iterate is defined as the (approximate) solution to the problem

min_{t≥0: x^{k}+td^{k}∈X} ψ(x^{k} + td^{k}).

The first known descent algorithm of this type is given by Zuhovickiǐ et al. [16]; see [10, 11, 7, 12] for surveys of descent methods for variational inequalities. Some of these algorithms are convergent under weaker conditions on the problem data than the classical successive approximation approaches, and the introduction of the line search may also lead to a higher practical convergence rate.

In general, however, in order to establish the convergence of either one of the two types of algorithms a strict or strong monotonicity assumption on F is required. [Examples of algorithms that require only monotonicity of F are the extragradient method [6] (a modification of the projection method), the descent method of Smith [13], and descent algorithms based on Newton’s method (e.g., [8]).] In addition, the convergence conditions frequently include the required knowledge of certain problem parameters, such as the strong monotonicity and Lipschitz constants of F, which may be difficult to estimate, and further conditions which are difficult to verify in practice. This is in contrast to the mild (and in many cases easily verified) conditions that guarantee the convergence of these types of algorithms in the case of convex programming [11].

The need for these strong assumptions to hold in order to guarantee the convergence of iterative algorithms for [VIP(F, X)] is very unfortunate, in view of the fact that important applications of variational inequalities may fail to satisfy them; one example is traffic equilibrium models with detailed representations of junctions which, according to Heydecker [5], can not satisfy a strict monotonicity assumption.

Recently, Zhu and Marcotte [15] established the convergence of a general descent algorithm for variational inequalities, which requires only monotonicity of F. The purpose of this note is to show that this algorithm may be shown to be a slight modification of classical successive approximation schemes as well as descent algorithms recently presented for the solution of [VIP(F, X)], which all require strict or strong monotonicity of F in their original statements. Thus, by introducing the proper modifications of these algorithms, convergence may be established under much milder assumptions on F. Furthermore, the additional technical conditions present for the original algorithms may be removed, thus enabling a much easier verification of the convergence conditions.

In the next Section, we give a short description of the algorithm of Zhu and Marcotte, and the requirements for its convergence. In Section 3, we relate the algorithm classes of Dafermos [2], Cohen [1], Wu et al. [14], Patriksson [10, 11], and Larsson and Patriksson [7] to each other and to the algorithm of Zhu and Marcotte. Utilizing these relationships we establish the modifications to these algorithms that are necessary in order to yield convergence under only a monotonicity assumption on F.

2 The algorithm of Zhu and Marcotte

Henceforth, we shall assume that X is bounded. (This ensures that the solution set Ω is nonempty.)

Let ϕ : X × X ↦ ℜ be a continuously differentiable function on X × X of the form ϕ(x, y), strictly convex with respect to y. Further, let ϕ be such that ∇_{y}ϕ(x, x) = 0, for all x ∈ X.

Let α > 0, define

G_{α}(x) = max_{y∈X} \{F (x)^{T}(x − y) − \frac{1}{α}ϕ(x, y)\} ,  (1)

and let y_{α}(x) denote the (unique) solution to the inner problem of (1).

The algorithm of Zhu and Marcotte proceeds as follows.

Step 0 (Initialization) Choose x^{0} ∈ X, ε, α_{0}, Δ_{α} > 0, and 0 < β, γ, σ < 1. Let k = 0.

Step 1 (Search direction generation) Evaluate G_{α_{k}}(x^{k}), and let d^{k} = y_{α_{k}}(x^{k}) − x^{k}.

Step 2 (Stopping criterion) If G_{α_{k}}(x^{k}) < ε, then stop. If

G_{α_{k}}(x^{k}) ≤ \frac{1}{(1 − γ)α} \{∇_{x}ϕ(x^{k}, y_{α_{k}}(x^{k}))^{T}(y_{α_{k}}(x^{k}) − x^{k}) − ϕ(x^{k}, y_{α_{k}}(x^{k}))\} ,

then let α_{k+1} = α_{k} + Δ_{α}, x^{k+1} = x^{k}, and go to Step 1; otherwise, let α_{k+1} = α_{k}, and go to Step 3.

Step 3 (Armijo-type line search) If G_{α_{k}}(x^{k} + d^{k}) ≤ G_{α_{k}}(x^{k}), then let t_{k} = 1; otherwise, let m be the smallest positive integer such that

G_{α_{k}}(x^{k}) − G_{α_{k}}(x^{k} + β^{m}d^{k}) ≥ −σβ^{m}∇G_{α_{k}}(x^{k})^{T}d^{k},  (2)

and t_{k} = β^{m}. Let x^{k+1} = x^{k} + t_{k}d^{k}, k := k + 1, and go to Step 1.

The convergence of the algorithm is given by the below theorem.

Theorem 1 [15] (Convergence of the algorithm of Zhu and Marcotte) Let F be continuously differentiable, monotone and Lipschitz continuous on X. Let x^{0} be arbitrary in X. Then either the algorithm terminates at a solution to [VIP(F, X)] or it generates an infinite sequence {x^{k}} such that any limit point is a solution to [VIP(F, X)].

In the next section we relate some earlier proposed iterative schemes for the solution of [VIP(F, X)] to each other and to the algorithm of Zhu and Marcotte. We finally describe the modifications to these algorithms that are necessary in order to ensure convergence under only a monotonicity assumption on F.

3 Algorithmic equivalence results and modified descent algorithms

We first state the generic cost approximation algorithm for [VIP(F, X)], introduced by Patriksson [10, 11] and Larsson and Patriksson [7].

Choose a sequence {φ^{k}} of strictly convex and continuously differentiable functions φ^{k} : X ↦ ℜ^{n}, and a merit function ψ.

Step 0 (Initialization) Choose x^{0} ∈ X, and let k = 0.

Step 1 (Search direction generation) Let y(x^{k}) be the solution to

max_{y∈X} {[F (x^{k}) − ∇φ^{k}(x^{k})]^{T}(x^{k} − y) − φ^{k}(y)} .  (3)
Let d^{k} = y(x^{k}) − x^{k}.

Step 2 (Stopping criterion) If y(x^{k}) = x^{k}, then stop.

Step 3 (Line search) Find a step length, t_{k}, which (approximately) solves the problem

min_{t≥0: x^{k}+td^{k}∈X} ψ(x^{k} + td^{k}).  (4)
Let x^{k+1} = x^{k} + t_{k}d^{k}, k := k + 1, and go to Step 1.

Below, we state an algorithmic equivalence result, which establishes the close relationships among iterative methods for [VIP(F, X)], including the one of Zhu and Marcotte.

Theorem 2 (Algorithmic equivalence results)

(a) If the sequence {φ^{k}} is given by φ^{k} = φ(·, x^{k}), where φ : X × X ↦ ℜ is continuous on X × X, then the resulting subproblem (3) is equivalent to the subproblems of Dafermos [2] and Wu et al. [14].

(b) If the sequence {φ^{k}} is given by φ^{k} = α_{k}φ, where α_{k} > 0 and φ : X ↦ ℜ is strictly convex, then the resulting subproblem (3) is equivalent to the subproblem of Cohen [1].

(c) If the sequence \{φ^{k}\} is given by φ^{k} = \frac{1}{α_{k}} ϕ(x^{k}, ·), where α_{k} > 0 and ϕ : X × X ↦ ℜ is given as in Section 2, then the resulting subproblem (3) is equivalent to the inner problem of (1).

Proof.

(a) See [10, 11, 7].

(b) See [11, 7].

(c) Let φ^{k} = \frac{1}{α_{k}} ϕ(x^{k}, ·). Then ∇φ^{k}(x^{k}) = 0, and (3) equals (1). □

To describe the above mentioned algorithms as instances of the generic cost approximation algorithm, we need only to specify the choices of step lengths in Step 3. The successive approximation algorithms of Dafermos and Cohen correspond to taking unit steps, while the descent algorithms of Wu et al. and Larsson and Patriksson include line searches with respect to merit functions of the form (3). The generic algorithm includes a wide variety of classical algorithms for variational inequalities; for instance, with t_{k} ≡ 1, the projection algorithm results from the choice φ^{k}(x) = \frac{1}{2}x^{T}Bx, where B ∈ ℜ^{n×n} is symmetric and positive definite, and the symmetrized Newton method from the choice φ^{k}(x) = \frac{1}{2}x^{T}∇F (x^{k})x. Further examples are found in [10, 11, 7].

The convergence of the algorithms of Cohen, Dafermos, Wu et al., and Larsson and Patriksson all require F to be at least strictly monotone. (In the case of Cohen, F must be strongly monotone.) Further, the convergence conditions of all these algorithms include additional assumptions on the relationships among problem parameters, such as the strong monotonicity and Lipschitz constants of F and of the respective choices of φ^{k}. By introducing the proper modifications of these algorithms, so that they fall into the framework of Zhu and Marcotte, all these assumptions may be replaced by only monotonicity, according to Theorem 1.

In the case of Cohen’s [1] algorithm (the auxiliary problem principle), the sequence {α_{k}} of parameters would be governed by the scheme of Section 2. In the case of Dafermos [2], Wu et al. [14], Patriksson [10, 11], and Larsson and Patriksson [7], the function φ would be replaced by a sequence \{\frac{1}{α_{k}} φ\} of functions. In all these algorithms, a line search of the type given in Step 3 of the algorithm of Zhu and Marcotte would replace a line search of the form (4) or a unit step.

Disregarding the line search step of the algorithm of Section 2, which is only considered when it is necessary in order to guarantee global convergence, the algorithm contains the same steps as the successive approximation version of the generic cost approximation algorithm; an implementation of, for instance, a modified version of an instance of the algorithm class of Dafermos would therefore amount to only minor adjustments of an existing implementation.

4 Conclusion

In this note, we have established that with only minor adjustments, classical successive approximation algorithms and descent algorithms for variational inequalities, which require the problem defining mapping to be at least strictly monotone, can be made globally convergent under only a monotonicity assumption. Furthermore, with these minor adjustments, the additional technical assumptions and the required knowledge of estimates of certain problem parameters, which are present in the convergence conditions of their original statements, may be removed; thus, a much easier verification of the convergence conditions is enabled.

References

[1] G. Cohen, Auxiliary problem principle extended to variational inequalities, Journal of Optimization Theory and Applications, 59 (1988), pp. 325–333.

[2] S. Dafermos, An iterative scheme for variational inequalities, Mathematical Programming, 26 (1983), pp. 40–47.

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

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

[5] B. G. Heydecker, Some consequences of detailed junction modeling in road traffic assignment, Transportation Science, 17 (1983), pp. 263–281.

[6] G. M. Korpelevich, The extragradient method for finding saddle points and other problems, Matekon, 13 (1977), pp. 35–49.

[7] T. Larsson and M. Patriksson, A class of gap functions for variational inequalities, Mathematical Programming, 64 (1994), pp. 53–79.

[8] P. Marcotte and J.-P. Dussault, A modified Newton method for solving variational inequalities, in Proceedings of the 24th IEEE Conference on Decision and Control, Fort Lauderdale, FL, 1985, pp. 1433–1436.

[9] J.-S. Pang and D. Chan, Iterative methods for variational and complementarity problems, Mathematical Programming, 24 (1982), pp. 284–313.

[10] M. Patriksson, A unified description of iterative algorithms for traffic equilibria, European Journal of Operational Research, 71 (1993), pp. 154–176.

[11] M. Patriksson, A unified framework of descent algorithms for nonlinear programs and variational inequalities, PhD thesis, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden, 1993.

[12] M. Patriksson, The Traffic Assignment Problem: Models and Methods, VSP, Utrecht, The Netherlands, 1995.

[13] M. J. Smith, A descent algorithm for solving monotone variational inequalities and monotone complementarity problems, Journal of Optimization Theory and Applications, 44 (1984), pp. 485–496.

[14] J. H. Wu, M. Florian, and P. Marcotte, A general descent framework for the monotone variational inequality problem, Mathematical Programming, 61 (1993), pp. 281–300.

[15] D. L. Zhu and P. Marcotte, Modified descent methods for solving the monotone variational inequality problem, Operations Research Letters, 14 (1993), pp. 111–120.

[16] S. I. Zuhovickiǐ, R. A. Polyak, and M. E. Primak, Two methods of search for equilibrium points of n-person concave games, Soviet Mathematics Doklady, 10 (1969), pp. 279–282.