A Finsler Geometrical Programming for the Nonlinear Complementarity Problem of Traffic Equilibrium

Let $M=I\!\!R^{n}$ be the real n-dimensional space. The set of all tangent vectors at the point $x\in M$ is called the tangent space of $M$ and denoted by $T_{x}M$. The set of all tangent spaces at $x\in M$ is called the tangent bundle of $M$ and denoted by $TM$, i.e. $\displaystyle TM:=\bigcup_{x\in M}T_{x}M$. Each element of $TM$ has the form $(x,y)$ consisting of the point $x\in M$ and the tangent vector $y\in T_{x}M$ at the point $x$. Let the natural projection $\pi:TM\rightarrow M$ be defined as $\pi(x,y):=x$. The pair $(M,\overline{F})$ is said to be a Finsler space where $\overline{F}:TM\rightarrow[0,\infty)$ is a function with the following properties:

1. 1.

   $\overline{F}(x,y)$ is differentiable on $TM\backslash\{0\}$.

2. 2.

   $\overline{F}$ is positively homogeneous of degree one in $y$, i.e. $\overline{F}(x,\lambda y)=\lambda\overline{F}(x,y),\forall\lambda>0$.

3. 3.

   The Hessian matrix of $\overline{F}^{2}$,

   $$g=(g_{ij}):=\left({1\over 2}\left[\frac{\partial^{2}}{\partial y^{i}\partial y^{j}}\overline{F}^{2}\right]\right),$$

   (1)

   is positive-definite on $TM\backslash\{0\}$ where $i,j\in 1,\cdots,n$.

The function $\overline{F}$ is called a Finsler structure and $g$ is called its associated Finsler metric on manifold $M$. Here, we use the notation $\overline{F}$ for the Finsler structure, rather than the usual notation $F$, to avoid any confusion with the function $F$ in the nonlinear complementarity problem.

We can define a norm function on the vector space $T_{x}M$ based on any Finsler metric $g$ on $M$. Let $\{U,(x^{i})\}$ or simply $(x^{1},...,x^{n})=(x^{i}):U\rightarrow I\!\!R^{n}$ be a local coordinate system on an open subset $U\subset M$ around the point $x\in M$. The coordinate system $\{U,(x^{i})\}$ induces a coordinate basis $\frac{\partial}{\partial x^{i}}$ on $T_{x}M$. Hence, we can write each tangent vector in the form $y=y^{i}\frac{\partial}{\partial x^{i}}\,$, where we apply the Einstein summation convention or Einstein notation, that is, whenever an index variable appears twice in a single term, once in an upper (superscript) and once in a lower (subscript) position, it implies that we are summing over all of its possible values.

Let $x$ be a point of $M$ with the local coordinate system $(x^{i})$, then it generates a local coordinate system $(x^{i},y^{i})$ on $TM$. The pair $(x^{i},y^{i})$ consisting of the position $x\in M$ and the direction $y\in T_{x}M$, is known as the line element of $(M,\overline{F})$. The Finsler structure $\overline{F}(x,y)$ is said to be Riemannian if it is independent of the direction $y$ and by homogeneity of $\overline{F}$ it is equivalent to say that $\displaystyle\frac{\partial\overline{F}}{\partial y^{i}}=0$ for $i\in 1,\cdots,n$. The Finsler structure $\overline{F}(x,y)$ is said to be Euclidean if $g_{ij}(x,y)=\delta_{ij}$, where $g_{ij}$ is defined by (1) and $\delta_{ij}$ is the Kronecker delta.

We denote by $\Gamma(p,q)$ the collection of all piecewise $C^{\infty}$ curves $\sigma:[a,b]\subset I\!\!R\longrightarrow M$ on $(M,\overline{F})$ with $\sigma(a)=p$ and $\sigma(b)=q$. Then the length of $\sigma$ is defined by

$$J(\sigma):=\int_{a}^{b}\overline{F}(\sigma,\frac{d\sigma}{dt})dt,$$

where $\frac{d\sigma}{dt}=\frac{d\sigma^{i}}{dt}\frac{\partial}{\partial x^{i}}\in T_{\sigma(t)}M$. Define the map

$$\begin{array}[]{clc}d:M\times M\longrightarrow[0,\infty)\\ d(p,q):=\inf_{\Gamma(p,q)}J(\sigma).\end{array}$$

It can be shown that $(M,d)$ satisfies the axioms of a metric space, expect the symmetry property, see [2] and [28]. In the original sense, a geodesic is a generalization of the notion of a "straight line" in a Euclidean space. However, when the metric is not Euclidean, geodesics are not necessarily straight lines and define as follows. A piecewise $C^{\infty}$ curve $\sigma:[a,b]\longrightarrow M$ with $\sigma(a)=p$ and $\sigma(b)=q$ on the space $M$ with the Finsler structure $\overline{F}$ is said to be a geodesic if it is a minimal curve in $\Gamma(p,q)$, with a constant velocity, i.e. $J(\sigma)=d(p,q)$. Hence, geodesics are defined to be (locally) the shortest path between points in the space.

For any Finsler metric $g$ on $M$, we can define an inner product $g(.,.):=<.,.>_{g}$ on the tangent space $T_{x}M$ (here, for $M=I\!\!R^{n}$ we have , $T_{x}M\cong I\!\!R^{n}$). In the local coordinate system $\{U,(x^{i})\}$, for all $y,z\in T_{x}M$ we have $g(y,z)=g_{ij}y^{i}z^{j}$. Each inner product defines a norm $||y||_{g}:=<y,y>_{g}=g_{ij}y^{i}y^{j}$ for a vector $y\in T_{x}M$ with respect to $g$. Hence, a vector $y$ on the tangent space $T_{x}M$ can have different norms according to different Finsler metrics defined on $M$. For a Riemannian metric $g_{ij}(\cdot)$, $\overline{F}(x^{i},y^{i})=(g_{ij}y^{i}y^{j})^{\frac{1}{2}}+b_{i}(x)y^{i}$, where $\beta=b_{i}(x)y^{i}$ is a 1-form on $M$ with $||\beta||_{g}<1$, is a Finsler structure on $M$ and its associated Finsler metric is called a Randers metric, see [28] for more details.

