A Class of Gap Functions for Variational Inequalities

by

Torbjörn Larsson Michael Patriksson

Department of Mathematics Linköping Institute of Technology S-581 83 Linköping Sweden

Abstract

Recently, Auchmuty (1989) has introduced a new class of merit functions, or optimization formulations, for variational inequalities in finite-dimensional space. We develop and generalize Auchmuty’s results, and relate his class of merit functions to other works done in this field. Especially, we investigate differentiability and convexity properties, and present characterizations of the set of solutions to variational inequalities. We then present new descent algorithms for variational inequalities within this framework, including approximate solutions of the direction finding and line search problems. The new class of merit functions include the primal and dual gap functions, introduced by Zuhovickiǐ et al. (1969a, 1969b), and the differentiable merit function recently presented by Fukushima (1992); also, the descent algorithm proposed by Fukushima is a special case from the class of descent methods developed in this paper. Through a generalization of Auchmuty’s class of merit functions we extend those inherent in the works of Dafermos (1983), Cohen (1988) and Wu et al. (1991); new algorithmic equivalence results, relating these algorithm classes to each other and to Auchmuty’s framework, are also given.

Key Words: Finite-Dimensional Variational Inequalities, Merit Functions, Variational Principles, Successive Approximation Algorithms, Descent Algorithms

Abbreviated title: Gap Functions for Variational Inequalities

1 Introduction

Let X be a nonempty, closed and convex subset of ℜ^{n}, and F : X ↦ ℜ^{n} be a continuous mapping. The variational inequality problem is to find an x^{∗} ∈ X such that

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

Here, T denotes transpose. We will throughout the paper assume that [VIP] admits at least one solution, and denote the solution set of [VIP] by Ω. The assumptions made on X and F are assumed to hold throughout the paper.

Variational inequality problems occur in a number of applications, and were first studied in infinite-dimensional space in connection with nonlinear partial differential equations. More recently, finite-dimensional applications of variational inequality theory, such as non-cooperative games and other equilibrium problems, have arisen.

The solution set is nonempty if, for instance, the feasible set, X, is bounded or if F is coercive on X, i.e., if there is a vector \overline{x} ∈ X such that

lim_{{x∈X \atop ∥x∥→+∞}} \{F (x)^{T} (x − \overline{x}) / ∥x∥\} = +∞,

where ∥·∥ is some appropriate vector norm, see, e.g., Kinderlehrer and Stampacchia (1980). Moreover, the set Ω is a singleton if it is nonempty and if F is strictly monotone on X, i.e., if

[F (x) − F (y)]^{T} (x − y) > 0, ∀ x, y ∈ X and x ≠ y.

The mapping F is said to be monotone on X if the strict inequality above is replaced by an inequality, and strongly monotone (with modulus m_{F}) on X if, in addition, the right hand side of the inequality is replaced by m_{F} ∥x − y∥^{2}. (Note that strong monotonicity implies both coercivity and strict monotonicity, so that strong monotonicity implies the existence of a unique solution to [VIP].) If F is the gradient of a function ϕ : ℜ^{n} ↦ ℜ, then the above properties are equivalent to strict convexity, convexity and strong convexity of ϕ on X, respectively, and, if F is continuously differentiable on an open neighbourhood of X, then the monotonicity properties of F on X may be characterized in terms of the positive definiteness of its Jacobian, ∇F, see e.g. Ortega and Rheinboldt (1970, Section 5.4). For an overview of theory, algorithms and applications of [VIP], we refer to the recent survey by Harker and Pang (1990).

It is well known that the problem [VIP] is equivalent to the first order optimality conditions for the convex problem

[P]  min_{x∈X} ϕ(x) =^{def} ∫_{0}^{x} F (s)^{T}ds,

if the Jacobian, ∇F, of the mapping F is symmetric and positive semidefinite on an open neighbourhood of X. If the mapping F has a Jacobian which is not symmetric, the integral in [P] is not unambiguously defined, and [VIP] can in this case not be converted into an equivalent minimization problem of the form [P]. (In this case, we say that [VIP] is asymmetric.) It is the purpose of this paper to review and develop reformulations of asymmetric variational inequalities as equivalent minimization problems, investigate their properties, and derive descent methods for the solution of [VIP], utilizing a class of such optimization formulations. The basis for our development is the article by Auchmuty (1989).

We shall make use of the following conventions. All vectors are assumed to be column vectors, ∥·∥ denotes the Euclidean vector norm in ℜ^{n}, and its induced matrix and operator norms. For a given function h : X ↦ ℜ^{l} the Lipschitz constant is denoted by M_{h}. The constant in the definition of strong monotonicity will be denoted by m_{h}, and the same notation will be used for the constant in the definition of strong convexity of h (when l = 1). We shall make use of the abbreviations u.s.c. and l.s.c. for upper and lower semicontinuity, respectively, and write h ∈ C^{p} on X meaning that h is p times continuously differentiable on an open neighbourhood of X. (We write h ∈ C^{p} if this holds on ℜ^{n}.)

The remainder of the paper is organized as follows. In Section 2 we present a class of merit functions for asymmetric variational inequalities, originally proposed by Auchmuty (1989). We summarize some of the most important results of that paper, and provide an interpretation and a motivation of the use of these merit functions. In Section 3 we review and relate to Auchmuty’s class of merit functions some earlier developed merit functions, with the common feature that they can be described as gap functions. In particular, we show that the primal and dual gap functions, which were introduced by Zuhovickiǐ et al. (1969a, 1969b), and the recently presented differentiable merit function of Fukushima (1992), belong to this class. In Section 4 we further investigate properties of Auchmuty’s merit functions, provide equivalent characterizations of the solution set, and establish descent algorithms, constructed in a manner similar to Fukushima’s. In Section 5 we present a generalization of his merit functions, and give some algorithmic equivalence results, relating our work to that of Dafermos (1983), Cohen (1988) and Wu et al. (1991). Finally, in Section 6 we make some concluding remarks and present research opportunities.

2 Background and motivation

The merit functions discussed in this paper are all of the type given by the following definition.

Definition 2.1 (Gap function) A function γ : X ↦ ℜ ∪ {−∞, +∞} is a gap function for [VIP] if

1. γ is restricted in sign on X, and

2. γ(x) = 0 ⇔ x ∈ Ω.

A gap function γ provides a measure of the violation of [VIP] at any point x ∈ X, and by minimizing γ over X (assuming γ(x) ≥ 0 on X) a point in Ω is obtained. Therefore, gap functions may be used as merit functions for variational inequalities.

We now summarize the results of Auchmuty (1989). Auchmuty develops merit functions for [VIP], based on a function L̃ : X × X ↦ ℜ, with

L̃(x, y) = f(x) − f(y) + [F (x) − ∇f(x)]^{T} (x − y),  (2.1)

where f : ℜ^{n} ↦ ℜ ∪ {+∞} is convex and l.s.c., and f ∈ C^{1} on X.

The following theorem relates saddle points to L̃ to the set of solutions to [VIP]. [For proofs of the theorems stated in this section, we refer to Auchmuty (1989).]

Theorem 2.1 (Saddle points are in Ω) If (x^{∗}, y^{∗}) ∈ X × X satisfies

L̃ (x^{∗}, y) ≤ L̃ (x^{∗}, y^{∗}) ≤ L̃ (x, y^{∗})

for all (x, y) ∈ X × X, then x^{∗} solves [VIP].

Remark 2.1 The point y^{∗} does not, in general, solve [VIP] and, since L̃(x, y) is not convex in the x argument, it is, in general, not a true saddle function.

The saddle point characterization of a solution to [VIP] defines two possible optimization formulations for the variational inequality problem by the introduction of two different gap functions. The first, which we will refer to as the primal generalized gap function, for reasons to be evident later, is defined as

[PGG]  G̃(x) =^{def} sup_{y∈X} L̃(x, y), x ∈ X,

and the corresponding optimization formulation is

[OPGG]  inf_{x∈X} G̃(x).

Note that [PGG] is a convex program, since L̃ is concave in y, and that L̃ is invariant under the addition of an affine function to f. For the primal generalized gap function G̃ : X ↦ ℜ ∪ {+∞}, Auchmuty’s results are summarized in the following theorem.

Theorem 2.2 (Properties of G̃)

1. G̃(x) is l.s.c. and nonnegative for all x ∈ X, and

2. G̃ (x) = 0 ⇔ x ∈ Ω.

In particular, when X is bounded, G̃ is finite on X.

Remark 2.2 Finiteness of G̃ may be accomplished also for unbounded sets for instance by imposing strong convexity of f. Since a minimum of G̃ over X always exists whenever G̃ is finite, [OPGG] can be used also to detect the non-existence of a solution to [VIP], since, in this case, min_{x∈X} G̃(x) > 0; the properties of such minimizers are subjects for further research.

Hence, solving [VIP] is equivalent to minimizing G̃ over X, so that G̃ is a merit function for variational inequalities.

Turning to the dual formulation, we introduce the function g̃ : X ↦ ℜ ∪ {−∞} through

[DGG]  g̃(y) =^{def} inf_{x∈X} L̃(x, y), y ∈ X,

and the resulting optimization formulation is

[ODGG]  sup_{y∈X} g̃(y).

For the function g̃ we have the following results, corresponding to Theorem 2.2.

Theorem 2.3 (Properties of g̃)

1. g̃(y) is nonpositive for all y ∈ X, and

2. g̃ (y) = 0 ⇒ y ∈ Ω.

In general, the converse of 2. does not hold, as the example below shows. A consequence of this is that g̃ is not a gap function. (However, for pseudo-monotone maps F and with f ≡ 0, the converse of 2. does hold, see Section 3.)

Example 2.1 Let F (x) = x and X = {x | 0 ≤ x ≤ 1}. The problem is then equivalent to minimizing \frac{1}{2}x^{2} over X, with the unique solution x^{∗} = 0 [Ω = \{0\}]. Choose f(x) = x^{4}, which is strictly convex. Then g̃(0) = −2 ≠ 0. □

We end this section by motivating the use of G̃ as a merit function, by providing an interpretation of it in terms of cost approximations of [VIP].

Since [PGG] is a convex program, evaluating G̃(x) is equivalent to finding a solution y(x) to the following variational inequality, defining the first order optimality conditions of [PGG] (e.g., Bazaraa and Shetty, 1979, Theorem 3.4.3).

∇_{y}L̃ (x, y(x))^{T} (y − y(x)) ≤ 0, ∀ y ∈ X  (2.2)

Here, ∇_{y} denotes differentiation with respect to y.

Now, assume that, in [VIP], the mapping F is approximated by the gradient of a convex function f. Obviously, the error made when replacing the original map is F − ∇f. If, for some fixed x ∈ X, this error is taken into account by adding to ∇f the error term F (x)−∇f(x), then the approximate symmetric variational inequality is to find a y(x) ∈ X such that

[AVIP] [∇f (y(x)) + F (x) − ∇f(x)]^{T} (y − y(x)) ≥ 0, ∀ y ∈ X.

But from (2.1) it then follows that (2.2) and [AVIP] are equivalent. We may thus conclude that the calculation of G̃(x) amounts to solving an approximate, symmetric, variational inequality obtained through a cost approximation. [This interpretation was first made by Patriksson (1991b).] Obviously, the better the gradient ∇f approximates the, possibly asymmetric, mapping F, the closer y(x) will be to Ω. This is further illustrated below.

Assume now that ∇F is symmetric on X. We may then choose the function f such that ∇f = F, and [AVIP] reduces to [VIP]. [Also, G̃(x) = f(x) + c, where c = − inf_{x∈X} f(x), so that minimizing G̃ is equivalent to minimizing f over X, see Auchmuty (1989).] This possibility of choosing ∇f so as to approximate F exactly for symmetric variational inequalities suggests a symmetrization strategy for the asymmetric case. The non-existence of the optimization problem [P] is due to the fact that the value of the line integral in [P] is dependent of the curve, Γ, taken from 0 to x ∈ X. To define an unambiguous integral, we may choose the curve Γ to be the straight line from 0 to x, and hence introduce a parametrization s = s(t) = tx, with t ∈ [0, 1]. We then define

f(x) =^{def} ∫_{Γ} F (s)^{T}ds = ∫_{0}^{1} Ψ(t)dt,  (2.3)

where Ψ : ℜ ↦ ℜ is given by Ψ(t) = F (tx)^{T}x. This approximation is exact (f ≡ ϕ in [P]) if F is the gradient of f, and should be a good approximation for modest asymmetries of ∇F. The following example shows that a well known symmetrization of affine variational inequalities is obtained from the application of (2.3).

Example 2.2 Consider the asymmetric and affine variational inequality, i.e., F (x) = Ax − b, where A is an asymmetric matrix in ℜ^{n×n}. By the choice of f as in (2.3), we obtain that

f(x) = ∫_{0}^{1}(tAx − b)^{T}xdt = \frac{1}{2}x^{T}Ax − b^{T}x,

which indeed defines a symmetrization of ∇F, since ∇^{2}f = \frac{1}{2} (A + A^{T}) is the symmetric part of ∇F = A. □

In the next section we relate the results obtained by Auchmuty to some earlier results on merit functions for [VIP].

3 Gap functions for variational inequalities

3.1 The primal and dual gap functions

We begin by studying the important special case of Auchmuty’s merit functions, resulting from letting f ≡ 0 in (2.1). (Auchmuty treats this case separately, but studies into the resulting merit functions in fact traces back to the late 1960’s.) The corresponding saddle function to (2.1) then is

L(x, y) =^{def} F (x)^{T}(x − y).  (3.1)

In the context of non-cooperative game theory this function was studied already by Zuhovickiǐ et al. (1969a, 1969b, 1970, 1973); they showed that, under a monotonicity assumption on F, a solution to the equilibrium problem is found by searching for a saddle point to L, i.e., a point (x^{∗}, y^{∗}) such that

[SP]  sup_{y∈X} inf_{x∈X} F (x)^{T}(x − y) = F (x^{∗})^{T} (x^{∗} − y^{∗}) = inf_{x∈X} sup_{y∈X} F (x)^{T}(x − y).

Exploring the rightmost equality of [SP] we obtain the primal gap function G : X ↦ ℜ ∪ {+∞} defined by

[PG] G(x) =^{def} sup_{y∈X} F (x)^{T}(x − y),

which has been extensively studied in various contexts. Below we summarize its most important properties.

Theorem 3.1 (Properties of G) For any x ∈ X, let Y (x) denote the (possibly empty) set of optimal solutions to the problem [PG].

1. G is a gap function.

2. G is l.s.c. on X.

3. If X is bounded and F ∈ C^{1} on X, then G is Lipschitz continuous on X, i.e., there exists a constant M_{G} ≥ 0 such that, for all x^{1}, x^{2} ∈ X,

∥G (x^{1}) − G (x^{2})∥ ≤ M_{G} ∥x^{1} − x^{2}∥ .

4. If F ∈ C^{1} on X, then G is differentiable at x ∈ X if Y (x) = {y(x)}, with ∇G(x) = F (x) + ∇F (x)^{T}(x − y(x)).

5. If F ∈ C^{1} on X, and monotone on X, then if x ∉ Ω and Y (x) = {y(x)}, the direction d = y(x) − x is a feasible direction of descent with respect to G at x, and the directional derivative G′ (x; d) = ∇G(x)^{T}d ≤ −G(x).

6. G is convex on X if F (x)^{T}x is convex on X and each component of F is concave on X.

7. (A fixed point characterization of Ω) x ∈ Ω ⇔ x ∈ Y (x).

8. (A stationary point characterization of Ω) Under the conditions on F in 5., x ∈ Ω ⇔ G′(x; y − x) ≥ 0, ∀ y ∈ X.

Proof

1. See Zuhovickiǐ et al. (1969a, 1969b, 1970, 1973). See also Demyanov and Rubinov (1970, Section 3.1) and Hearn (1978, 1982).

2. See Dunn (1980).

3. See Marcotte (1985).

4. See Demyanov and Pevnyi (1972). See also Zuhovickiǐ et al. (1973), Auslender (1976, Section VII.3), Hearn (1978, 1982) and Hearn et al. (1984).

5. See Demyanov and Pevnyi (1972). See also Hearn (1982) for the first result, and Marcotte (1985).

6. See Hearn (1978, 1982) and Hearn et al. (1984).

7. See Marcotte (1985). See also Evtushenko (1985, p. 34).

8. See Marcotte (1985). □

Thus, if [VIP] has a solution, the set of solutions to

[OPG]  inf_{x∈X} G(x)

equals the set Ω. Note that when X is polyhedral, [PG] reduces to a linear program which, in the symmetric case, is equivalent to that solved in the Frank-Wolfe algorithm, see e.g. Hearn (1978, 1982). The function G has been used as a merit function in several algorithms for the solution of [VIP], see e.g. Zuhovickiǐ et al. (1970, 1973), Demyanov and Pevnyi (1972), Primak (1975), Lawphongpanich and Hearn (1984), Marcotte (1985, 1986), Marcotte and Dussault (1985, 1987, 1989), and Marcotte and Guélat (1988).

In the next section we will extend the results given in Theorem 3.1 to the function G̃.

Turning to the leftmost equality of [SP] we obtain the dual gap function g : X ↦ ℜ∪{−∞} defined by [DG] g(y) =^{def} inf_{x∈X} F (x)^{T}(x − y).

As established earlier, in the general case (f ≢ 0) the dual formulation does not constitute a proper gap function. For the case f ≡ 0, however, it is possible to show that g is a gap function, provided that the mapping F is pseudo-monotone on X, i.e.,

F (y)^{T}(x − y) ≥ 0 ⇒ F (x)^{T}(x − y) ≥ 0, ∀ x, y ∈ X.  (3.2)

(This property is, for instance, implied by monotonicity.) Under this condition [VIP] is equivalent to finding an x^{∗} ∈ X such that

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

see e.g. Karamardian (1976) and Auslender (1976, Section VII.1). We summarize some properties of g below.

Theorem 3.2 (Properties of g) Let F : X ↦ ℜ^{n} be pseudo-monotone on X. Also, for any y ∈ X, let X(y) denote the (possibly empty) set of optimal solutions to the problem [DG].

1. g is a gap function.

2. g is concave on X.

3. If F ∈ C^{1} on X, then g is differentiable at y ∈ X if X(y) = {x(y)}, with ∇g(y) = −∇F (x(y)).

Proof

1. See Zuhovickiǐ et al. (1969a, 1969b). See also Demyanov and Pevnyi (1972) and Auslender (1976, Section VII.5).

2. See Hearn and Nguyen (1982), Hearn et al. (1984) and Nguyen and Dupuis (1984).

3. See Hearn and Nguyen (1982) and Hearn et al. (1984). □

As a consequence of the gap function properties of g, the set of solutions to

[ODG]  sup_{y∈X} g(y)

equals the set Ω. Methods developed for [ODG] mostly apply constraint generation techniques to the semi-infinite linear program

[SIP] max z

s.t. z ≤ F (x)^{T}(x − y), ∀ x ∈ X
y ∈ X.

A line of development of such methods can be traced in Zuhovickiǐ et al. (1969a, 1969b, 1973), Demyanov and Pevnyi (1972), Auslender (1976, Section VII.5), Nguyen and Dupuis (1984) and Hearn and Lawphongpanich (1989).

Summarizing the properties of the saddle function L, although it is not convex in the x argument, we have, for pseudo-monotone F,

g(y) ≤ 0 ≤ G(x)  ∀ (x, y) ∈ X × X, and
sup_{y∈X} g(y) = 0 = inf_{x∈X} G(x),

and (x^{∗}, y^{∗}) is a saddle point to L if and only if x^{∗}, y^{∗} ∈ Ω.

One may note the nice symmetry in the properties of G and g. While the calculation of G(x) is a convex problem, the minimization of G is in general both a nonconvex and nondifferentiable problem; on the other hand, while the evaluation of g(y) is, in general, a nonconvex problem, the maximization of g is always a convex problem. Also, convexity of G holds for affine and monotone maps F, and under the same conditions the calculation of g(y) is a convex problem.

Finally, it can be mentioned that subgradient optimization methods have been devised for the reformulations [OPG] and [ODG], see e.g. Hearn (1978, 1982) and Hammond and Magnanti (1987).

3.2 Smith’s class of gap functions

In the context of traffic equilibrium, Smith (1983a, 1983b) has developed a family of gap-type merit functions for variational inequalities on polyhedral sets. If we define

[x]_{+} = max {0, x} ,

the family of objectives can be written as:

G^{p}(x) = ∑_{i∈E} ([F (x)^{T} (x − ŷ^{i})]_{+})^{p} , x ∈ X,

where p > 0 and {ŷ^{i} : i ∈ E} is the set of extreme points of the bounded polyhedron X. The functions have the following properties, similar to the ones for G̃, G and g: for all p ≥ 1, G^{p}(x) > 0, ∀ x ∉ Ω and G^{p} (x^{∗}) = 0 ⇔ x^{∗} ∈ Ω. Further studies of the properties of G^{p}(x) are made by Hearn et al. (1984). They show that the primal gap function G is a limiting case of this class of functions, since, for all x ∈ X,

\begin{aligned}lim_{p→+∞} (G^{p}(x))^{1/p} & = & max_{i∈E} F (x)^{T} (x − ŷ^{i}) \\ & = & G(x). \end{aligned}

They proceed to show that G^{p}(x) is differentiable for 2 ≤ p < +∞, and convex for p ≥ 2 and p = +∞ e.g. if F is affine and monotone. Note that the extreme points must be known explicitly in order to evaluate G^{p}(x), for p < +∞. The practical use of these gap functions is thus limited to polyhedral sets, in combination with simplicial decomposition/column generation techniques, see Smith (1983a, 1983b).

3.3 Fukushima’s special case of gap function

Fukushima (1992) introduces a gap function, which may be identified as a special case from Auchmuty’s class, by using f(x) = \frac{1}{2} ∥x∥_{Q}^{2} =^{def} \frac{1}{2}x^{T}Qx, where Q is a given symmetric and positive definite matrix in ℜ^{n×n}. The problem [PGG] is shown to reduce to a projection problem, i.e., to find the unique point y(x) minimizing ∥y − (x − Q^{−1}F (x))∥_{Q} over y ∈ X. [This problem is equivalent to that solved iteratively in the projection algorithm, see e.g. Dafermos (1983).] Introducing the notation G̃_{Fu} for Fukushima’s special case of gap function, we have the following results. [For proofs of the results in this section, we refer to Fukushima (1992).]

Theorem 3.3 (Properties of G̃_{Fu})

1. G̃_{Fu} is a gap function.

2. (A fixed point characterization of Ω) x ∈ Ω ⇔ x = y(x).

3. If F : ℜ^{n} ↦ ℜ^{n} is continuous, then G̃_{Fu} is also continuous.

4. If F : ℜ^{n} ↦ ℜ^{n} is in C^{1} then G̃_{Fu} is also in C^{1}.

5. (Stationary points are in Ω) If F ∈ C^{1}, with a positive definite Jacobian ∇F on

X, we have that

∇G̃_{Fu}(x)^{T}(y − x) ≥ 0, ∀ y ∈ X ⇒ x ∈ Ω.  (3.3)

Fukushima also devises descent methods for asymmetric variational inequalities with positive definite Jacobian. Global convergence is guaranteed from the stationary point property (3.3), and the fact that the direction y(x) − x is a feasible direction of descent with respect to G̃_{Fu} whenever x ∉ Ω. We summarize these results below.

Theorem 3.4 (Descent properties) Let F : ℜ^{n} ↦ ℜ^{n} be in C^{1}, with positive definite Jacobian on X.

1. If x ∉ Ω, then

∇G̃_{Fu}(x)^{T}(y(x) − x) < 0.

2. If F also is strongly monotone on X, then for all x ∈ X,

∇G̃_{Fu}(x)^{T}(y(x) − x) ≤ −m_{F} ∥y(x) − x∥^{2} .

Theorem 3.5 (Global convergence) Let X be bounded, and let F : ℜ^{n} ↦ ℜ^{n} be in C^{1} with positive definite Jacobian on X.

1. Assume that x^{0} is chosen arbitrary in X, and that x^{k+1} is determined from x^{k} through the exact line search rule

min_{0≤t≤1} G̃_{Fu} (x^{k} + t (y (x^{k}) − x^{k})) .  (3.4)

Then, lim_{k→+∞} x^{k} = x^{∗}, i.e., the unique solution to [VIP].

2. Assume, in addition, that both F and its Jacobian are Lipschitz continuous on X, and that F is strongly monotone on X.

Replace the exact line search rule (3.4) by the Armijo (1964) step length rule, where the step length t_{k} in iteration k is chosen as t_{k} = β^{l_{k}}, where l_{k} is the smallest nonnegative integer l such that

G̃_{Fu} (x^{k} + β^{l} (y (x^{k}) − x^{k})) ≤ G̃_{Fu} (x^{k}) − αβ^{l} ∥y (x^{k}) − x^{k}∥^{2} ,  (3.5)

with α > 0 and 0 < β < 1.

Then the same conclusions as above hold, provided that α < m_{F}.

Fukushima’s special case of gap function has also been used in a descent algorithm based on Newton’s method, see Taji et al. (1991). This algorithm extends the globally convergent Newton methods by Marcotte and Dussault (1985, 1987, 1989), based on the primal gap function, G.

Remark 3.1 The authors became aware of Fukushima’s work after the original manuscript had been submitted. Some extensions (Theorems 4.4 and 4.9) of his results have been added in this revised version. We would like to point out that, from the interpretation and motivation made in Section 2, a gap function based on a symmetric approximation ∇f of F seems to be a more natural choice than a gap function based on a fixed matrix Q.

4 The primal generalized gap function

Based on the discussions made in the previous sections, we will here further investigate the characteristics of the primal generalized gap function and the mathematical program [OPGG]. We will in particular provide characterizations of Ω in terms of fixed points and stationary points, give sufficient conditions under which G̃ is continuously differentiable and convex, and establish globally convergent descent algorithms.

4.1 The properties of the generalized gap function

The following theorem provides a new fixed point characterization of solutions to variational inequalities, and extends the results of Theorems 3.1.7 and 3.3.2.

Theorem 4.1 (A fixed point characterization of Ω) For any x ∈ X, let Y (x) denote the set of optimal solutions to [PGG]. Then,

x ∈ Ω ⇔ x ∈ Y (x).

Proof

⇒) If x ∈ Ω, then G̃(x) = 0. From L̃(x, x) = 0, the result then follows immediately.

⇐) If x ∈ Y (x), then from [AVIP] it follows that

[−∇f(x) − F (x) + ∇f(x)]^{T} (y − x) = −F (x)^{T}(y − x) ≤ 0, ∀ y ∈ X,

which implies that x ∈ Ω. □

To simplify the subsequent discussion we shall henceforth let f be continuous on X. An immediate consequence of this property is that G̃ then also is continuous whenever it is everywhere finite; continuity of G̃ is important when developing descent algorithms, since the algorithmic map associated with the line search with respect to G̃ then is closed in the sense of Zangwill (1969).

Theorem 4.2 (Continuity properties of G̃ and Y)

1. For any x ∈ X, the set Y (x) is closed and convex, the mapping x ↦ Y (x) is closed and G̃ is l.s.c.

2. If X is bounded or if f is strongly convex on X, then for any x ∈ X, Y (x) is nonempty and bounded, and G̃ is continuous on X.

3. If X is bounded and F ∈ C^{1} on X, and f ∈ C^{2} on X, then G̃ is Lipschitz continuous on X.

4. If X is bounded and f is strictly convex on X, or if f is strongly convex on X, then, for any x ∈ X, Y (x) is a singleton and x ↦ Y (x) is continuous.

Proof

1. The closedness of Y (x) follows from the continuity of L̃ (Hogan, 1973), and its convexity from the convexity of the problem [PGG] (e.g. Minty, 1962). The l.s.c. property of G̃ is given in Theorem 2.2.

2. The first two results are well known. Continuity of G̃ follows from the continuity and boundedness of L̃.

3. The assumptions imply the continuity and boundedness of ∇_{x}L̃(x, y), which in turn implies the Lipschitz continuity of L̃ (Ortega and Rheinboldt, 1970, Corollary 3.2.4). By Theorem 2.1 of Clarke (1975) G̃ is then also Lipschitz continuous.

4. The first result is obvious. For the second result, see e.g. Hogan (1973). □

Under appropriate assumptions on F and f, it is also possible to show that the mapping x ↦ Y (x) is Lipschitz continuous, and this is therefore also true for ∇G̃. This property is crucial when establishing convergence using inexact line searches, see Lemma 4.1. The next theorem gives sufficient conditions for G̃ to be continuously differentiable on X.

Theorem 4.3 (Differentiability of G̃) Let F ∈ C^{1} on X and f ∈ C^{2} on X. If X is bounded and f is strictly convex on X, or if f is strongly convex on X, then G̃ ∈ C^{1} on X, with

∇G̃(x) = F (x) + [∇F (x)^{T} − ∇^{2}f(x)] (x − y(x)) ,  (4.1)

where y(x) is the unique solution to [PGG].

Proof G̃ is differentiable since Y (x) is a singleton from Theorem 4.2.4 [see also Rockafellar (1981, Proposition 3B)]. The continuity of ∇G̃ then follows from the continuity of ∇_{x}L̃, and ∇G̃(x) is given by ∇_{x}L̃(x, y(x)) [cf. Rockafellar (1981, Proposition 3H)]. □

It is therefore possible to equivalently reformulate asymmetric variational inequalities, with a differentiable mapping F, as a continuously differentiable minimization problem, see Harker and Pang (1990, p. 165).

One may note the major difference between the differentiability properties of G̃ compared to the ones for G. (Differentiability of G holds in general only under the restrictive assumption that the set X is strongly convex in the sense of Zuhovickiǐ et al. (1969a), which excludes applications where X is polyhedral.)

The next theorem characterizes solutions to [VIP] as stationary points of the problem [OPGG], for different monotonicity properties of F, and, correspondingly, different convexity properties of f.

Theorem 4.4 (Stationary point characterization of Ω) Let F ∈ C^{1} on X, and f ∈ C^{2} on X. Under either one of the following three additional assumptions, x^{∗} solves [VIP] if and only if x^{∗} is a stationary point of the problem [OPGG], i.e., if and only if

G̃′ (x^{∗}; x − x^{∗}) ≥ 0, ∀ x ∈ X.  (4.2)

1. X is bounded, and the matrix ∇F (x^{∗})^{T} − ∇^{2}f (x^{∗}) is positive definite.

2. X is bounded, f is strictly convex on X, and the matrix ∇F (x^{∗})^{T} − ∇^{2}f (x^{∗}) is positive semidefinite.

3. F is strongly monotone on X, f is strongly convex on X, ∇f is Lipschitz continuous

on X, and

M_{∇f} − m_{f} < m_{F} .  (4.3)

Proof Assume first that (4.2) does not hold for some \overline{x} ∈ X. For a sufficiently small ε > 0 it must then hold that G̃ (x^{∗} + ε (\overline{x} − x^{∗})) < G̃ (x^{∗}) = 0, which contradicts the optimality of x^{∗}. We have thus shown that a solution x^{∗} to [VIP] must satisfy (4.2).

We next turn to prove the reverse, for the three sets of assumptions, respectively. We first note that the directional derivative G̃′ (x^{∗}; x − x^{∗}) is given by [e.g., Rockafellar (1981, Proposition 3B)]

G̃′ (x^{∗}; x−x^{∗})= sup_{y∈Y (x^{∗})} (F (x^{∗})+[∇F (x^{∗})^{T}−∇^{2}f (x^{∗})] (x^{∗}−y))^{T} (x−x^{∗}) ≥ 0, ∀ x ∈ X.

(4.4)

The set Y (x^{∗}) is convex and compact, cf. Theorem 4.2.1 and Theorem 4.2.2. The restriction of (4.4) to x ∈ Y (x^{∗}) defines a point-to-set map from Y (x^{∗}) into itself, i.e., a map of the form x ↦ S(x), where S(x) is the set of optimal solutions to the problem defined in (4.4). The set S(x) inherits the properties of Y (x^{∗}), and furthermore, the map x ↦ S(x) is u.s.c., since the inner problem is linear in x. Using Kakutani’s (1941) fixed point theorem, we conclude that there is a \overline{y} ∈ Y (x^{∗}) such that \overline{y} ∈ S (\overline{y}). From (4.4) we then have that

(F (x^{∗}) + [∇F (x^{∗})^{T} − ∇^{2}f (x^{∗})] (x^{∗} − \overline{y}))^{T} (\overline{y} − x^{∗}) ≥ 0.  (4.5)

(Note that for a strictly convex f this holds directly from ∇G̃ (x^{∗})^{T} (y (x^{∗}) − x^{∗}) ≥ 0, by replacing \overline{y} with y (x^{∗}), since, in this case, Y (x^{∗}) is a singleton.)

Since \overline{y} ∈ Y (x^{∗}), we also have from (2.2) that

[−∇f (\overline{y}) − F (x^{∗}) + ∇f (x^{∗})]^{T} (x − \overline{y}) ≤ 0, ∀ x ∈ X.  (4.6)

Combining (4.5) and (4.6), with x = x^{∗}, we then have that

(\overline{y} − x^{∗})^{T} [∇F (x^{∗})^{T} − ∇^{2}f (x^{∗})] (\overline{y} − x^{∗}) ≤ [∇f (\overline{y}) − ∇f (x^{∗})]^{T} (x^{∗} − \overline{y}) .  (4.7)

We now turn to the three sets of assumptions.

1. From the positive definiteness of ∇F (x^{∗})^{T} − ∇^{2}f (x^{∗}) and the convexity of f, the inequality (4.7) can only hold if \overline{y} = x^{∗}. Replacing \overline{y} by x^{∗} in (4.6), we obtain that x^{∗} solves [VIP].

2. Follows from the same line of arguments as in 1.

3. Using the monotonicity and Lipschitz continuity properties of the maps F and ∇f in (4.7), it follows that

(m_{F} − M_{∇f} + m_{f}) ∥\overline{y} − x^{∗}∥^{2} ≤ 0,

which, together with (4.3), yields \overline{y} = x^{∗}, and as in 1., we conclude that x^{∗} solves [VIP]. □

It is a direct consequence of this theorem, that if a feasible point x is not a solution to [VIP], then there is a y ∈ Y (x) such that the direction y − x is a feasible direction of descent with respect to G̃. Based on this observation we shall, later on, develop descent algorithms.

Since the descent methods to be presented here are all asymptotically convergent, an optimal solution is, in general, not reached finitely, and it is of great practical interest to obtain a measure of the distance from an approximate solution point to the set Ω. The following theorem establishes an a posteriori error bound for strongly monotone variational inequalities, measured in terms of the value of the function G̃.

Theorem 4.5 (An a posteriori error bound) Let F be strongly monotone on X, and f ∈ C^{2} on X, with a Lipschitz continuous gradient on X. If f is chosen such that M_{∇f} < 2m_{F}, then for any x ∈ X,

∥x − x^{∗}∥^{2} ≤ \frac{2G̃(x)}{2m_{F} − M_{∇f}} .  (4.8)

Proof Combining the inequalities obtained from the strong monotonicity of F, and the fact that x^{∗} is the solution of [VIP], we obtain for any x ∈ X that

F (x)^{T} (x − x^{∗}) ≥ m_{F} ∥x − x^{∗}∥^{2} .  (4.9)

Now,

G̃(x) = f(x) − f(y(x)) + [F (x) − ∇f(x)]^{T} (x − y(x))
≥ f(x) − f (x^{∗}) + [F (x) − ∇f(x)]^{T} (x − x^{∗})  (y(x) solves [PGG])
≥ f(x) − f (x^{∗}) − ∇f(x)^{T} (x − x^{∗}) + m_{F} ∥x − x^{∗}∥^{2} (Equation (4.9))
≥ (m_{F} − \frac{M_{∇f}}{2} ) ∥x − x^{∗}∥^{2} ,  (∇f Lipschitz)

and the theorem is proved. □

The error bound (4.8) generalizes those obtained by Pang (1987) for the choices of f(x) = \frac{1}{2} ∥x∥^{2} (projection measure, Theorem 3.1) and f ≡ 0 (linear programming measure, Theorem 4.1), and the result obtained by Taji et al. (1991) for the choice of f(x) = \frac{1}{2} ∥x∥_{Q}^{2}. Notice that neither Lipschitz continuity [cf. Pang (1987)], nor differentiability, of F is necessary, and that the result holds regardless of any convexity properties of the function f.

The following corollary gives some interesting properties of G̃.

Corollary 4.1 (Coercivity of G̃) Under the assumptions of the theorem, G̃ has bounded level sets and is weakly coercive on X, i.e.,

lim_{{x∈X \atop ∥x∥→+∞}} G̃(x) = +∞.  (4.10)

Proof Follows directly from (4.8). □

Remark 4.1 Although G̃ is, in general, not convex, the corollary establishes properties of G̃ shared with convex functions. (Weak coercivity and boundedness of level sets are well known properties of strongly convex functions.)

Below we show that, for affine variational inequalities, G̃ can be constructed strictly convex.

Theorem 4.6 (Convexity of G̃) Let F be affine, i.e., F (x) = Ax − b. Let f be given by f(x) = \frac{1}{2}x^{T}Qx, where Q is symmetric and positive definite. Then G̃ is convex on X if the matrix A + A^{T} − Q is positive semidefinite, and strictly convex if this matrix is positive definite.

Proof If, for any fixed y ∈ X, the function L̃ is (strictly) convex in its x argument on the set X, then G̃, which is defined as the pointwise supremum of L̃, is also (strictly) convex. But

∇_{x}L̃(x, y) = [A + A^{T} − Q]^{T} (x − y),

so that

∇_{xx}^{2}L̃(x, y) = A + A^{T} − Q,

and the result follows directly. □

Note that the choice of f as the symmetrization made in Example 2.2 leads to a strictly convex gap function whenever A is positive definite. Moreover, this condition also leads to the stationary point property, see Theorem 4.4.2. Whether G̃ can be constructed convex for non-affine mappings F is an open question.

4.2 A descent algorithm for asymmetric variational inequalities

We conclude this section by developing descent algorithms, based on the stationary point characterization of Theorem 4.4. We also investigate the possibility of obtaining descent directions from inexact solutions of [PGG], and using inexact line searches; both these extensions of the basic scheme are of interest in implementations.

Theorem 4.7 (Descent properties) Let F ∈ C^{1} on X and f ∈ C^{2} on X. Also, for any x ∈ X, let Y (x) denote the set of optimal solutions to [PGG].

1. If X is bounded, x ∉ Ω, and the matrix ∇F (x)^{T} − ∇^{2}f(x) is positive definite, then there exists a y ∈ Y (x) such that

G̃′ (x; y − x) < 0.

2. If X is bounded, f is strictly convex on X, x ∉ Ω and the matrix ∇F (x)^{T} − ∇^{2}f(x) is positive semidefinite, then

∇G̃(x)^{T}(y(x) − x) < 0.

3. Assume that F is strongly monotone on X, and that f is strongly convex with a Lipschitz continuous gradient on X. Then, for any x ∈ X,

∇G̃(x)^{T}(y(x) − x) ≤ − (m_{F} + m_{f} − M_{∇f}) ∥y(x) − x∥^{2} .  (4.11)

Proof

1. Follows from expressing G̃′(x; y − x) as in (4.4), and using the same technique as in the proof of Theorem 4.4, together with (2.2), to establish the existence of a \overline{y} ∈ Y (x) such that G̃′ (x; \overline{y} − x) < 0.

2. Follows from the expression

G̃′ (x; y(x) − x) = ∇G̃(x)^{T}(y(x) − x),

combined with (2.2).

3. Proven as in 2. □

Note that for affine F and f quadratic, the conditions 2. reduce to the positive semidefiniteness of the matrix A^{T} − Q. The symmetrization given in Example 2.2 has the descent property whenever A is positive definite. Note also that, because of the generality of f, the conditions of Theorem 4.7 do not reduce to those of Theorem 3.4 when choosing f quadratic.

Using the stationary point property we have thus shown that the solution to [PGG], obtained when calculating G̃(x), defines a feasible descent direction with respect to G̃, whenever x ∉ Ω. We next show that, using an exact line search rule, the sequence of iteration points converges towards the unique solution x^{∗}, from any feasible starting point.

Theorem 4.8 (Global convergence) Let F ∈ C^{1} on X and f ∈ C^{2} on X. Let x^{0} be arbitrary in X, and let x^{k+1} be determined from x^{k} through the exact line search rule

min_{0≤t≤1} G̃ (x^{k} + td^{k}) ,

where d^{k} = y (x^{k}) − x^{k} with y (x^{k}) ∈ Y (x^{k}). Consider the following sets of assumptions.

1. X is bounded, the matrix ∇F (x)^{T} − ∇^{2}f(x) is positive definite on X, and the point y (x^{k}) is chosen as in Theorem 4.7.1.

2. X is bounded, f is strictly convex on X, and the matrix ∇F (x)^{T}−∇^{2}f(x) is positive semidefinite on X.

3. F is strongly monotone on X, f is strongly convex with a Lipschitz continuous gradient on X and chosen such that (4.3) holds. Further, X is bounded or M_{∇f} < 2m_{F} holds.

Under either one of the above sets of assumptions, [VIP] has a unique solution, and the sequence {x^{k}} converges to it.

Proof We begin by showing that the assumptions of Theorem A of Zangwill (1969) are fulfilled in all the three cases, i.e., i) that {x^{k}} stay in a compact subset of X, ii) that

G̃ (x^{k+1}) < G̃ (x^{k}) whenever x^{k} ∉ Ω, and x^{k} ∈ Ω if G̃ (x^{k+1}) ≥ G̃ (x^{k}), and iii) that the algorithmic map is closed.

i) For cases 1. and 2., this is obvious since X is compact. For case 3., either it holds from the compactness of X, or from the compactness of the level sets (cf. Corollary 4.1).

ii) Follows directly from Theorems 4.4 and 4.7, and the choice of step length.

iii) For case 1., it follows from Theorem 4.2.1 and the closedness of S(x) in the proof of Theorem 4.4, that the point-to-set map assigning the search direction d^{k} to the point x^{k} is closed. For cases 2. and 3., the continuity of this map follows from Theorem 4.2.4. Since the exact line search is well known to be closed for a continuous objective, the composite algorithmic map is closed for all three cases.

Thus, by Zangwill’s Theorem A, every accumulation point [from i), at least one such point exists] is optimal in [VIP]. For all three cases, it is straightforward to show that Ω is a singleton, and we conclude that {x^{k}} converges to the unique solution of [VIP]. □

Remark 4.2 Boundedness of X, which was assumed by Fukushima (1992), is not required for the global convergence of the algorithm. If x^{0} is infeasible, x^{0} can be replaced by y (x^{0}).

Global convergence with an Armijo step length rule can also be established, extending the result of Fukushima for the gap function G̃_{Fu}. It is well known that the use of the Armijo rule requires the gradient of the objective to be Lipschitz continuous; in this case, this property is a consequence of the Lipschitz continuity of the map x ↦ Y (x), which is established in the below lemma.

Lemma 4.1 (Lipschitz continuity of Y) Let F be Lipschitz continuous on X, and f strongly convex with a Lipschitz continuous gradient on X. Then the mapping x ↦ Y (x) is Lipschitz continuous on X with modulus \frac{M_{F} +M_{∇f}}{m_{f}}.

Proof Given arbitrary x^{1}, x^{2} ∈ X, combining the two inequalities (2.2), where we choose y = y (x^{2}) and y = y (x^{1}), respectively, and rearranging terms, we obtain

[F (x^{2}) − F (x^{1})]^{T} (y (x^{2}) − y (x^{1})) +

[∇f (x^{1})−∇f (x^{2})]^{T} (y (x^{2})−y (x^{1})) ≤ [∇f (y (x^{1}))−∇f (y (x^{2}))]^{T} (y (x^{2})−y (x^{1}))
≤ −m_{f} ∥y (x^{2}) − y (x^{1})∥^{2} ,

which implies that

\begin{aligned}m_{f} ∥y (x^{2}) − y (x^{1})∥^{2} & ≤ & (∥F (x^{2}) − F (x^{1})∥ + ∥∇f (x^{1}) − ∇f (x^{2})∥) ∥y (x^{2}) − y (x^{1})∥ \\ & ≤ & (M_{F} + M_{∇f}) ∥x^{2} − x^{1}∥ ∥y (x^{2}) − y (x^{1})∥ , \end{aligned}

and the result follows. □

Global convergence under an Armijo step length rule is shown below for the case of strongly monotone variational inequalities.

Theorem 4.9 (Global convergence under Armijo rule) Let the assumptions of Theorem 4.8.3 and Lemma 4.1 hold. Furthermore, let ∇F and ∇^{2}f be Lipschitz continuous on X, and replace the exact line search with the Armijo step length rule (3.5), where G̃ replaces G̃_{Fu}. Letting μ =^{def} m_{F} + m_{f} − M_{∇f} > 0, the conclusions of Theorem 4.8.3 hold if α is chosen such that α < μ.

Proof From Lemma 4.1 and the Lipschitz continuity of ∇F and ∇^{2}f, it follows that ∇G̃ is also Lipschitz continuous on X. Using this fact together with (4.7), we obtain, for all 0 ≤ t ≤ 1, that

G̃ (x^{k} + td^{k}) − G̃ (x^{k}) ≤ −t (μ − \frac{t}{2}M_{∇G̃}) ∥d^{k}∥^{2} ,

where d^{k} = y (x^{k}) − x^{k}. Tracing the proof of Theorem 4.2 of Fukushima (1992) we may conclude that the step length t_{k} = β^{l_{k}} satisfies

t_{k} > min {β, 2β(μ − α)/M_{∇G̃}} ,  (4.12)

and

G̃ (x^{k+1}) ≤ G̃ (x^{k}) − αt_{k} ∥d^{k}∥^{2} .  (4.13)

Since, from (4.13), the sequence {G̃ (x^{k})} is monotonically decreasing, it follows from

(4.12) that lim_{k→+∞} ∥d^{k}∥ = 0.

The sequence {x^{k}} is contained in a compact subset of X, and hence has at least one accumulation point, say \overline{x}. From the continuity property of y(x) (cf. Theorem 4.2), \overline{x} = y(\overline{x}), so that, by Theorem 4.1, \overline{x} solves [VIP]. The strong monotonicity of F then implies that \overline{x} must be the unique accumulation point, and we conclude that the sequence {x^{k}} converges to the unique solution to [VIP]. □

Remark 4.3 The subproblem solution y (x^{k+1}) is obtained in the Armijo line search for t_{k}, and is therefore provided with no extra computation.

Assume now that the algorithm for solving [PGG] is truncated prematurely, in the sense that it is terminated when, for some a priori determined ε > 0, a point y_{ε}(x) is found, satisfying

∇_{y}L̃ (x, y_{ε}(x))^{T} (y − y_{ε}(x)) ≤ ε, ∀ y ∈ X.  (4.14)

This implies, by the concavity of L̃ with respect to y, that G̃(x) ≤ L̃ (x, y_{ε}(x))+ε, i.e., that y_{ε}(x) is an ε-optimal solution to [PGG]. [Note that when X is polyhedral the termination criterion (4.14) is easily checked by solving the linear subproblem of the Frank-Wolfe algorithm, see, e.g., Migdalas (1990).] An interesting question then is if a point y_{ε}(x) satisfying (4.14) also satisfies ∇G̃(x)^{T} (y_{ε}(x) − x) < 0, for all sufficiently small ε. If the assumptions of Theorem 4.7.3 are satisfied, the theorem below establishes an affirmative answer.

Theorem 4.10 (Descent obtained from truncated subproblems) Let the assumptions of Theorem 4.7.3 be satisfied. Then, for any x ∈ X and ε ≥ 0,

∥y(x) − y_{ε}(x)∥^{2} ≤ \frac{ε}{m_{f}} .  (4.15)

Furthermore, if x ∉ Ω, (4.3) holds, and ε > 0 is chosen small enough (dependent of x), then

∇G̃(x)^{T} (y_{ε}(x) − x) < 0.

Proof From (2.2) and (4.14) we have

1. [−∇f(y(x)) − F (x) + ∇f(x)]^{T} (y − y(x)) ≤ 0, ∀ y ∈ X, and

2. [−∇f (y_{ε}(x)) − F (x) + ∇f(x)]^{T} (y − y_{ε}(x)) ≤ ε, ∀ y ∈ X.

Combining these inequalities, with y = y_{ε}(x) and y = y(x), respectively, we obtain, also using the strong convexity of f, that

m_{f} ∥y(x) − y_{ε}(x)∥^{2} ≤ [∇f(y(x)) − ∇f (y_{ε}(x))]^{T} (y(x) − y_{ε}(x)) ≤ ε,

which yields (4.15).

Now, from Theorems 4.3 and 4.7.3,

∇G̃(x)^{T}(y_{ε}(x) − x) = ∇G̃(x)^{T}(y(x) − x) + ∇G̃(x)^{T}(y_{ε}(x) − y(x))
≤ − (m_{F} + m_{f} − M_{∇f}) ∥y(x) − x∥^{2} + F (x)^{T}(y_{ε}(x) − y(x))
+(x − y(x))^{T} [∇F (x)^{T} − ∇^{2}f(x)] (y_{ε}(x) − y(x))
≤ − (m_{F} + m_{f} − M_{∇f}) ∥y(x) − x∥^{2} +
(∥F (x)∥ + ∥∇F (x)^{T} − ∇^{2}f(x)∥ · ∥x − y(x)∥) ∥y_{ε}(x) − y(x)∥
< 0,

if

∥y_{ε}(x) − y(x)∥ < −\frac{(m_{F} + m_{f} − M_{∇f}) ∥y(x) − x∥^{2}}{∥F (x)∥ + ∥∇F (x)^{T} − ∇^{2}f(x)∥ · ∥x − y(x)∥}.  (4.16)

Since the right hand side of this strict inequality is strictly positive whenever x ∉ Ω, it follows from (4.15) that (4.16) holds by choosing ε small enough. □

Remark 4.4 By further imposing Lipschitz continuity of f on X, the term ∥y(x) − x∥ may be estimated both from above and below by bounded positive measures in x, ε and y_{ε}(x) only, thus enabling the right hand side of (4.16) to be bounded from below. The resulting bound may then be used in a termination criterion for the solution of [PGG]. Also, this bound tends to zero when x approaches Ω, so that, in effect, the condition in (4.16) amounts to solving [PGG] accurately in the limit. Introducing a sequence {ε_{k}} with ε_{k} → 0, the global convergence of the overall scheme is also easily established from Theorem 4.8.

In the next section we shall extend Auchmuty’s class of gap functions, by introducing a sequence of functions f_{k}, with the same properties as the function f in Auchmuty’s framework. By associating with each step k in an iterative algorithm an appropriate function f_{k}, the problem [PGG] may thus even better approximate [VIP]. The introduction of this more general class of gap functions also results in interesting relationships with successive approximation-based algorithms of Cohen (1988), Noor (1992) and Dafermos (1983), and with the descent algorithms of Wu et al. (1991).

5 Generalizations of Auchmuty’s class of gap functions

Cohen (1988) develops an iterative algorithm for [VIP] using a successive approximation approach. Below we show that the subproblem solved in this algorithm is equivalent to [PGG], so that, immediately, a successive approximation algorithm based on the calculation of G̃ is established.

In our notation the subproblem, given x^{k} ∈ X, is to find x^{k+1} ∈ X solving

[C]  min_{x∈X} {f(x) + [εF (x^{k}) − ∇f (x^{k})]^{T} (x − x^{k})} ,

where ε is a positive constant. (Cohen refers to this problem as the auxiliary problem, and to the algorithm as the auxiliary problem principle.) If we, in Auchmuty’s framework, replace f by \frac{1}{ε}f, then it is not difficult to see that [PGG] is equivalent to [C]. The successive approximation algorithm, which thus is defined by letting x^{k+1} = y (x^{k}) in [PGG], is globally convergent through Cohen’s analysis. (A successive approximation algorithm can then be seen as an alternative to the descent approach, if the line search with respect to G̃ is considered computationally too expensive.)

The global convergence of the successive approximation variant of the descent methods of Section 4.2 is given below. The proof follows from Theorem 2.2 of Cohen (1988).

Theorem 5.1 (A successive approximation algorithm) Let F be strongly monotone and Lipschitz continuous on X, and let f be strongly convex on X. Let x^{0} be arbitrary in X, and let x^{k+1} be the (unique) solution to [PGG], defined at x^{k}. Then the sequence {x^{k}} converges towards the unique solution to [VIP], provided that

2m_{f} > \frac{M_{F}^{2}}{m_{F}} .  (5.1)

Remark 5.1 The algorithm defined in the theorem includes well known algorithms such as the projection algorithm [e.g. Dafermos (1983)]. It is interesting to note that the convergence criterion (5.1) amounts to choosing the function f so that it, in a sense, dominates the original mapping F, while in the descent approach the convergence criteria [e.g. (4.3)] amounts to precisely the opposite.

Remark 5.2 Noor (1992) recently extended Cohen’s algorithm to allow for variational inequality subproblems [cf. Remark 2.4 in Cohen (1988)]. This means that, in [AVIP], ∇f is replaced by a mapping a : ℜ^{n} ↦ ℜ^{n} that is not necessarily a gradient; thus [AVIP] does not reduce to the problem [PGG], i.e., to the calculation of a gap function.

Cohen develops his approach to also allow for F being a point-to-set map, and a varying parameter, ε_{k}, in [C]. Global convergence is now ensured by also letting {ε_{k}} fulfill the conditions

ε_{k} > 0, ∑_{k=0}^{+∞} ε_{k} = +∞ and ∑_{k=0}^{+∞} ε_{k}^{2} < +∞.

This result of course carries over directly to Auchmuty’s framework, provided that the function f is allowed to change with iteration (which would correspond to letting f_{k} =^{def} \frac{1}{ε_{k}} · f).

From the above discussion we are led to introduce a sequence {f_{k}} of functions, where each function f_{k} inherits the properties of f in Auchmuty’s framework. The rationale behind this generalization is that the gradients ∇f_{k} can be chosen so as to better approximate F (x^{k}) than the fixed gradient ∇f (cf. Section 2).

Introducing the sequence \{f_{k}\} thus introduces a sequence of gap functions \left\{{ \atop G̃_{k}}\right\}, where each function G̃_{k} inherits the properties of G̃, given in Theorems 2.1, 2.2 and 4.1. Without imposing a continuity assumption [such as equicontinuity in the sense of Rockafellar (1970)] on the sequence of functions f_{k}, the gap decreasing algorithms of Section 4.2 can not be easily extended to the more general case. Global convergence under equicontinuity assumptions is an open problem.

A natural way of ensuring continuity is to restrict the functions f_{k} to vary continuously, in the following sense. Introduce f : ℜ^{n} × X ↦ ℜ as a continuous function with respect to its second argument, and convex and continuously differentiable with respect to its first. In the point x^{k}, the function f_{k} = f (·, x^{k}) then replaces f in [PGG]. Since this function defines a special case of the sequence of functions f_{k}, the Theorems 2.1, 2.2 and 4.1 apply directly. [A proof of this fact is given in Patriksson (1991b).] Furthermore, the gap function G̃, defined through this special case of \left\{{ \atop G̃_{k}}\right\}, is continuous under the same conditions as in Theorem 4.2.2.

In the rest of this section we shall assume f to be a continuous function on ℜ^{n} × X as defined above (and let G̃, [PGG] and [AVIP] be defined accordingly), and consider this generalization of Auchmuty’s framework. We will show that the descent algorithms derived in Section 4.2 may be extended to the more general case of function f, and relate this class of algorithms to those of Dafermos (1983) and Wu et al. (1991). We first consider the works of Dafermos (1983).

Dafermos presents a general framework of successive approximation algorithms for [VIP]. Dafermos defines a smooth function h : X × X ↦ ℜ^{n}, with the properties i) h(x, x) = F (x), ∀ x ∈ X, and ii) ∇_{x}h(x, y) is symmetric and positive definite for any x, y ∈ X. A successive approximation algorithm is then defined through the subproblem

h (x^{k+1}, x^{k})^{T} (x − x^{k+1}) ≥ 0, ∀ x ∈ X.  (5.2)

(Due to assumption ii) above, (5.2) reduces to a strictly convex minimization problem.)

The sequence {x^{k}} is convergent towards the unique solution of [VIP] if

∥∇_{x}h^{−1/2} (x^{1}, y^{1}) · ∇_{y}h (x^{2}, y^{2}) · ∇_{x}h^{−1/2} (x^{3}, y^{3})∥ < 1, ∀ x^{i}, y^{i} ∈ X,  (5.3)

for i = 1, 2, 3. (Dafermos shows that Condition (5.3) implies strict monotonicity of F.) Several variational inequality algorithms have been analyzed in Dafermos’ framework, especially for economic equilibrium problems, see, e.g., Zhao and Dafermos (1991), and the references cited therein.

Patriksson (1991b) shows that the subproblem (5.2) and [PGG] are equivalent, in the sense that for any choice of function f, a function h may be chosen so that the subproblem (5.2) equals [PGG], and vice versa. (Dafermos’ class of methods may therefore be viewed as successive approximation variants of the descent algorithms presented in this paper, for the choice of functions f : ℜ^{n} × X ↦ ℜ.) The class of algorithms defined by Cohen (1988) is then clearly a special case of Dafermos’ class of algorithms. Since her convergence results actually do not require the mapping h to be symmetric [cf. Remark 2.2 in Dafermos (1983)], the same conclusion follows for Noor’s class of methods.

An interesting question provoked by this algorithmic equivalence result is whether the gap decreasing algorithms of Section 4.2 can be extended to include functions f : ℜ^{n}×X ↦ ℜ, and thereby introduce an accelerating line search in Dafermos’ class of algorithms. As is shown below (through another interesting algorithmic equivalence result), the answer is in the affirmative, at least for some choices of such functions f.

Let f be such that ∇_{y}f(x, x) =^{def} ∇_{y}f(y, x)|_{y=x} = 0, for all x ∈ X. Then [PGG] may be written as

min_{y∈X} {f(y, x) + F (x)^{T}(y − x)} ,  (5.4)

which is the subproblem of Wu et al. (1991). [Actually, Patriksson (1991b) shows that [PGG] and (5.4) are equivalent, in the same sense as for [PGG] and (5.2).] Wu et al. develop descent algorithms for [VIP] through the subproblem (5.4), and exact line searches with respect to the corresponding gap function. In the convergence analysis they consider the special case of choosing f(y, x) = \frac{1}{2}(y−x)^{T}Q(x)(y−x), where Q(x) is a symmetric and positive definite matrix on X. (This implies a direct generalization of Fukushima’s (1992) algorithm, where the matrix Q is fixed.) Their basic convergence result (Proposition 3.11) requires the matrix ∇Q(x)(y(x) − x) to be positive definite for all x ∈ X. This condition is, however, difficult to verify in practice.

Remark 5.3 In the case of nonlinear programming, the algorithmic classes of Cohen (1988) and Wu et al. (1991) reduce to the ones of Cohen (1980) and Patriksson (1991a), and to the ones of Migdalas (1990) and Tseng (1991), respectively. A partial list of corresponding algorithmic equivalence results can be found in Patriksson (1991b); further studies of algorithmic equivalence results are made in Patriksson (1993).

Remark 5.4 It seems, from the discussions made above, that it is an inherent property of the algorithms that their convergence conditions are severe and very difficult to verify in cases when f is allowed to be iteration dependent [cf. Condition (5.3) in Dafermos’ successive approximation method and the conditions in Wu’s et al. descent method], while the conditions in the case of iteration independent functions f may be stated in terms of the original data (including, typically, Lipschitz and strongly monotone constants) [cf. Condition (4.3) in Auchmuty’s framework, Condition (5.1) in Cohen’s framework and the conditions of Theorem 3.1 of Noor (1992)].

6 Concluding remarks

In this paper we have developed and unified mathematical programming reformulations of variational inequalities, as well as proposed new descent algorithms derived from these reformulations. We have also provided algorithmic equivalence results, relating Auchmuty’s framework to the algorithm classes of Dafermos (1983), Cohen (1988), Wu et al. (1991) and Noor (1992).

The framework of Auchmuty extends hitherto proposed optimization formulations, in the sense that the function f defining [OPG] may be chosen rather arbitrarily, and may therefore be used to more closely approximate the original mapping F (cf. Section 2). Moreover, it is possible to take problem structure into account when choosing the function f. As an example [due to Cohen (1988)], consider the case where the feasible set X is a Cartesian product, i.e., X = ∏_{i∈C} X_{i}, where X_{i} is a closed and convex set in ℜ^{n_{i}}, and ∑_{i∈C} n_{i} = n. [A variety of equilibrium problems can be cast in terms of such variational inequalities; see Pang (1985), Bertsekas and Tsitsiklis (1989, Section 3.5), and Harker and Pang (1990).] It may then be appropriate to choose

f(x) = ∑_{i∈C} f_{i} (x_{i}) ,

where each function f_{i} : X_{i} ↦ ℜ is convex and continuously differentiable on X_{i}. The evaluation of G̃(x), i.e., the solution of the convex problem [PGG], then decomposes into |C| problems of smaller dimensions. Since a decomposition takes place in the line search phase also, the computations involved in the descent algorithms of Section 4.2 could in this example effectively utilize parallel computing environments.

Patriksson (1993) combines the gap decreasing algorithm outlined above with cyclic decomposition with respect to the individual sets X_{i}. In this combined algorithm, search directions for G̃ are defined through the solution of [PGG] where, in some iteration k, all variables but x_{i_{k}}, i_{k} ∈ C, are fixed to their current values. The algorithm, which generalizes the standard cyclic (Gauss-Seidel) decomposition methods (see, e.g., Dafermos, 1983) to a descent algorithm, can be established convergent under conditions similar to those of Theorem 4.9, and if further each index i ∈ C is chosen at least once every B ≥ |C| successive iterations.

If the feasible set X is a closed and convex cone, then [VIP] reduces to the nonlinear complementarity problem, i.e., to find x^{∗} ∈ X such that [NCP] F (x^{∗}) ∈ X^{∗} and F (x^{∗})^{T} x^{∗} = 0,

where X^{∗} is the polar set of X. In the special case of X = ℜ_{+}^{n}, Cottle (1966) (see also Karamardian, 1971) shows that x^{∗} solves [NCP] if and only if x^{∗} minimizes F (x)^{T}x on the set {x ≥ 0 | F (x) ≥ 0}, and F (x^{∗})^{T} x^{∗} = 0. Auchmuty shows that [OPG] extends this optimization reformulation to a general nonlinear complementarity problem, by establishing that [OPG] in fact is equivalent to minimizing F (x)^{T}x on the set {x ∈ X | F (x) ∈ X^{∗} }, and that x^{∗} solves [NCP] if and only if F (x^{∗})^{T} x^{∗} = 0 (i.e., if and only if G (x^{∗}) = 0). Noting that, in this case, f ≡ 0, we may therefore conclude that the generalized gap function G̃ provides a means for making optimization reformulations of nonlinear complementarity problems; the one of Cottle is indeed a very special case of such an optimization reformulation. (New descent algorithms for [NCP] may thus be constructed, by specializing those algorithms developed in this paper that are valid also for variational inequalities over unbounded feasible sets.)

An interesting question for further studies regards the convexity properties of the gap function G̃. There are, seemingly (see Section 4.1), some connections between the descent, convexity and coercivity properties of G̃ that is not covered by the existing theory. Is it possible to characterize these connections, and to extend them to non-affine variational inequalities?

Some extensions of the developed theory and algorithms would be of interest to investigate. Such extensions include infinite-dimensional settings, as considered by Cohen (1988) and Noor (1992), an introduction of point-to-set maps F, as in Cohen (1988), equicontinuity of f_{k}, and the possibility to combine approximate line searches and truncated subproblems. Newton methods with line searches on gap functions have been shown to be globally convergent for the two special choices of f ≡ 0 and f(x) = \frac{1}{2}x^{T}Qx (see, e.g., Marcotte and Dussault, 1985, and Taji et al., 1991). The possibility of extending these algorithms to more general functions f is currently under investigation. Finally, the practical as well as the theoretical convergence rates obtained for various choices of functions f, and line search and subproblem truncation strategies, must be studied further.

Acknowledgements

The authors would like to thank Dr. Athanasios Migdalas for valuable discussions, and the referees for several remarks leading to improvements of the paper.

References

[] L. Armijo, “Minimization of functions having Lipschitz continuous partial derivatives,” Pacific Journal of Mathematics 16 (1964) 1–3.

[] G. Auchmuty, “Variational principles for variational inequalities,” Numerical Functional Analysis and Optimization 10 (1989) 863–874.

[] A. Auslender, Optimisation: Méthodes numériques (Masson, Paris, France, 1976).

[] M.S. Bazaraa and C.M. Shetty, Nonlinear programming: Theory and algorithms (John Wiley & Sons, New York, NY, 1979).

[] D.P. Bertsekas and J.N. Tsitsiklis, Parallel and distributed computation: Numerical methods (Prentice-Hall, London, 1989).

[] F.H. Clarke, “Generalized gradients and applications,” Transactions of the American Mathematical Society 205 (1975) 247–262.

[] G. Cohen, “Auxiliary problem principle and decomposition of optimization problems,” Journal of Optimization Theory and Applications 32 (1980) 277–305.

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

[] R.W. Cottle, “Nonlinear programs with positively bounded Jacobians,” SIAM Journal on Applied Mathematics 14 (1966) 147–158.

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

[] V.F. Demyanov and A.B. Pevnyi, “Numerical methods for finding saddle points,” USSR Computational Mathematics and Mathematical Physics 12 (1972) 11–52.

[] V.F. Demyanov and A.M. Rubinov, Approximate methods in optimization problems (Elsevier, New York, NY, 1970).

[] J.C. Dunn, “Convergence rates for conditional gradient sequences generated by implicit step length rules,” SIAM Journal of Control and Optimization 18 (1980) 473–487.

[] Yu.G. Evtushenko, Numerical optimization techniques (Optimization Software, Inc., New York, NY, 1985).

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

[] J.C. Hammond and T.L. Magnanti, “A contracting ellipsoid method for variational inequality problems,” Working Paper OR 160-87, Operations Research Center, Massachusetts Institute of Technology (Cambridge, MA, 1987).

[] 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) 161–220.

[] D.W. Hearn, “Network aggregation in transportation planning models, Part I,” Mathtec Final Report DOT-TSC-RSPD-78-8, Mathtec, Inc. (Princeton, NJ, 1978).

[] D.W. Hearn, “The gap function of a convex program,” Operation Research Letters 1 (1982) 67–71.

[] D.W. Hearn and S. Lawphongpanich, “A dual ascent algorithm for traffic assignment problems,” Conference paper, Joint Seminar on Urban Traffic Networks, Capri, Italy, 1989.

[] D.W. Hearn, S. Lawphongpanich, and S. Nguyen, “Convex programming formulations of the asymmetric traffic assignment problem,” Transportation Research 18B (1984) 357–365.

[] D.W. Hearn and S. Nguyen, “Dual and saddle functions related to the gap function,” Research Report 82-4, Department of Industrial and Systems Engineering, University of Florida (Gainesville, FL, 1982).

[] W.W. Hogan, “Point-to-set maps in mathematical programming,” SIAM Review 15 (1973) 591–603.

[] S. Kakutani, “A generalization of Brouwer’s fixed point theorem,” Duke Mathematics Journal 8 (1941) 457–459.

[] S. Karamardian, “Generalized complementarity problem,” Journal of Optimization Theory and Applications 8 (1971) 161–168.

[] S. Karamardian, “An existence theorem for the complementarity problem,” Journal of Optimization Theory and Applications 18 (1976) 445–454.

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

[] S. Lawphongpanich and D.W. Hearn, “Simplicial decomposition of the asymmetric traffic assignment problem,” Transportation Research 18B (1984) 123–133.

[] P. Marcotte, “A new algorithm for solving variational inequalities with application to the traffic assignment problem,” Mathematical Programming Study 33 (1985) 339–351.

[] P. Marcotte, “Gap-decreasing algorithms for monotone variational inequalities,” Conference paper, ORSA/TIMS Joint National Meeting, Miami Beach, FL, 1986.

[] 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.

[] P. Marcotte and J.-P. Dussault, “A note on a globally convergent Newton method for solving monotone variational inequalities,” Operations Research Letters 6 (1987) 35–42.

[] P. Marcotte and J.-P. Dussault, “A sequential linear programming algorithm for solving monotone variational inequalities,” SIAM Journal of Control and Optimization 27 (1989) 1260–1278.

[] P. Marcotte and J. Guélat, “Adaptation of a modified Newton method for solving the asymmetric traffic equilibrium problem,” Transportation Science 22 (1988) 112–124.

[] A. Migdalas, “A regularization of the Frank-Wolfe algorithm,” Report LiTH-MAT-R-90-10, Linköping Institute of Technology (Linköping, Sweden, 1990).

[] G.J. Minty, “Monotone (non-linear) operators in Hilbert space,” Duke Mathematics Journal 29 (1962) 341–346.

[] S. Nguyen and C. Dupuis, “An efficient method for computing traffic equilibria in networks with asymmetric transportation costs,” Transportation Science 18 (1984) 185–202.

[] M.A. Noor, “General algorithm for variational inequalities,” Journal of Optimization Theory and Applications 73 (1992) 409–413.

[] J.M. Ortega and W.C. Rheinboldt, Iterative solution of nonlinear equations in several variables (Academic Press, New York, NY, 1970).

[] J.-S. Pang, “Asymmetric variational inequality problems over Cartesian product sets: applications and iterative methods,” Mathematical Programming 31 (1985) 206–219.

[] J.-S. Pang, “A posteriori error bounds for the linearly-constrained variational inequality problem,” Mathematics of Operations Research 12 (1987) 474–484.

[] M. Patriksson, “Partial linearization methods in nonlinear programming,” Report LiTH-MAT-R-91-11, Linköping Institute of Technology (Linköping, Sweden, 1991). Forthcoming in Journal of Optimization Theory and Applications 78 (1993).

[] M. Patriksson, “A unified description of iterative algorithms for traffic equilibria,” Report LiTH-MAT-R-91-34, Linköping Institute of Technology (Linköping, Sweden, 1991). Forthcoming in European Journal of Operational Research.

[] M. Patriksson, “A unified framework of descent algorithms for nonlinear programming and variational inequalities,” Ph.D. thesis, Linköping University (Linköping, Sweden, 1993).

[] M.E. Primak, “A computational process of search for equilibrium points,” Cybernetics 9 (1975) 106–113.

[] R.T. Rockafellar, Convex analysis (Princeton University Press, Princeton, NJ, 1970).

[] R.T. Rockafellar, The theory of subgradients and its applications to problems of optimization: Convex and nonconvex functions (Heldermann Verlag, Berlin, 1981).

[] M.J. Smith, “The existence and calculation of traffic equilibria,” Transportation Research 17B (1983) 291–303.

[] M.J. Smith, “An algorithm for solving asymmetric equilibrium problems with a continuous cost-flow function,” Transportation Research 17B (1983) 365–371.

[] K. Taji, M. Fukushima, and T. Ibaraki, “A globally convergent Newton method for solving strongly monotone variational inequalities,” Technical Report 91006, Kyoto University (Kyoto, Japan, 1991). Forthcoming in Mathematical Programming.

[] P. Tseng, “Decomposition algorithm for convex differentiable minimization,” Journal of Optimization Theory and Applications 70 (1991) 109–135.

[] J.H. Wu, M. Florian, and P. Marcotte, “A general descent framework for the monotone variational inequality problem,” Publication 723, Centre de recherche sur les transports, Université de Montréal (Montréal, Canada, 1991).

[] W.I. Zangwill, Nonlinear programming: A unified approach (Prentice-Hall, Englewood Cliffs, NJ, 1969).

[] L. Zhao and S. Dafermos, “General economic equilibrium and variational inequalities,” Operations Research Letters 10 (1991) 369–376.

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

[] S.I. Zuhovickiǐ, R.A. Poljak, and M.E. Primak, “Numerical methods of finding equilibrium points of n-person games,” in: Proceedings of the First Winter School of Mathematical Programming at Drogobych (1969) no. 1, pp. 93–130.

[] S.I. Zuhovickiǐ, R.A. Poljak, and M.E. Primak, “On an n-person concave game and a production model,” Soviet Mathematics Doklady 11 (1970) 522–526.

[] S.I. Zuhovickiǐ, R.A. Poljak, and M.E. Primak, “Concave multiperson games. Numerical methods,” Matekon 9 (1973) 10–30.