147

数理解析研究所講究録
第 741 巻 1991 年 147-161

Equivalent Differentiable optimization Problems andDescent Methods for Asymmetric Variational Inequality

Problems
Masao FUKUSHIMA
Department of Applied Mathematics and Physics
Faculty of Engineering
Kyoto University
Kyoto 606 Japan
Abstract

Whether or not the general asymmetric variational inequality prob-

lem can be formulated as a differentiable optimization problem has been an open
question. This paper gives an affirmative answer to this question. We provide

a new optimization problem formulation of the variational inequality problem
and show that its objective function is continuously differentiable whenever the

mapping involved in the latter problem is continuously differentiable. We also
show that under appropriate assumptions on the latter mapping, any stationary

point of the optimization problem is a global optimal solution, and hence solves

the variational inequality problem. We discuss descent methods for solving theequivalent optimization problem and comment on systems of nonlinear equations

and nonlinear complementarity problems.

1

Introduction

In this paper we consider the problem of finding a point$x^{*}\in S,$\langle $F(x^{*}),x-x^{*}$ }1$\geq 0$$x^{*}\in R^{n}$such thatfor all $x\in S$ ,

(1.1)

148
where
and

$S$

$\langle\cdot, \cdot\rangle$

is a nonempty closed convex subset of
denotes the inner product in$R^{n}$$R^{n},$$F$

is a mapping from$R^{n}$

into itself,. This problem is called the variational inequality

problem and has been used to study various equilibrium models in economics, operations
research, transportation and regional science [2,5,7,13].
In the special case where $S=R_{+}^{n}$ , the nonnegative orthant in$R^{n}$, problem (1.1) can be

rewritten as the nonlinear complementarity problem$x^{*}\geq 0,$$F(x^{*})\geq 0$and$(x^{*}, F(x^{*})\rangle$

$=0$

.

(1.2)

When $S=R^{n}$ , problem (i.1) simply reduces to solving the system of nonlinear equations$F(x)=0$ .

(1.3)

Therefore it is quite natural that many algorithms developed to solve the variational inequality problems are generalizations of the classical methods for systems of equations, such as

Newton’s method, SOR methods, projection methods and nonlinear Jacobi (diagonalization)

methods $[3,15]$ .
Yet another approach for solving the variational inequality problem (1.1) is to transform

it into an equivalent minimization problem. An obvious advantage of this approach lies in
the fact that the latter problem may be solved by descent algorithms which possess a global

convergence property. A typical situation. where problem (1.1) can be reformulated as an
optimization problem is that $F(x)$ is the gradient of a differentiable function$\theta$: $R^{n}arrow R$ , inwhich case problem (1.1) is equivalent to the problem
minimize$\theta(x)$subject to $x\in S$ .

As is well known [14, Theorem 4.1.6], when the mapping $F$ is differentiable, a necessary andsufficient condition for $F$ to satisfy the above condition is that the Jacobian matrix
is synmetric for all$x$$\nabla F(x)$. Unfortunately we cannot expect this symmetry condition to hold inmany practical equilibrium models.
For the general asymmetric variational inequality problem (1.1), a different optimization
approach has been proposed [1,11,12], on the basis of the so called gap function $g:R^{n}arrow R$

defined by$g(x)= \max\{\langle F(x), x-y\rangle|y\in S\}$

2

.

(1.4)

149
This function was introduced by Auslender [1] for variational inequality problems and laterby Hearn [8] for convex programming problems. It is easy to see that $g(x)\geq 0$ for all $x\in S$

and $g(x^{*})=0$ whenever$x^{*}$

satisfies (1.1). Hence the variational inequality problem (1.1) isequivalent to the problem

minimize$g(x)$

By the definition (1.4), the gap functionthat the function

$g$

$g$

subject to $x\in S$ .

is in general nondifferentiable. Auslender [1] shows

is differentiable provided the set$S$

is strongly convex. Unfortunately

this assumption is not satisfied in many important applications such as traffic or market
equilibrium problems where the set$S$

is polyhedral convex.

Thus whether or not the general asymmetric variational inequality problem can be formulated as a differentiable optimization problem has been an open question [7]. This paper
gives an affirmative answer to it. We shall provide a new optimization problem formulationof problem (1.1), in which the objective function is continuously differentiable whenever so

is the mapping $F$ . Since the set$S$

is only as sumed to be closed and convex, a wide variety ofpractical applications may be treated within this framework.

This paper is organized as follows: In Section 2 we review some preliminary results

conceming the projection operators and monotone mappings. In Section 3 we formulate an
optimization problem equivalent to the variational inequality problem (1.1). We also show
that, under appropriate assumptions, the objective function of the optimization problem isdifferentiable and any stationary point is a global optimal solution of the problem. In Section 4

we discuss descent algorithms for solving the equivalent optimization problem. Finally in
Section 5 we comment on systems of nonlinear equations and nonlinear complementarity
problems.

2
Let

Preliminaries$||\cdot||_{G}$denote the norm in$R^{n}$

defined bypositive definite matrix. Given the norm$||\cdot||_{G}$3$||x||_{G}=\langle x,Gx\}^{\frac{1}{2}}$, where, the projection of a point$G$

is a symmetric$x$onto the closed

150

convex set$S$, denoted by Proj $s,c(x)$ , is defined as the (unique) solution of the problem
minimize

The projection operator Proj

$S,G(\cdot)$

subject to $y\in S$ .

$||y-x||_{G}$is nonexpansive, i.e.,$||Proj_{S,G}(x)-Proj_{S,G}(x’)||_{G}\leq||x-x’||_{G}$for all $x,$ $x’\in R^{n}$ .

(2.1)

for all $y\in S$ .

(2.2)

Moreover, for each $x\in R^{n}$ , Proj $s,c(x)$ satisfies\langle –Proj $s,c(x),$ $G(y$ –Proj$x$$S,G(x))\rangle$$\leq 0$

A proof of these results for the special case where $G=I$ may be found in [1, Chapter 5] [10,Chapter 1], and can be extended to the present case in a straightforward manner.
The mapping $F:R^{n}arrow R^{n}$ is said to be monotone on$\{F(x)-F(x’),x-x’\}\geq 0$

and strictly monotone on

$S$

$S$

if

for all $x,$ $x’\in S$ ,(2.3)

if strict inequality holds in (2.3) whenever $x\neq x’$ . It is known[14, Theorem 5.4.3] that, if $F$ is continuously differentiable and the Jacobian matrix $\nabla F(x)$is positive definite for all $x\in S$ , i.e.,$\langle d, \nabla F(x)d\rangle>0$then $F$ is strictly monotone on$S$

for all $x\in S,$ $d\in R^{n}(d\neq 0)$ ,. Note that we do not require$\nabla F(x)$(2.4)
to be symmetric in(2.4). The mapping $F$ is said to be strongly (or uniformly) monotone with modulus $\mu>0$

on

$S$

if
$\{F(x)-F(x’),x-x’\}\geq\mu||x-x’||^{2}$

where

$||$

. Il denotes the Euclidean norm in$R^{n}$

for all $x,$ $x’\in S$ ,(2.5)

. It can be shown [14, Theorem 5.4.3] that,when $F$ is continuously differentiable, a necessary and sufficient condition for (2.5) isfor all $x\in S,$ $d\in R^{n}$ .

$\{d, \nabla F(x)d\}\geq\mu||d||^{2}$

Clearly any strongly monotone mapping is strictly monotone.

4

(2.6)

151
3

Equivalent optimization problem

In the rest of the paper we suppose that an $n\cross n$ symmetric positive definite matrix

$G$

is

given. Let $x\in R^{n}$ be temporarily fixed and consider the following problem:
minimize \langle $F(x),y-x$ }$+ \frac{1}{2}\langle y-x,$$G(y-x)$ }subject to $y\in S.$(3.1)

Since this problem is essentially equivalent to the problem

minimizesubject to $y\in S$ ,$||y-(x-G^{-1}F(x))||_{G}^{2}$the optimal solution of (3.1) is precisely $Proj_{S,G}(x-G^{-1}F(x))$ , the projection of the point$x-G^{-1}F(x)$ onto the set $S$ with respect to the norm $||\cdot||c$. Thus for each , we can uniquely$x$determine the optimal solution of (3.1). Hereafter we shall denote it by $H(x)$ for notational

simplicity. Namely we define the mapping $H$ : $R^{n}arrow R^{n}$ as$H(x)=Proj_{S,G}(x-G^{-1}F(x))$ .

(3.2)

The mapping $H$ thus defined yields a fixed point characterization of the solution of thevariational inequality problem (1.1).

Proposition 3.1 For each $x\in R^{n}$ , let $H(x)$ be the unique optimal solution of problem(3.1), or equivalently, let $H$ : $R^{n}arrow R^{n}$ be the mapping defined by (3.2). Thenvariational inequality problem (1.1) if and only if

$x$

$x$

solves theis a fixed point of the mapping $H,$ $i.e.$ ,$x=H(x)$ .

Proof

See for example [2].

$\square$Now we are in a position to state the optimization problem equivalent to the variational
inequality problem (1.1). Let us define the function$f$: $R^{n}arrow R$ by$f(x)=-\{F(x),$ $H(x)-x\rangle$ $- \frac{1}{2}\{H(x)-x,$ $G(H(x)-x)\rangle$ ,(3.3)

i.e., $f(x)$ is the negative of the optimal value of problem (3.1), and consider the problem

minimizesubject to $x\in S$ .

$f(x)$(3.4)

The next theorem establishes the equivalence of the variational inequality problem (1.1) andthe optimization problem (3.4).
5

152
Theorem 3.1 Let the function $f$ : $R^{n}arrow R$ be defined by (3.3). Then $f(x)\geq 0$ for all $x\in S$ ,and $f(x)=0$ if and only if$x$solves the variational inequality problem (1.1). Hence$x$

solvesthe optimization problem (3.4) if and only if it solves the variational inequality problem (1.1).

Proof

The function$f$

can be written as$f(x)= \frac{1}{2}\{||G^{-1}F(x)||_{G}^{2}-||H(x)-(x-G^{-1}F(x))||_{G}^{2}\}$Since $||G^{-1}F(x)||_{G}$ equals the G-distance between$G^{-1}F(x))||_{G}$

$x$

.

(3.5)

and $x-G^{-1}F(x)$ , and $||H(x)-(x-$is the G-distance between $x-G^{-1}F(x)$ and its projection $H(x)$ onto

$S$

, we

have $f(x)\geq 0$ for all $x\in S$ . Moreover the definition of $H(x)$ implies that those distances areequal, i.e. $f(x)=0$ , if and only if $x=H(x)$ . This along with Proposition 3.1 proves the firstpart of the theorem. The last part of the theorem is a direct consequence of the first part.
$\square$Note that Theorem 3.1 relies upon no specific assumptions on $F$ and$f$. In order forthe equivalent optimization problem (3.4) to be practically useful, however, the objectivefunction$f$

has to possess some desirable properties. Fortunately we can show that, for any

closed convex set
$F$

$S$

, the function$f$is continuously differentiable whenever so is the mapping. This is in contrast with the gap function$g$defined by (1.4), which in general fails toinherit the smoothness property from $F$ .
Theorem 3.2 If the mapping $F$ : $R^{n}arrow R^{n}$ is continuous, then the function$f$: $R^{n}arrow R$

defined by (3.3) is also continuous. Furthermore, if is $\omega ntinuously$ differentiable, thenis also continuously differentiable and its gradient is given by$F$$\nabla f(x)=F(x)-[\nabla F(x)-G](H(x)-x)$ .

Proof
$H$

$f$

(3.6)

Suppose that $F$ is continuous. Then it follows from (2.1) and (3.2) that the mapping

is continuous. Hence, by (3.3), the function$f$is also continuous. To prove the second halfof the theorem, let us define the function $h:R^{n}\cross Sarrow R$ by$h(x,y)=\{F(x),$ $y-x$ ) $+ \frac{1}{2}\{y-x,$ $G(y-x)\rangle$ .

6

(3.7)

153
Clearly, when $F$ is continuously differentiable, so is the function$h$. Since, by definition,(3.8)$f(x)=- \min\{h(x,y)|y\in S\}$and since the minimum on the right-hand side of (3.8) is uniquely attained at $y=H(x)$ , itfollows from [1, Chapter 4, Theorem 1.7] that$f$is differentiable and$\nabla f(x)=-\nabla_{x}h(x,H(x))$

The formula (3.6) now follows from (3.7) and (3.9).

$\nabla f(x)$is given by

.

(3.9)

$\square$Now let us have a closer look at the relationship between the variational inequality problem(1.1) and the optimization problem (3.4). Theorem 3.1 says that solving (1.1) amounts tofinding a global optimal solution of problem (3.4). However, since the function$f$is in general

nonconvex, problem (3.4) may have local minima or stationary points which do not minimize$f(x)$ over $x\in S$ globally. This could be a serious drawback of the present approach, because

most of the existing optimization algorithms are only able to find local optimal solutions whenapplied to nonconvex problems. Fortunately, this difficulty can be completely avoided whenthe mapping $F$ is continuously differentiable and$\nabla F(x)$is positive definite for all $x\in S$ .

Theorem 3.3 Assume that the mapping $F:R^{n}arrow R^{n}$ is continuously differentiable and its
Jacobian matrix$\nabla F(x)$is positive definite for all $x\in S$ . If$x$is a stationary point of problem(3.4), $i.e.$ ,
(

then

$x$

$\nabla f(x),$ $y-x\rangle$$\geq 0$for all $y\in S$,(3.10)

is a global optimal solution of problem (3.4), and hence it solves the variational in-equality problem (1.1).
Proof

Suppose that$x$satisfies (3.10). Then substituting the formula (3.6) into (3.10) andputting $y=H(x)$ yield\langle $F(x)+G(H(x)-x),$ $H(x)-x$ } $\geq\langle\nabla F(x)(H(x)-x),$ $H(x)-x)$ .

(3.11)On the other hand, since $H(x)=Proj_{S,G}(x-G^{-1}F(x))$ , it follows from (2.2) that$\langle x-G^{-1}F(x)-H(x), G(y-H(x))\rangle\leq 0$

7

for $aUy\in S.$(3.12)

154
In particular, putting $y=x$ in (3.12), we obtain$\langle x-G^{-1}F(x)-H(x), G(x-H(x))\rangle$$=$\langle $F(x)+G(H(x)-x),$ $H(x)-x$ }$\leq$$0$.

(3.13)

Thus by (3.11) and (3.13), we have$\langle\nabla F(x)(H(x)-x),H(x)-x\rangle\leq 0$.

(3.14)

However, since $\nabla F(x)$ is positive definite, it follows from (2.4) that the inequality (3.14) holds

only if $x=H(x)$ . By Proposition 3.1, this implies thatproblem (1.1) and, by Theorem 3.1,

4

$x$

$x$

solves the variational inequality

is a global optimal solution of problem (3.4).

$\square$Descent methods

Let the mapping $F$ : $R^{n}arrow R^{n}$ be continuously differentiable. Then by Theorem 3.2, theobjective function$f$of problem (3.4) is also continuously differentiable and its gradient$\nabla f(x)$can be calculated from (3.6). We may therefore apply any of the existing gradient-type
algorithms to solve problem (3.4). In the following, however, we shall not further discuss thegradient-based approaches, but explore the possibility of utilizing the vector
$d$

$=$

$H(x)-x$$=$

Proj $s,c(x-G^{-1}F(x))-x$(4.1)

as a search direction at $x\in S$ . Since (4.1) does not involve the Jacobian matrix
vector$d$

may be much easier to compute than the gradient$\nabla f(x)$$\nabla F(x)$, the, particularly when evalua-tion of $\nabla F(x)$ is expensive (see (3.6)). The next proposition shows that, under monotonicity

assumptions on $F$ , the vector
$f$

at

$x$

$d$

given by (4.1) is actually a descent direction of the function.

Proposition 4.1 Let the mapping $F:R^{n}arrow R^{n}$ be continuously differentiable. If the Jacobian matrix $\nabla F(x)$ is positive definite on$S$, then for each $x\in S$ the vector $d=H(x)-x$

satisfies the descent condition$\langle\nabla f(x),d\rangle<0$

8

,

(4.2)

155
whenever $d\neq 0$ . Moreover if $F$ is strongly monotone with modulus $\mu>0$ on$S_{f}$

then for each$x\in S$$\langle\nabla f(x),d\rangle\leq-\mu||d||^{2}$

.

(4.3)

From (3.6) and (4.1), we haveProof$\langle\nabla f(x), d\rangle=\langle F(x)+G(H(x)-x),H(x)-x\rangle-(\nabla F(x)(H(x)-x),H(x)-x\rangle$

.

(4.4)

But since $H(x)=Proj_{S,G}(x-G^{-1}F(x))$ , it follows from (2.2) that\langle $x-G^{-1}F(x)-H(x),G(y-H(x))$ }$\leq 0$for all $y\in S$ ,which in turn implies$\langle F(x)+G(H(x)-x), H(x)-x\rangle\leq 0$

.

(4.5)

Combining (4.4) and (4.5), we obtain.

$\{\nabla f(x), d\}\leq-\{\nabla F(x)(H(x)-x),H(x)-x\rangle=-\langle\nabla F(x)d, d\rangle$(4.6)

Thus if $\nabla F(x)$ is positive definite, then (4.2) follows from (2.4) and (4.6), while if $F$ is strongly
monotone, then (4.6) together with (2.6) implies (4.3).

$\square$

The following theorem establishes global convergence of the algorithm that uses the search
directions $d=H(x)-x$ with the exact line search rule.

Theorem 4.1 Let

be a sequence generated by the iteration$\{x^{k}\}$$x^{k+1}=x^{k}+t_{k}d^{k}$where$d^{k}$, $k=0,1,2,$$\ldots$,

are given by $d^{k}=H(x^{k})-x^{k}$ and $t_{k}\in[0,1]$ are determined from$f(x^{k}+t_{k}d^{k})= \min\{f(x^{k}+td^{k})|0\leq t\leq 1\}$

Suppose that

$S$

.

(4.7)

is compact and that the mapping $F:R^{n}arrow R^{n}$ is continuously differentiable

and $\nabla F(x)$ is positive definite for all $x\in S.$
generated sequence$\{x^{k}\}$lies in$S$

Then, for any starting point $x^{0}\in S_{f}$ theand converges to the unique solution of the variational

inequality problem (1.1).
9

156First notice that the continuity of $F$ together with the compactness of

Proof

$S$

impliesthat problem (1.1) has a solution [10, page 12]. Moreover since the given hypotheses on $F$
imply that $F$ is strictly monotone, the solution of (1.1) is unique [10, page 84].

Since the points$x^{k}$

and $H(x^{k})=x^{k}+d^{k}$ both belong tofollows fron the convexity of$S$

that the sequence$\{x^{k}\}$$S$

and since $0\leq t_{k}\leq 1$ , itis contained in S. To prove global

convergence of the algorithm we shall use Zangwill’s Convergence Theorem A [16, page 91].
By Proposition 4.1, the direction$d$satisfies the descent condition (4.2) under the given

hypotheses, and $d=H(x)-x$ is continuous with respect to$x$, whenever $F$ is continuous.

Moreover since the point-to-set mapping that as signs to each pair $(x, d)$ the points determinedby the exact line search (4.7) is closed in the sense of [16], the algorithmic map associatedwith the iterative procedure under consideration is also closed. Consequently, the abovementioned convergence theorem guarantees that any accumulation point of the generated

sequence$\{x^{k}\}$solves problem (1.1). Since the solution of (1.1) is unique by the assumptions

on $F$ , the entire sequence is convergent to the solution of (1.1).

$\square$Under the strong monotonicity assumption on the mapping $F$ , we can establish a stronger

convergence result which allows the use of inexact line search procedures. Specifically weconsider here the following Armijo-type steplength rule: Letthat $\alpha>0$ and $0<\beta<1$ . For the current iterate
the steplength$t_{k}$

as$t_{k}=\beta^{\ell_{k}}$where$\ell_{k}$$x^{k}$

and$\alpha$$\{x^{k}\}$is the smallest nonnegative integer$d^{k}$.

$\ell$$d^{k}$, determine

such that(4.8)

be a sequence generated by the iteration$x^{k+1}=x^{k}+t_{k}d^{k}$where

be given constants suchand the search direction$f(x^{k}+\beta^{\ell}d^{k})\leq f(x^{k})-\alpha\beta^{\ell}||d^{k}||^{2}$

Theorem 4.2 Let$\beta$, $k=0,1,2,$$\ldots$,

are given by $d^{k}=H(x^{k})-x^{k}$ and $t_{k}\in[0,1]$ are determined by the Armijo-type

rule (4.8). Suppose that the set$S$

is compact and the mapping $F:R^{n}arrow R^{n}$ is differentiable

and strongly monotone with modulus $\mu>0$ on S. Suppose also that $F(x)$ and $\nabla F(x)$ are10

157
Lipschitz continuous on $S,$ $i.e.$ , there exist constants $L_{0}>0$ and $L_{1}>0$ such that$||F(x)-F(x’)||\leq L_{0}||x-x’||$for all$x,$ $x’\in S$

,

(4.9)

and

for all$||\nabla F(x)-\nabla F(x’)||\leq L_{1}||x-x’||$$x,$ $x’\inS$,(4.10)

where the norm on the left-hand side of (4.10) is an appropriate matrix norm. Then thegenerated sequence$\{x^{k}\}$lies in$S$

and converges to the unique solution of the variational

inequality problem (1.1) for any starting point $x^{0}\in S$ , if the positive constantchosen sufficiently small so that$\alpha<\mu$in (4.8) is.

Since (2.1), (3.2) and (4.9) ensure that the mapping $H$ is Lipschitz continuous, itProoffollows from (3.6) that the Lipschitz continuity (4.10) of$\nabla f(x)$$\alpha$$\nabla F(x)$implies the same property of, i.e., there exists a constant $L>0$ such that$||\nabla f(x)-\nabla f(x’)||\leq L||x-x’||$for all $x,x’\in S$ .

(4.11)

It follows from (4.3) and (4.11) that, for $0\leq t\leq 1$$f(x^{k}+td^{k})-f(x^{k})$$=$$\int_{0}^{t}\{\nabla f(x^{k}+sd^{k}), d^{k}\}ds$$=$$t \{\nabla f(x^{k}), d^{k}\}+\int_{0}^{t}\{\nabla f(x^{k}+sd^{k})-\nabla f(x^{k}),d^{k}\}ds$$\leq$$=$$- \mu t||d^{k}||^{2}+\int_{0}^{t}Ls||d^{k}||^{2}ds$$(- \mu t+\frac{1}{2}Lt^{2})||d^{k}||^{2}$.

Then it is not difficult to see that the inequality$f(x^{k}+td^{k})\leq f(x^{k})-\alpha t||d^{k}||^{2}$

holds for all$t$satisfying $0 \leq t\leq\min\{1,2(\mu-\alpha)/L\}$ , provided thatfrom the manner in which the steplength$t_{k}$$\alpha<\mu$

is determined, it follows that$t_{k}> \min\{\beta,2\beta(\mu-\alpha)/L\}$for all .
$k$11. Consequently,$t_{k}=\beta^{\ell_{k}}$satisfies(4.12)

158
On the other hand, since$\{x^{k}\}$is contained in$S$$t_{k}\leq 1$, the convexity of$S$

ensures that the generated sequence. Therefore, by Theorem 3.1, the sequence$\{f(x^{k})\}$

is bounded frombelow. Also (4.8) implies$f(x^{k+1})\leq f(x^{k})-\alpha t_{k}||d^{k}||^{2}$,(4.13)and hence $\{f(x^{k})\}$ is monotonically decreasing. Thus it follows from (4.12) and (4.13) that$\lim||d^{k}||=0$$karrow\infty$

By the compactness of $S,$
$H(x^{k})-x^{k}$$\{x^{k}\}$.

(4.14)

has at least one accumulation point. Moreover, since $d^{k}=$and since the mapping $H$ is continuous, (4.14) implies that any such accumulation

point satisfies $H(x)=x$ . Thus it follows from Proposition 3.1 that any accumulation pointof$\{x^{k}\}$solves the variational inequality problem (1.1). Since the strong monotonicity of $F$

guarantees that the solution of (1.1) is unique, we can conclude that the entire sequence

converges to the solution of (1.1).

$\square$$\{x^{k}\}$.

In Theorems 4.1 and 4.2, we have as sumed the compactness of the set$S$in order to avoid

such anomalies as nonexistence of a solution and divergence of a generated sequence. This

assumption may appear so restrictive that the method cannot be applied to a wide range ofproblems including the nonlinear complementarity problem (1.2) and the system of nonlinear
equations (1.3). From a practical viewpoint, however, this difficulty is not very serious.
In fact, it may rather be helpful to introduce artificial bounds on the variables, which aresupposed to contain a desired solution and prevent the method from generating meaninglesspoints during the iterations.

The iterative methods considered above have a close relationship with the projection
method which is currently one of the most popular methods for variational inequality problems [2,3,15]. In fact, using our notation, the projection method may be stated as$x^{k+1}=Proj_{S,G}(x^{k}-\rho G^{-1}F(x^{k}))$

where

$G$

is symmetric and positive definite and$\rho$,(4.15)

is a positive parameter fixed throughout

the iteration. It is known [2] that if the mapping is strongly monotone and the parameter is$\rho$

chosen to be smaller than a certain threshold value which depends on the modulus of strong12monotonicity of $F$ , then the iteration (4.15) converges to the unique solution of problem(1.1). Note however that the projection method does not resort to minimization of any merit

function and hence it is not a descent method.

Concluding remarks

5

The variational inequality problems contain as special cases the nonlinear equations andnonlinear complementarity problems. In the case of nonlinear equations (1.3), the mapping$H$

is simply written as$H(x)=x-G^{-1}F(x)$ .

Hence problem (3.4) reduces to the problem of minimizing$f(x)= \frac{1}{2}\{F(x), G^{-1}F(x)\}$,which is to find the (weighted) least squares solution of the system of equations (1.3). There-

fore the approach presented in this paper may be regarded as a very natural extension of
the classical least squares methods for nonlinear equations $[4,14]$ . Moreover, in the case of

nonlinear equations, the iterative methods considered in the previous section take the form$x^{k+1}=x^{k}-t_{k}G^{-1}F(x^{k})$

.

(5.1)

Note that the iterative methods that use the same search directions as (5.1) but different

steplength criteria have recently been studied in $[6,9]$ for systems of nonlinear equations.
Since the evaluation of $f(x)$ for problem (1.1) involves minimization of a convex quadratic

function over$S$

, the practicality of the optimization approach based on problem (3.4) isdependent on the tractability of the set$S$. In the case of the nonlinear complementarity

problem (1.2), the particular choice $G=I$ yields$H(x)=[x-F(x)]_{+}$ ,where, for any vector $z\in R^{n},$$1,2,$$\ldots,$$n$$[z]_{+}$

denotes the vector with components $\max(O, z_{i}),$ $i=$

. Hence the optimization problem (3.4) can be written as

minimize$\frac{1}{2}\{||F(x)||^{2}-||x-F(x)-[x-F(x)]_{+}||^{2}\}$13

subject to$x\geq 0$

(5.2)

160
(cf. (3.5).) Since the objective function of problem (5.2) can readily be evaluated from $F(x)$ ,descent methods such as those studied in the previous section may effectively be applied tosolve (5.2). Therefore we may expect that the present approach offers a new insight into thesolution of nonlinear complementarity problems as well.

Acknowledgement

I am grateful to Professors T. Ibaraki and T. Hasegawa of Kyoto

University for their helpful comments and support.

References[1] A. Auslender, optimisation: M\’ethodes Num\’eriques (Masson, Paris, 1976).

[2] S. Dafermos, “Traffic equilibrium and variational inequalities”, Transportation Scie nce

14 (1980) 42-54.
[3] S. Dafermos, “An iterative scheme for variational inequalities“, Mathematical Program-ming 26 (1983) 40-47.
[4] J.E. Dennis, Jr. and R.B. Schnabel, Numerical Methods for Unconstrained optimization

and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, N.J., 1983).
[5] M. Florian, “Mathematical programming applications in national, regional and urban

planning”, in: M. Iri and K. Tanabe, Eds., Mathematical Programming: Recent Developments and Applications (KTK Scientific Publishers, Tokyo, 1989) 57-81.
[6] J.H. Hammond and T.L. Magnanti, “Generalized descent methods for asymmetric sys-

tems of equations”, Mathematics of Operations Research 12 (1987) 678-699.
[7] P.T. Harker and J.S. Pang, “Finite-dimensional variational inequality and nonlinear com-plementarity problems: A survey of theory, algorithms and applications”, Working paper
87-12-06, Department of Decision Sciences, University of Pennsylvania, (Philadelphia,
PA, 1987).

14

161
[8] D.W. Hearn, “The gap function of a convex program”, Operations ReSearch Letters 1(1982) 67-71.
[9] T. Itoh, M. Fukushima and T. Ibaraki, “An iterative method for variational inequalities

with application to traffic equilibrium problems”, Journal of the Opemtions ResearchSociety of Japan 31 (1988) 82-103.
[10] D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities andTheir Applications (Academic Press, New York, 1980).
[11] P. Marcotte, “A new algorithm for solving variational inequalities with application to

the traffic assignment problem”, Mathematical Progmmming 33 (1985) 339-351.
[12] P. Marcotte and J.P. Dussault, “A note on a globally convergent Newton method forsolving monotone variational inequalities”, Operations Research Letters 6 (1987) 35-42.
[13] A. Nagurney, “Competitive equilibrium problems, variational inequalities and regional

science”, Journal of Regional Science 27 (1987) 503-517.
[14] J.M. Ortega and W.C. Rheinboldt, Itemtive Solution of Nonlinear Equations in Several

Variables (Academic Press, New York, 1970).
[15] J.S. Pang and D. Chan, “Iterative methods for variational and complementarity prob-lems“, Mathematical Progmmming 24 (1982) 284-313.
[16] W.I. Zangwill, Nonlinear Programming: A Unified Approach (Prentice-Hall, Englewood

Cliffs, N.J., 1969).

15