The nonlinear complementarity problems (NCPs) arise from optimisation theory, engineering and economic applications. The restricted NCP functions which can be used to reformulate NCPs as constrained optimisation problems are first introduced by Yamashita [30]. Furthermore, the discretisation of infinite-dimensional variational inequalities leads to linear and nonlinear complementarity problems with many degrees of freedom. Luo and Tseng [24] proposed a class of merit functions for the NCPs and showed that they satisfy several interesting properties under some assumptions. Kanzow, Yamashita and Fukushima have used the similar idea and proposed new merit functions for the NCP in [18].

For a given smooth mapping $F:I\!\!R^{n}\rightarrow I\!\!R^{n}$, the NCP consists of finding a vector $x\in I\!\!R^{n}$ such that

$$x\geq 0,\qquad F(x)\geq 0,\qquad F(x)^{T}.x=0,$$

(2)

where $F(x)^{T}$ is the transpose of $F(x)$. Complementarity problems can be reformulated as systems of nonlinear equations in several ways. A large number of methods has been developed based on Newton method and its generalisations. In order to overcome some disadvantages of the class of non-smooth Newton methods and the class of the so-called smoothing methods, a third class known as Jacobian smoothing methods developed in [16]. A Jacobian smoothing method is a mixture of Newton and non-smooth methods and is based on solving the mixed Newton equation: a combination of the original semi-smooth function and the Jacobian of the smooth operator of the Clarke generalised Jacobian [7]. There are also several related algorithms entitled Newtonian algorithms, see for instance [9, 15, 16, 26, 30]. Further, a solution of NCP with neural networks algorithm was presented in [23]. Among these algorithms, the modified Newton algorithm is preferred.

The modified Newton algorithm is a reformulation of system of differential equations (2) that converts it to a non-modal optimisation problem which is convergent under some conditions, see Section 8.7 of [5]. This reformulation is given by the system of equations:

$$\phi(x)=\left(\begin{array}[]{lcl}\phi_{1}(x)\\ \vdots\\ \phi_{n}(x)\end{array}\right)=\left(\begin{array}[]{lcl}\phi(x_{1},F_{1}(x))\\ \vdots\\ \phi(x_{n},F_{n}(x))\end{array}\right)=0,$$

(3)

where the NCP-function $\phi$ is the Fisher-Burmeister NCP-function ([10, 11]) defines as follows,

$$\begin{array}[]{ll}\phi:I\!\!R^{2}\rightarrow I\!\!R,\qquad\phi(a,b)=\sqrt{a^{2}+b^{2}}-(a+b),\end{array}$$

(4)

where $\phi(a,b)=0\Leftrightarrow a\geq 0,\,b\geq 0,\,ab=0$. The resulting system of nonlinear equations (2) is semi-smooth and the NCP has an solution $x$ if and only if $x$ is a solution for (3). Note that the function $\phi$ is locally Lipschitz and continuous at every point. Thus, the Clarke generalised Jacobian at every point is defined. In [12], the NCP is recast as an unconstrained minimisation problem and the natural merit function $G:I\!\!R^{n}\rightarrow I\!\!R$ given by

$$G(x)=\frac{1}{2}\sum_{i=1}^{n}\phi(x_{i},F_{i}(x))^{2}=\frac{1}{2}\|\phi(x)\|^{2},$$

(5)

is considered. Also, it is proved that any stationary point of the above function is a solution of the NCP if the mapping $F$ involved in Eq. (2) is continuously differentiable and monotone. Hence, the solution of the NCP are given by solving

$$\min_{x\in I\!\!R^{n}}G(x).$$

(6)

The NCP mainly applied in solving the traffic equilibrium problem which is studied here, and the Karush-Kuhn-Tucker (KKT) optimality conditions [13].

Network equilibrium models have a variety of applications in urban transportation, energy distribution, game theory, spatially separated economic markets, electrical networks, and water resource planning, [1]. Although the idea of traffic equilibrium originated as early as 1924 with Frank Knight [20], the mathematical description of equilibrium was provided for the first time in 1952 by Wardrop. The Wardrop’s equilibrium principals [29] are related to the idea of Nash equilibrium [22] in game theory which is developed separately. However, analysing the transportation networks with many players involved is more difficult than analysing games with a few number of players. The Wardrop’s principals states as follows:

Here, we illustrate that the Fischer-Burmeister function is a special Randers metric.

By virtue of the above proposition, solutions of the NCP, i.e. the optimised paths of the Fischer-Burmeister function, are geodesics of a Randers metric given by Eq. (12).

The traffic congestion and transport demand in some hours of a day (peak hours) are extremely increasing. A typical solution to address this issue, instead of building additional infrastructure, is introduction of dynamic elements to the road traffic management. This includes for instance using sensors to measure traffic flows and automatic interconnected guidance systems (for example traffic signs which open a lane in different directions depending on the time of day) to manage traffic in peak hours. Here, we generalise the method of solving the NCP (in the previous subsection) to dynamic systems.

Now, we can present a Finsler geometrical model for solving the dynamical Wardrop’s user equilibrium problem: