A resolvent method for solving mixed variational inequalities

Abdellah Bnouhachem; Muhammad Aslam Noor; Mohamed Khalfaoui; Sheng Zhaohan

doi:10.1016/j.jksus.2010.07.015

View/Download PDF

Buy Reprints

PDF

Translate this page into:

ORIGINAL ARTICLE

23 (

); 235-240

doi:

10.1016/j.jksus.2010.07.015

A resolvent method for solving mixed variational inequalities

Abdellah Bnouhachem^a,b, Muhammad Aslam Noor^c,d,⁎, Mohamed Khalfaoui^e, Sheng Zhaohan^a

a School of Management Science and Engineering, Nanjing University, Nanjing 210093, PR China

b Ibn Zohr University, ENSA, BP 32/S, Agadir, Morocco

c Mathematics Department, COMSATS Institute of Information Technology, Islamabad, Pakistan

d Mathematics Department, College of Science, King Saud University, Riyadh, Saudi Arabia

e Ibn Zohr University, Présidence, BP 32/S, Agadir, Morocco

⁎Corresponding author at: Mathematics Department, COMSATS Institute of Information Technology, Islamabad, Pakistan. Tel.: +92 23454027532. noormaslam@hotmail.com (Muhammad Aslam Noor)

Received: 2010-6-30, Accepted: 2010-7-11, Published: 2010-04-01

Disclaimer:
This article was originally published by Elsevier and was migrated to Scientific Scholar after the change of Publisher.

Available online 16 July 2010

Peer-review under responsibility of King Saud University.

Abstract

It is well known that the mixed variational inequalities involving the nonlinear term are equivalent to the fixed-point problems. In this paper, we use this alternative equivalent formulation to suggest and analyze a new resolvent-type method for solving mixed variational inequalities. Our results can be viewed as significant extensions of the previously known results for mixed variational inequalities. An example is given to illustrate the efficiency and implementation of the proposed method.

Keywords

Mixed variational inequalities

Self-adaptive rules

Pseudomonotone

Resolvent operator

Show Related Articles from PubMed

1 Introduction

Variational inequalities introduced in the early sixties have played a fundamental and significant part in the study of several unrelated problems arising in finance, economics, network analysis, transportation, elasticity and optimization (see Baiocchi and Capelo, 1984; Bnouhachem, 2005; Bnouhachem et al., 2006; Brezis, 1973; Fukushima, 1992; Fu, 2008; Giannessi et al., 2001; Glowinski et al., 1981; Han and Lo, 2002; He and Liao, 2002; He et al., 2004; Kinderlehrer and Stampacchia, 2000; Lions and Stampacchia, 1967; Noor, 1997, 1998, 2000, 2002, 2003a,b, 2004a,b; Noor and Bnouhachem, 2005; Peng and Fukushima, 1999; Solodov and Svaiter, 2000; Stampacchia, 1964; Yang and Bell, 1997 ) and the references therein. In recent years variational inequalities have been extended in various directions using novel and innovative techniques. A useful and important generation of variational inequalities is the mixed variational inequality containing a nonlinear term. Due to the presence of the nonlinear bifunction, the projection method and its variant forms including the Wiener–Hopf equations technique can not be extended to suggest iterative methods for solving mixed variational inequalities. To overcome these drawbacks, some iterative methods have been suggested for a special cases of the mixed variational inequalities. For example, if the nonlinear term is a proper, convex and lower-semicontinuous function, then one can show that the mixed variational inequalities are equivalent to the fixed point and the resolvent equations. This alternative formulation has played a significant part in the developing various resolvent-type methods for solving mixed variational inequalities. This equivalent formulation has been used to suggest and analyze some iterative methods, the convergence of these methods requires that the operator is both strongly monotone and Lipschitz continuous. Secondly, it is very difficult to evaluate the resolvent of the operator except for very simple cases. Noor (2004b) has used the technique of updating the solution to suggest and analyze some three-step iterative methods for solving some classes of variational inequalities and related optimization problems. It has been shown that three-step iterative methods (Bnouhachem et al., 2006; Fu, 2008) are more efficient than two-step and one-step iterative methods. Inspired and motivated by the research going in this direction. We suggest and analyze a new self-adaptive method for solving mixed variational inequalities by using the resolvent operator and a new step size. We prove the convergence of the proposed method under certain conditions. In numerical experiment, we take a special case of the proposed method and an example is given to illustrate the efficiency of the proposed method.

2 Preliminaries

Let H be a real Hilbert finite-dimensional space, whose inner product and norm are denoted by $〈 \cdot, \cdot 〉$ and $‖ \cdot ‖$ . Let $T : H \to H$ be nonlinear operators. Let $\partial φ$ denote the subdifferential of a proper, convex and lower-semicontinuous function $φ : H \to R \cup {+ \infty}$ . It is well known that the subdifferential $\partial φ$ is a maximal monotone operator. We consider the problem of finding $u^{*} \in H$ such that

(2.1)

〈 T (u^{*}), u - u^{*} 〉 + φ (u) - φ (u^{*}) ⩾ 0, \forall u \in H,

which is called the mixed variational inequality (see Noor, 2003b).

If K is a closed and convex set in H and $φ (u) = I_{K} (u)$ is the indicator function of K defined by $I_{K} (u) = \{\begin{matrix} 0, & if u \in K; \\ + \infty, & otherwise, \end{matrix}$ then the problem (2.1) is equivalent to finding $u^{*} \in K$ such that

(2.2)

〈 T (u^{*}), u - u^{*} 〉 ⩾ 0, \forall u \in K,

which is known as the classical variational inequality introduced and studied by Stampacchia (1964). For the applications, numerical methods and other aspects of the mixed variational inequalities (see Baiocchi and Capelo, 1984; Bnouhachem, 2005; Bnouhachem et al., 2006; Brezis, 1973; Fukushima, 1992; Fu, 2008; Giannessi et al., 2001; Glowinski et al., 1981; Han and Lo, 2002; He and Liao, 2002; He et al., 2004; Kinderlehrer and Stampacchia, 2000; Lions and Stampacchia, 1967; Noor, 1997, 1998, 2000, 2002, 2003a,b, 2004a,b; Noor and Bnouhachem, 2005; Peng and Fukushima, 1999; Solodov and Svaiter, 2000; Stampacchia, 1964; Yang and Bell, 1997 ) and the references therein.

Definition 2.1

(Brezis, 1973) For any maximal operator T, the resolvent operator associated with T, for any $ρ > 0$ , is defined as

(2.3)

J_{T} (u) = {(I + ρ T)}^{- 1} (u), \forall u \in H .

It is well known that the subdifferential

\partial φ (\cdot)

of a proper, convex and lower-semicontinuous function

φ (\cdot)

is a maximal monotone operator. Thus, we have

J_{φ} (u) = {(I + ρ \partial φ (\cdot))}^{- 1} (u), \forall u \in H .

We also have the following characterization of the resolvent operator

J_{φ}

, which plays the crucial part in the analysis of our results.

Lemma 2.1

[Brezis, 1973] For a given $w \in H$ and $ρ > 0$ , the inequality $〈 w - z, z - v 〉 + ρ φ (v) - ρ φ (z) ⩾ 0, \forall v \in H$ holds if and only if $z = J_{φ} (w)$ , where $J_{φ} = {(I + ρ \partial φ)}^{- 1}$ is the resolvent operator. It follows from Lemma 2.1 that

(2.4)

〈 w - J_{φ} (w), J_{φ} (w) - v 〉 + ρ φ (v) - ρ φ (J_{φ} (w)) ⩾ 0, \forall v, w \in H .

If $φ$ is the indicator function of a closed convex set $Ω$ in H, then the resolvent operator $J_{φ} (\cdot)$ reduces to the projection operator $P_{Ω} [\cdot]$ (see Noor, 1997). It is well known that $J_{φ}$ is nonexpansive i.e.,

(2.5)

‖ J_{φ} (u) - J_{φ} (v) ‖ ⩽ ‖ u - v ‖, \forall u, v \in H .

Lemma 2.2

[Noor, 1998] $u^{*} \in H$ is solution of the mixed variational inequality (2.1) if and only if $u^{*} \in H$ satisfies the relation:

(2.6)

u^{*} = J_{φ} [u^{*} - ρ T (u^{*})],

where

J_{φ} = {(I + ρ \partial φ)}^{- 1}

is the resolvent operator. From Lemma 2.2, it is clear that

u \in H

is solution of (2.1) if and only if u is a zero point of the residue vector

r (u, ρ) = u - J_{φ} [u - ρ T (u)] .

Throughout this paper, we make following assumptions.

Assumptions:

T is continuous and pseudomonotone operator on H, that is $〈 T (u) - T (v), u - v 〉 ⩾ 0, \forall u, v \in H .$
The solution set of problem (2.1), denoted by $S^{*}$ , is nonempty.

3 Basic results

In this section, we prove some basic properties, which will be used to establish the sufficient and necessary conditions for the convergence of the proposed method. The following lemmas summarize some basic inequalities with respect to the resolvent operator. We refer to (see, for example, Bnouhachem, 2005) for the complete proof.

Lemma 3.1

Lemma 3.1 Bnouhachem (2005)

For all $u \in H$ and $ρ^{'} ⩾ ρ > 0$ , it holds that

(3.1)

‖ r (u, ρ^{'}) ‖ ⩾ ‖ r (u, ρ) ‖

and

(3.2)

\frac{‖ r (u, ρ^{'}) ‖}{ρ^{'}} ⩽ \frac{‖ r (u, ρ) ‖}{ρ} .

Lemma 3.2

[Bnouhachem (2005)]If u is not a solution of problem (2.1), then there exist $δ \in (0, 1)$ and $∊^{'} > 0$ , such that for all $ρ \in (0, ∊^{'}]$ ,

(3.3)

ρ ‖ T (u) - T (J_{φ} [u - ρ T (u)]) ‖ ⩽ δ ‖ r (u, ρ) ‖ .

Lemma 3.3

$\forall u \in H, u^{*} \in S^{*}$ and $ρ > 0$ we have

(3.4)

〈 g (u) - g (u^{*}), d (u, ρ) 〉 ⩾ ϕ (u, ρ),

where

d (u, ρ) : = r (u, ρ) + ρ T (J_{φ} [u - ρ T (u)])

and

ϕ (u, ρ) : = ‖ r (u, ρ) ‖^{2} - ρ 〈 r (u, ρ), T (u) - T (J_{φ} [u - ρ T (u)]) 〉 .

Proof

For any $u^{*} \in S^{*}$ solution of problem (2.1), we have

(3.5)

〈 ρ T (u^{*}), v - u^{*} 〉 + ρ φ (v) - ρ φ (u^{*}) ⩾ 0, \forall v \in H, ρ > 0 .

Taking

v = J_{φ} [u - ρ T (u)]

in (3.5) and using the monotonicity of T, we obtain

(3.6)

〈 ρ T (J_{φ} [u - ρ T (u)]), J_{φ} [u - ρ T (u)] - u^{*} 〉 + ρ φ (J_{φ} [u - ρ T (u)]) - ρ φ (u^{*}) ⩾ 0 .

Substituting

w = u - ρ T (u)

and

v = u^{*}

into (2.4), and using the definition of

r (u, ρ)

, we get

(3.7)

〈 r (u, ρ) - ρ T (u), J_{φ} [u - ρ T (u)] - u^{*} 〉 + ρ φ (u^{*}) - ρ φ (J_{φ} [u - ρ T (u)]) ⩾ 0 .

Adding (3.6) and (3.7), we have

〈 r (u, ρ) - ρ [T (u) - T (J_{φ} [u - ρ T (u)])], J_{φ} [u - ρ T (u)] - u^{*} 〉 ⩾ 0,

which can be rewritten as

〈 r (u, ρ) - ρ [T (u) - T (J_{φ} [u - ρ T (u)])], u - u^{*} - r (u, ρ) 〉 ⩾ 0,

then

\begin{matrix} 〈 u - u^{*}, r (u, ρ) + ρ T (J_{φ} [u - ρ T (u)]) 〉 ⩾ ‖ r (u, ρ) ‖^{2} \\ - ρ 〈 r (u, ρ), T (u) - T (J_{φ} [u - ρ T (u)]) 〉 + 〈 u - u^{*}, ρ T (u) 〉 . \end{matrix}

Using the monotonicity of T, the last term in the right side of the above inequality is positive, we obtain

〈 u - u^{*}, d (u, ρ) 〉 ⩾ ‖ r (u, ρ) ‖^{2} - ρ 〈 r (u, ρ), T (u) - T (J_{φ} [u - ρ T (u)]) 〉,

and the conclusion of Lemma 3.3 is proved.

□

From Lemmas 3.2 and 3.3 we have

(3.8)

〈 u - u^{*}, d (u, ρ) 〉 ⩾ ϕ (u, ρ) ⩾ (1 - δ) ‖ r (u, ρ) ‖^{2} .

Taking the above inequality into consideration, we suggest and consider a new method for solving the mixed variational inequality (2.1).

Algorithm 3.1

For a given $u^{k} \in H$ , find the approximate solution by the following iterative schemes involving the two-steps.

Step 1.

(3.9)

{\tilde{u}}^{k} = J_{φ} [u^{k} - ρ_{k} T (u^{k})],

where

ρ_{k}

satisfies

(3.10)

‖ ρ_{k} (T (u^{k}) - T ({\tilde{u}}^{k})) ‖ ⩽ δ ‖ u^{k} - {\tilde{u}}^{k} ‖, 0 < δ < 1 .

Step 2. The new iterate $u^{k + 1}$ is defined by $u^{k + 1} = J_{φ} [u^{k} - α_{k} d (u^{k}, ρ_{k})],$ where

(3.11)

d (u^{k}, ρ_{k}) = u^{k} - {\tilde{u}}^{k} + ρ_{k} T ({\tilde{u}}^{k}),

(3.12)

ε^{k} = ρ_{k} (T ({\tilde{u}}^{k}) - T (u^{k})),

(3.13)

D (u^{k}, ρ_{k}) : = u^{k} - {\tilde{u}}^{k} + ε^{k},

(3.14)

ϕ (u^{k}, ρ_{k}) : = 〈 u^{k} - {\tilde{u}}^{k}, D (u^{k}, ρ_{k}) 〉,

and

(3.15)

α_{k} : = \frac{{‖\frac{D (u^{k}, ρ_{k})}{2} + u^{k} - {\tilde{u}}^{k}‖}^{2}}{‖ D (u^{k}, ρ_{k}) + u^{k} - {\tilde{u}}^{k} ‖^{2}} .

Remark 3.1

(3.10) implies that

(3.16)

| 〈 u^{k} - {\tilde{u}}^{k}, ε^{k} 〉 | ⩽ δ ‖ u^{k} - {\tilde{u}}^{k} ‖^{2}, 0 < δ < 1 .

For the convergence analysis of the proposed method, we need the following results.

Lemma 3.4

For given $u^{k} \in R^{n}$ and $ρ_{k} > 0$ , let ${\tilde{u}}^{k}$ and $ε^{k}$ satisfy (3.9) and (3.12), then

(3.17)

ϕ (u^{k}, ρ_{k}) ⩾ (1 - δ) ‖ u^{k} - {\tilde{u}}^{k} ‖^{2}

and

(3.18)

α_{k} ⩾ \frac{1}{2} .

Proof

It follows from (3.13) and (3.16) that $\begin{matrix} ϕ (u^{k}, ρ_{k}) : = 〈 u^{k} - {\tilde{u}}^{k}, D (u^{k}, ρ_{k}) 〉 \\ = ‖ u^{k} - {\tilde{u}}^{k} ‖^{2} + 〈 u^{k} - {\tilde{u}}^{k}, ε^{k} 〉 \\ ⩾ (1 - δ) ‖ u^{k} - {\tilde{u}}^{k} ‖^{2} . \end{matrix}$ Otherwise from (3.10), we have $\begin{matrix} 〈 u^{k} - {\tilde{u}}^{k}, D (u^{k}, ρ_{k}) 〉 = ‖ u^{k} - {\tilde{u}}^{k} ‖^{2} + 〈 u^{k} - {\tilde{u}}^{k}, ε^{k} 〉 \\ ⩾ \frac{1}{2} ‖ u^{k} - {\tilde{u}}^{k} ‖^{2} + 〈 u^{k} - {\tilde{u}}^{k}, ε^{k} 〉 + \frac{1}{2} ‖ ε^{k} ‖^{2} \\ = \frac{1}{2} ‖ D (u^{k}, ρ_{k}) ‖^{2} . \end{matrix}$ Using Cauchy–Schwartz inequality, we get $‖ u^{k} - {\tilde{u}}^{k} ‖ ⩾ \frac{1}{2} ‖ D (u^{k}, ρ_{k}) ‖ .$ From the above inequality, we obtain $\begin{matrix} {‖\frac{D (u^{k}, ρ_{k})}{2} + u^{k} - {\tilde{u}}^{k}‖}^{2} = \frac{‖ D (u^{k}, ρ_{k}) ‖^{2}}{4} + 〈u^{k} - {\tilde{u}}^{k}, D (u^{k}, ρ_{k})〉 \\ + ‖ u^{k} - {\tilde{u}}^{k} ‖^{2} \\ = \frac{1}{2} \{\frac{‖ D (u^{k}, ρ_{k}) ‖^{2}}{2} + 2 〈 u^{k} - {\tilde{u}}^{k}, D (u^{k}, ρ_{k}) 〉 \\ + ‖ u^{k} - {\tilde{u}}^{k} ‖^{2} + ‖ u^{k} - {\tilde{u}}^{k} ‖^{2}\} \\ ⩾ \frac{1}{2} \{\frac{‖ D (u^{k}, ρ_{k}) ‖^{2}}{2} + 2 〈 u^{k} - {\tilde{u}}^{k}, D (u^{k}, ρ_{k}) 〉 \\ + ‖ u^{k} - {\tilde{u}}^{k} ‖^{2} + \frac{‖ D (u^{k}, ρ_{k}) ‖^{2}}{2}\} \\ = \frac{1}{2} ‖ D (u^{k}, ρ_{k}) + u^{k} - {\tilde{u}}^{k} ‖^{2}, \end{matrix}$ which implies that $α_{k} ⩾ \frac{1}{2},$ we obtain the required result. $□$

4 Convergence analysis

In this section, we begin to investigate convergence of the proposed method.

Theorem 4.1

Let $u^{*}$ be a solution of problem (2.1) and let $u^{k + 1}$ be the sequence obtained from Algorithm 3.1. Then $u^{k}$ is bounded and $‖ u^{k + 1} - u^{*} ‖^{2} ⩽ ‖ u^{k} - u^{*} ‖^{2} - \frac{γ (1 - δ)}{2} ‖ r (u^{k}, ρ_{k}) ‖^{2} .$

Proof

Let $u^{*}$ be a solution of problem (2.1). Then, from (3.11), we have

(4.1)

\begin{matrix} ‖ u^{k + 1} - u^{*} ‖^{2} ⩽ ‖ u^{k} - u^{*} - γ α_{k} d (u^{k}, ρ_{k}) ‖^{2} \\ = ‖ u^{k} - u^{*} ‖^{2} - 2 γ α_{k} 〈u^{k} - u^{*}, d (u^{k}, ρ_{k})〉 \end{matrix}

(4.2)

+ γ^{2} α_{k}^{2} ‖ d (u^{k}, ρ_{k}) ‖^{2},

where the inequality follows from the nonexpansive of the resolvent operator. Let

Φ (α_{k}) = 2 γ α_{k} 〈u^{k} - u^{*}, d (u^{k}, ρ_{k})〉 - γ^{2} α_{k}^{2} ‖ d (u^{k}, ρ_{k}) ‖^{2} .

Note that

Φ (α)

is a quadratic function of

α

and it reaches its maximum at

α_{k}^{*} = \frac{〈u^{k} - u^{*}, d (u^{k}, ρ_{k})〉}{γ ‖ d (u^{k}, ρ_{k}) ‖^{2}}

and

Φ (α_{k}^{*}) = γ α_{k}^{*} 〈 u^{k} - u^{*}, d (u^{k}, ρ_{k}) 〉 .

From (3.8) and (4.2), we obtain

\begin{matrix} ‖ u^{k + 1} - u^{*} ‖^{2} & ⩽ ‖ u^{k} - u^{*} ‖^{2} - Φ (α_{k}^{*}) \\ ⩽ ‖ u^{k} - u^{*} ‖^{2} - γ α_{k}^{*} (1 - δ) ‖ r (u^{k}, ρ_{k}) ‖^{2} \\ ⩽ ‖ u^{k} - u^{*} ‖^{2} - \frac{γ (1 - δ)}{2} ‖ r (u^{k}, ρ_{k}) ‖^{2}, \end{matrix}

where the last inequality follows from (3.18). Since

γ > 0

and

δ \in (0, 1)

we have

‖ u^{k + 1} - u^{*} ‖ ⩽ ‖ u^{k} - u^{*} ‖ ⩽ \dots ⩽ ‖ u^{0} - u^{*} ‖ .

This shows that the sequence

u^{k}

is bounded.

□

The following result can be proved by similar arguments as in Bnouhachem et al. (2006). Hence the proof is omitted.

Theorem 4.2

The sequence ${u^{k}}$ generated by the proposed method converges to a solution point of problem (2.1).

We now describe the new algorithm as follows.

Algorithm 4.1

Step 0. Let $ρ_{0} = 1, δ : = 0.95 < 1, γ = 1.95, ∊ > 0, k = 0$ and $u^{0} \in H$ .
Step 1. If $‖ | r (u^{k}, ρ_{k}) ‖_{\infty} ⩽ ∊$ , then stop. Otherwise, go to Step 2.
Step 2.
${\tilde{u}}^{k} = J_{φ} [u^{k} - ρ_{k} T (u^{k})]$ , $ε^{k} = ρ_{k} (T ({\tilde{u}}^{k}) - T (u^{k}))$ ,
$r = \frac{‖ ε^{k} ‖}{‖ u^{k} - {\tilde{u}}^{k} ‖}$ .
While $(r > δ)$
$ρ_{k} = \frac{0.8}{r} * ρ_{k}$ , ${\tilde{u}}^{k} = J_{φ} [u^{k} - ρ_{k} T (u^{k})]$ ,
$ε^{k} = ρ_{k} (T ({\tilde{u}}^{k}) - T (u^{k}))$ , $r = \frac{‖ ε^{k} ‖}{‖ u^{k} - {\tilde{u}}^{k} ‖}$ .
end While
Step 3. Set
$D (u^{k}, ρ_{k}) : = u^{k} - {\tilde{u}}^{k} + ε^{k}$ ,
$d (u^{k}, ρ_{k}) = u^{k} - {\tilde{u}}^{k} + ρ_{k} T ({\tilde{u}}^{k})$ ,
$α_{k} : = \frac{{‖\frac{D (u^{k}, ρ_{k})}{2} + u^{k} - {\tilde{u}}^{k}‖}^{2}}{‖ D (u^{k}, ρ_{k}) + u^{k} - {\tilde{u}}^{k} ‖^{2}}$ ,
$u^{k + 1} = J_{φ} [u^{k} - γ α_{k} d (u^{k}, ρ_{k})]$ ,
Step 4. $ρ_{k + 1} = \{\begin{matrix} \frac{ρ_{k} * 0.7}{r} & if r ⩽ 0.5; \\ ρ_{k} & otherwise. \end{matrix}$
Step 5. k := k + 1; go to Step 1.

5 Computational results

In this section, we apply the new method to a traffic equilibrium problem, which is a classical and important problem in transportation science (see, for example, He et al., 2004; Yang and Bell, 1997). The numerical results show that the new method is attractive in practice.

Consider a network $[N, L]$ of nodes N and directed links L, which consists of a finite sequence of connecting links with a certain orientation. Let $a, b$ , etc., denote the links; $p, q$ , etc., denote the paths; $ω$ denote an origin/destination (O/D) pair of nodes of the network; $P_{ω}$ denotes the set of all paths connecting O/D pair $ω$ ; $u_{p}$ represent the traffic flow on path p; $d_{ω}$ denote the traffic demand between O/D pair $ω$ , which must satisfy $d_{ω} = \sum_{p \in P_{ω}} u_{p},$ where $u_{p} ⩾ 0, \forall p$ ; and $f_{a}$ denote the link load on link a, which must satisfy the following conservation of flow equation $f_{a} = \sum_{p \in P} δ_{ap} u_{p},$ where $δ_{ap} = \{\begin{matrix} 1, & if a is contained in path p; \\ 0, & otherwise. \end{matrix}$

Let A be the path-arc incidence matrix of the given problem and $f = {f_{a}, a \in L}$ be the vector of the link load. Since u is the path-flow, f is given by $f = A^{T} u .$

In addition, let $t = {t_{a}, a \in L}$ be the row vector of link costs, with $t_{a}$ denoting the user cost of traveling link a which is given by

(5.1)

t_{a} (f_{a}) = t_{a}^{0} [1 + 0.15 {(\frac{f_{a}}{C_{a}})}^{4}],

where

t_{a}^{0}

is the free-flow travel cost on link a and

C_{a}

is designed capacity of link a. Then t is a mapping of the path-flow u and its mathematical form is

t (u) : = t (f) = t (A^{T} u) .

Note that the travel cost on the path p denoted by $θ_{p}$ is $θ_{p} = \sum_{a \in L} δ_{ap} t_{a} (f_{a}) .$

Let P denote the set of all the paths concerned. Let $θ = {θ_{p}, p \in P}$ be the vector of (path) travel cost. For given link travel cost vector t, $θ$ is a mapping of the path-flow u, which is given by $θ (u) = At (u) = At (A^{T} u) .$

Associated with every O/D pair $ω$ , there is a travel disutility $λ_{ω} (d)$ , which is defined as following:

(5.2)

λ_{ω} (d) = - m_{ω} \log (d_{ω}) + q_{ω} .

Note that both the path costs and the travel disutilities are functions of the flow pattern u. The traffic network equilibrium problem is to seek the path-flow pattern $u^{*}$ , which induces a demand pattern $d^{*} = d (u^{*})$ , for every O/D pair $ω$ and each path $p \in P_{ω}$ , $T (u) \equiv T_{p} (u) = θ_{p} (u) - λ_{ω} (d (u)) .$

The problem can be reduced to a variational inequality in the space of path-flow pattern $u \in R_{+}^{n}$ such that

(5.3)

〈 u - u^{*}, T (u^{*}) 〉 ⩾ 0, \forall u \in R_{+}^{n},

which is a special case of the mixed variational inequality (2.1), by taking

φ (u) = \{\begin{matrix} 0, & if u \in R_{+}^{n}; \\ + \infty, & otherwise. \end{matrix}

For the comparison sake, we consider the same example studied in He et al. (2004) and Yang and Bell (1997). The network is depicted in Fig. 1. The free-flow travel cost and the designed capacity of links (5.1) are given in Table 1, the O/D pairs and the coefficient m and q in the disutility function (5.2) are given in Table 2. For this example, there are together 12 paths for the 4 given O/D pairs listed in Table 4.

The network used for the numerical test.

Table 1 The free-flow cost and the designed capacity of links in (5.1).

Link	Free-flow travel time $t_{a}^{0}$	Capacity $C_{a}$	Link	Free-flow travel time $t_{a}^{0}$	Capacity $C_{a}$
1	6	200	7	5	150
2	5	200	8	10	150
3	6	200	9	11	200
4	16	200	10	11	200
5	6	100	11	15	200
6	1	100	–	–	–

Table 2 The O/D pairs and the coefficient m and q in (5.2).

No. of the pair	O/D pair	$m_{ω}$	$q_{ω}$
1	(1, 7)	25	25log 600
2	(2, 7)	33	33log 500
3	(3, 7)	20	20log 500
4	(6, 7)	20	20log 400

In all tests we take $δ = 0.95$ and $γ = 1.95$ . All iterations start with $u^{0} = {(1, \dots, 1)}^{T}$ and $ρ_{0} = 1$ , and stopped whenever $‖ r (u, ρ) ‖_{\infty} ⩽ ε$ . All codes are written in Matlab and run on a P4-2.00G note book computer. The test results of Algorithm 4.1 and the method in Bnouhachem et al. (2006) for different $ε$ are reported in Table 3. k is the number of iterations and l denotes the number of evaluations of mapping T. For the case $ε = 10^{- 8}$ , the optimal path-flow and link flow are given in Tables 4 and 5, respectively. The numerical experiments show that the new method is more flexible and efficient to solve the traffic equilibrium problem.

Table 3 Numerical results for different

ε

Different ε	Algorithm 4.1			The method in Bnouhachem et al. (2006)
Different ε	k	l	CPU (Sec.)	k	l	CPU (Sec.)
$10^{- 4}$	31	71	0.031	85	185	0.04
$10^{- 5}$	35	79	0.047	103	221	0.06
$10^{- 6}$	42	96	0.51	120	255	0.07
$10^{- 7}$	48	109	0.6	138	291	0.08
$10^{- 8}$	54	122	0.72	155	325	0.09

Table 4 The optimal path-flow.

O/D pair	Path No.	Link of path	Optimal path-flow
O/D pair (1, 7)	1	(1, 3)	165.3145
	2	(2, 4)	0
	3	(11)	138.5735
	4	(5, 1, 3)	82.5281
	5	(5, 2, 4)	0
O/D pair (2, 7)	6	(5, 11)	55.7871
	7	(8, 6, 4)	0
	8	(8, 9)	87.0260
O/D pair (3, 7)	9	(7, 3)	19.7549
O/D pair (3, 7)	10	(10)	229.9747
O/D pair (6, 7)	11	(9)	178.5600
O/D pair (6, 7)	12	(6, 4)	0

Table 5 The optimal link flow.

Link No.	Link flow	Link No.	Link flow	Link No.	Link flow	Link No.	Link flow
1	247.8426	4	0	7	19.7549	10	229.9747
2	0	5	138.3152	8	87.0260	11	194.3606
3	267.5974	6	0	9	265.5860	–	–

Acknowledgements

This research was supported partly by NSFC Grants Nos. 70731002 and 70571034, “The Second Term ‘985’ Engineering-Innovation Center for Computational Laboratory of Evolutionary Economic Theory and its Applications” and “Study on the Evolution of Complex Economic System” at “Innovation Center of Economic Transition and Development of Nanjing University” of Ministry of Education, China.

References

Baiocchi C., Capelo A., . Variational and Quasi Variational Inequalities. New York: J. Wiley and Sons; 1984.
Bnouhachem A., . A self-adaptive method for solving general mixed variational inequalities. J. Math. Anal. Appl.. 2005;309:136-150.
[Google Scholar]
Bnouhachem A., Noor M.A., Rassias Th.R., . Three-steps iterative algorithms for mixed variational inequalities. Appl. Math. Comput.. 2006;183:436-446.
[Google Scholar]
Brezis H., . Operateurs Maximaux Monotone et Semigroupes de Contractions dans les Espace d’Hilbert. Amsterdam, Holland: North-Holland; 1973.
Fu X., . A two-stage prediction–correction method for solving variational inequalities. J. Comput. Appl. Math.. 2008;214:345-355.
[Google Scholar]
Fukushima M., . Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Program.. 1992;53:99-110.
[Google Scholar]
Giannessi F., Maugeri A., Pardalos P.M., . Equilibrium Problems: Nonsmooth Optimization and Variational Inequality Models. Dordrecht, Holland: Kluwer, Academic Press; 2001.
Glowinski R., Lions J.L., Tremoliers R., . Numerical Analysis of Variational Inequalities. Amsterdam, Holland: North-Holland; 1981.
Han D., Lo H.K., . Two new self-adaptive projection methods for variational inequality problems. Comput. Math. Appl.. 2002;43:1529-1537.
[Google Scholar]
He B.S., Liao L.Z., . Improvement of some projection methods for monotone variational inequalities. J. Optim. Theory Appl.. 2002;112:111-128.
[Google Scholar]
He B.S., Yang Z.H., Yuan X.M., . An approximate proximal-extragradient type method for monotone variational inequalities. J. Math. Anal. Appl.. 2004;300(2):362-374.
[Google Scholar]
Kinderlehrer D., Stampacchia G., . An Introduction to Variational Inequalities and their Applications. Philadelphia: SIAM; 2000.
Lions J.L., Stampacchia G., . Variational inequalities. Commun. Pure Appl. Math.. 1967;20:493-512.
[Google Scholar]
Noor M. Aslam, . A new iterative method for monotone mixed variational inequalities. Math. Comput. Model.. 1997;26(7):29-34.
[Google Scholar]
Noor M. Aslam, . An implicit method for mixed variational inequalities. Appl. Math. Lett.. 1998;11:109-113.
[Google Scholar]
Noor M. Aslam, . A class of new iterative methods for general mixed variational inequalities. Math. Comput. Model.. 2000;31:11-19.
[Google Scholar]
Noor M. Aslam, . Proximal methods for mixed quasi variational inequalities. J. Optim. Theory Appl.. 2002;115:447-451.
[Google Scholar]
Noor M. Aslam, . Pseudomonotone general mixed variational inequalities. Appl. Math. Comput.. 2003;141:529-540.
[Google Scholar]
Noor M. Aslam, . Mixed quasi variational inequalities. Appl. Math. Comput.. 2003;146:553-578.
[Google Scholar]
Noor M. Aslam, . Fundamentals of mixed quasi variational inequalities. Int. J. Pure Appl. Math.. 2004;15:137-258.
[Google Scholar]
Noor M. Aslam, . Some developments in general variational inequalities. Appl. Math. Comput.. 2004;152:199-277.
[Google Scholar]
Noor M. Aslam, Bnouhachem A., . Self-adaptive methods for mixed quasi variational inequalities. J. Math. Anal. Appl.. 2005;312:514-526.
[Google Scholar]
Peng J.M., Fukushima M., . A hybrid Newton method for solving the variational inequality problem via the D-gap function. Math. Program.. 1999;86:367-386.
[Google Scholar]
Solodov M.V., Svaiter B.F., . Error bounds for proximal point subproblems and associated inexact proximal point algorithms. Math. Program. Ser. B. 2000;88:371-389.
[Google Scholar]
Stampacchia G., . Formes bilineaires coercivites sur les ensembles convexes. C. R. Acad. Sci. Paris. 1964;258:4413-4416.
[Google Scholar]
Yang H., Bell M.G.H., . Traffic restraint, road pricing and network equilibrium. Transp. Res. B. 1997;31:303-314.
[Google Scholar]

Introduction

Preliminaries

Basic results

Convergence analysis

Computational results

Fulltext Views
20

PDF downloads
11

View/Download PDF
Download Citations

BibTeX
RIS

Show Sections

[1] Baiocchi C., Capelo A., . Variational and Quasi Variational Inequalities. New York: J. Wiley and Sons; 1984.

[2] Bnouhachem A., . A self-adaptive method for solving general mixed variational inequalities. J. Math. Anal. Appl.. 2005;309:136-150.
[Google Scholar]

[3] Bnouhachem A., Noor M.A., Rassias Th.R., . Three-steps iterative algorithms for mixed variational inequalities. Appl. Math. Comput.. 2006;183:436-446.
[Google Scholar]

[4] Brezis H., . Operateurs Maximaux Monotone et Semigroupes de Contractions dans les Espace d’Hilbert. Amsterdam, Holland: North-Holland; 1973.

[5] Fu X., . A two-stage prediction–correction method for solving variational inequalities. J. Comput. Appl. Math.. 2008;214:345-355.
[Google Scholar]

[6] Fukushima M., . Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Program.. 1992;53:99-110.
[Google Scholar]

[7] Giannessi F., Maugeri A., Pardalos P.M., . Equilibrium Problems: Nonsmooth Optimization and Variational Inequality Models. Dordrecht, Holland: Kluwer, Academic Press; 2001.

[8] Glowinski R., Lions J.L., Tremoliers R., . Numerical Analysis of Variational Inequalities. Amsterdam, Holland: North-Holland; 1981.

[9] Han D., Lo H.K., . Two new self-adaptive projection methods for variational inequality problems. Comput. Math. Appl.. 2002;43:1529-1537.
[Google Scholar]

[10] He B.S., Liao L.Z., . Improvement of some projection methods for monotone variational inequalities. J. Optim. Theory Appl.. 2002;112:111-128.
[Google Scholar]

[11] He B.S., Yang Z.H., Yuan X.M., . An approximate proximal-extragradient type method for monotone variational inequalities. J. Math. Anal. Appl.. 2004;300(2):362-374.
[Google Scholar]

[12] Kinderlehrer D., Stampacchia G., . An Introduction to Variational Inequalities and their Applications. Philadelphia: SIAM; 2000.

[13] Lions J.L., Stampacchia G., . Variational inequalities. Commun. Pure Appl. Math.. 1967;20:493-512.
[Google Scholar]

[14] Noor M. Aslam, . A new iterative method for monotone mixed variational inequalities. Math. Comput. Model.. 1997;26(7):29-34.
[Google Scholar]

[15] Noor M. Aslam, . An implicit method for mixed variational inequalities. Appl. Math. Lett.. 1998;11:109-113.
[Google Scholar]

[16] Noor M. Aslam, . A class of new iterative methods for general mixed variational inequalities. Math. Comput. Model.. 2000;31:11-19.
[Google Scholar]

[17] Noor M. Aslam, . Proximal methods for mixed quasi variational inequalities. J. Optim. Theory Appl.. 2002;115:447-451.
[Google Scholar]

[18] Noor M. Aslam, . Pseudomonotone general mixed variational inequalities. Appl. Math. Comput.. 2003;141:529-540.
[Google Scholar]

[19] Noor M. Aslam, . Mixed quasi variational inequalities. Appl. Math. Comput.. 2003;146:553-578.
[Google Scholar]

[20] Noor M. Aslam, . Fundamentals of mixed quasi variational inequalities. Int. J. Pure Appl. Math.. 2004;15:137-258.
[Google Scholar]

[21] Noor M. Aslam, . Some developments in general variational inequalities. Appl. Math. Comput.. 2004;152:199-277.
[Google Scholar]

[22] Noor M. Aslam, Bnouhachem A., . Self-adaptive methods for mixed quasi variational inequalities. J. Math. Anal. Appl.. 2005;312:514-526.
[Google Scholar]

[23] Peng J.M., Fukushima M., . A hybrid Newton method for solving the variational inequality problem via the D-gap function. Math. Program.. 1999;86:367-386.
[Google Scholar]

[24] Solodov M.V., Svaiter B.F., . Error bounds for proximal point subproblems and associated inexact proximal point algorithms. Math. Program. Ser. B. 2000;88:371-389.
[Google Scholar]

[25] Stampacchia G., . Formes bilineaires coercivites sur les ensembles convexes. C. R. Acad. Sci. Paris. 1964;258:4413-4416.
[Google Scholar]

[26] Yang H., Bell M.G.H., . Traffic restraint, road pricing and network equilibrium. Transp. Res. B. 1997;31:303-314.
[Google Scholar]