A neural network for a generalized vertical complementarity problem

1.   Introduction

In this paper, a generalized vertical complementarity problem is investigated as follows: find a vector $x\in \mathbb{R}^{n}$ such that

where $F_{ij}:\mathbb{R}^{n}\to\mathbb{R}, i = 1, 2, \cdots, n, j = 1, 2, \cdots, l$ are twice continuously differentiable functions.

Finite dimensional complementarity problem and its applications in engineering, economy, game theory and networks have become a mature and fruitful discipline in mathematical programming. When the involved functions $F_{ij}(\cdot), i = 1, 2, \cdots, n, j = 1, 2, \cdots, l$ in (1.1) are linear, the problem (1.1) becomes a generalized vertical linear complementarity problem (GVLCP), which was first proposed in ^[1]. If, in addition, $F_{i1}(x) = x_{i}, i = 1, 2, \cdots, n$, then (1.1) is a vertical linear complementarity problem (VLCP). There are several methods for solving VLCP and GVLCP, like smoothing Newton methods ^[2,3], continuation methods ^[4,5], projected splitting methods ^[6] or algorithms that are based on formulating equivalent complementarity problems ^[7,8,9,10]. And other relevant works are ^{[1,11,12,13,14,15,16]}. In the case when $l = 2$ and $F_{i1}(x) = x_{i}, i = 1, 2, \cdots, n$, (1.1) is a nonlinear complementarity problem (NCP) in ^[17,18]. In the introduction of ^[18], merit function approach, nonsmooth Newton method, smoothing methods, regularization approach, interior-point method, and proximal point algorithm are mentioned, which are well-known approaches to solve NCP. If, in addition, $F_{i2}(x), i = 1, 2, \cdots, n$ are linear functions, problem (1.1) is a linear complementarity problem (LCP) in ^[19,20,21]. And smoothing Newton method, projected method, many modulus-based algorithms are mentioned for solving LCP ^[20,21] and references therein. $ If an optimization problem contains the generalized vertical complementarity problem as its constraint, it is called mathematical programming with general vertical complementarity constraints (MPVCC) ^{[22,23,24,25]}, which can be found in equilibrium systems, engineering design, optimal control and game theory ^[26].

The traditional research of optimization was restricted by theoretical investigation and numerical implementation. However, neural networks were used to solve optimization problems ^[27,28,29] since 1980s. The LCP and the NCP were studied in ^[30] and ^[31] through neural networks, respectively. Another new neural network was proposed in ^[19] for solving the LCP. In recent years, neural networks are still popular among scholars, and many complex optimization problems were solved by using neural networks ^{[18,32,33,34,35,36,37,38,39,40]}. As shown in ^[30], the significant and unique feature of neural network to optimization is the realization of simple and real-time hardware implementation.

In this paper, we focus on solving the generalized vertical complementarity problem (1.1) through neural networks. At first, based on the properties of log-exponential function, we reformulate the problem (1.1) as an unconstrained minimization problem and the consistency is studied. Then the neural network is used to solve the unconstrained minimization problem, and under certain conditions, the equilibrium point is asymptotically stable or exponentially stable. The obtained results are finally applied to an example of generalization of bimatrix game.

The main contributions of this paper are as follows: first, different from the neural networks in ^[30] and ^[31], a neural network is constructed by a smoothing form of the nonsmooth problem (1.1), which avoids computing subgradients in the nonsmooth case. Second, some conditions ensuring consistency of the the equilibrium point in the neural network to the solution of (1.1) are provided. Moreover, asymptotical stability and exponential stability of equilibrium point of the differential equation with the initial condition are studied under certain conditions. Third, the neural network is finally used to solve a generalized vertical complementarity problem in a generalization of bimatrix game.

The main difficulties of this paper are as follows: first, the proof of consistency is obtained by combining the definition of convergence of sequence of set, the properties of log-exponential function, and the properties of solution mapping, which requires more complex techniques in variational analysis. Second, in the process of approximating the original problem, $\Phi$ is smooth when $\alpha > 0$, and not smooth when $\alpha = 0$. Hence, in order to ensure the convergence of solutions, the above two cases are investigated to complete the consistency analysis of the original problem (1.1), the approximated problem (3.3) and the differential Eq (3.5). Third, in the study of the stability of the neural network in the Lyapunov sense, many definitions and theorems on stability are mentioned, which need some differential equation techniques to combine them to get the desired conclusion.

This paper is organized as follows: in Section 2, some preliminary knowledge are provided. In Section 3, we reformulate the complementarity problem as an unconstrained minimization problem and construct a neural network. The consistency and stability results are discussed in Section 4 and Section 5, respectively. Simulation results are presented in Section 6. Finally, some concluding remarks are drawn in Section 7.

2.   Preliminaries

In this section, some background material are provided.

Let $\left\|\cdot\right\|$ denote the Euclidean norm of a vector or the Frobenius norm of a matrix. Let $\mathbb{B}$ denote the closed unit ball and $\mathbb{B}(x, \delta)$ denote the closed ball around $x$ of radius $\delta\ > 0$. Let $\nabla\phi(x)$ denote the gradient of $\phi$ : $\mathbb{R}^{n}\to\mathbb{R}$ at $x$. For a mapping $\varphi$ : $\mathbb{R}^{n}\to\mathbb{R}^{m}$, $J\varphi(x)$ denotes the Jacobian of $\varphi$ at $x$. The notation of Clarke generalized Jacobian ^[41] is as follows.

Definition 2.1. Let $F$ : $\mathbb{R}^{n}\to\mathbb{R}^{m}$ be locally Lipschitz at $\bar{x}\in \mathbb{R}^{n}$, by Redemacher's theorem, $F$ is differentiable almost everywhere. Let $\omega_{F}$ denote the set where $F$ is differentiable. We can define the B-subdifferential of $F$ at $\bar{x}$ as

and the Clarke subdifferential of $F$ at $\bar{x}$ as

where co denotes the convex hull of a set.

The log-exponential function is a smoothing function for max-type functions. Let $V$ : $\mathbb{R}^{n}\to\mathbb{R}$ be defined by

where $v_{i}$, $i = 1, 2, \cdots, m$, are continuously differentiable functions. Notice that, $V(x)$ is continuous in $\mathbb{R}^{n}$, but $V(x)$ is not differentiable everywhere. The log-exponential function is defined as follows.

Definition 2.2. ^[42,43] For any $\alpha > 0$, the log-exponential function of $V(x)$, denoted as $\widetilde{V}(\alpha, x): \mathbb{R}^{n+1}\to\mathbb{R}$, is defined by

Notice that,

which implies $\lim\limits_{\alpha\to 0}\widetilde{V}(\alpha, x) = V(x)$ and the convergence is uniformly with respect to $x$. From the definition, we know that $V(\alpha, x)$ is a smoothing function with respect to $x$ for any $\alpha > 0$.

Definition 2.3. ^[43] For sets $X^{n}$ and $X$ in $\mathbb{R}^{n}$, $X$ is closed, the sequence $\{X^{n}\}_{n\in N}$ is called convergence to $X$ if

with

where $\mathcal{N}_{\infty} = \left\lbrace N\subseteq{\bf{N}} \mid {\bf{N}}\backslash N\ \; finite\; \right\rbrace, \mathcal{N}^{\#}_{\infty} = \left\lbrace N\subseteq{\bf{N}} \mid N \ \; infinite\; \ \right\rbrace$ and ${\bf{N}}$ denotes the set of all positive integer numbers.

Definition 2.4. ^[44] Let $h$ : $\mathbb{R}^{n}\to\mathbb{R}$ be locally Lipschitz. We call $\widetilde{h}$ : $\mathbb{R}^{n}\times (0, +\infty)\to \mathbb{R}$ a smoothing function of $h$, if $\widetilde{h}$ satisfies the following conditions:

1) For any fixed $\mu \in (0, +\infty)$, $\widetilde{h}(\cdot, \mu)$ is continuously differentiable in $\mathbb{R}^{n}$, and for any fixed $x \in \mathbb{R}^{n}$, $\widetilde{h}(x, \cdot)$ is differentiable in $(0, +\infty)$.

2) For any fixed $x \in \mathbb{R}^{n}$, $\lim\limits_{\mu \to 0} \widetilde{h}(x, \mu) = h(x)$.

3) $\{\lim_{z \to x, \mu\to 0} \nabla_{z} \widetilde{h}(z, \mu)\} \subseteq \partial h(x)$.

4) There is a positive constant $\kappa > 0$ such that $\left| \nabla_{\mu} {h}(x, \mu)\right| \le \kappa$, $\forall x \in\mathbb{R}^{n}, \mu \in (0, +\infty)$.

Some fundamental definitions about differential equation in the ^[45] are reviewed. Consider the following differential equation

Definition 2.5. We said $x^{*} = x(t^{*})$ is an equilibrium point or the stable state of the dynamical system (2.3) if $H(x^{*}) = 0$. And $x^{*}$ is called an isolated equilibrium point if there exists a neighbourhood $\Omega$ of $x^{*}$, $\Omega \subseteq \mathbb{R}^{n}$, such that $H(x^{*}) = 0$ but $H(x)\ne 0$ for $x\in \Omega\backslash \{x^{*}\}$.

Definition 2.6. An isolated equilibrium point $x^{*}$ of (2.3) is asymptotically stable if it is stable in the sense Lyapunov stable and there exists a $\delta > 0$, such that for any maximal solution $x(t), t \in \left[t_{0}, t_{1}\right)$, if $\left\|x_{0}-x^{*}\right\| < \delta$, then one has $t_{1} = +\infty$ and $\lim\limits_{t\to \infty} x(t) = x^{*}$.

Definition 2.7. An isolated equilibrium point $x^{*}$ of (2.3) is said to be exponentially stable if there exist $\omega < 0$, $\kappa > 0$, $\delta > 0$ such that arbitrary solution $x(t)$, with the initial condition $x(t_{0}) = x_{0}$, $\left\|x_{0}-x^{*}\right\| < \delta$, is defined on $\left[t_{0}, +\infty \right)$ and satisfies

Definition 2.8. ^[46] Let $L = \{1, 2, \cdots, n\}$. The function $F$ : $\mathbb{R}^{n}\to\mathbb{R}^{n}$ is said to be a $P_{0}$ function if for all $x, y\in\mathbb{R}^{n}$ with $x\ne y$

Let $F^{i}(x) = (F_{1i}(x), F_{2i}(x), \cdots, F_{ni}(x))^{T}$, $i = 1, 2, \cdots, l$. If for each $x\in \mathbb{R}^{n}$ and $i \in L$, $F_{i}(x) \in \{F^{1}_{i}(x), F^{2}_{i}(x), \cdots, F^{l}_{i}(x)\}$, then $F$ is a row representative of $\{F^{1}, F^{2}, \cdots, F^{l}\}$. And we say $\{F^{1}, F^{2}, \cdots, F^{l}\}$ has $P_{0}$ property if every representative of $\{F^{1}, F^{2}, \cdots, F^{l}\}$ is a $P_{0}$ function.

3.   Neural network

In this section, (1.1) is approximated as an unconstrained minimization problem by using the log-exponential function. Then, the neural network in the forms of differential equation is proposed for solving the unconstrained minimization problem.

For convenience, in this paper, we only consider (1.1) for $l = 3$, that is finding a vector $x\in \mathbb{R}^{n}$ such that

Notice that for each $k$, $\min\{F_{k1}(x), F_{k2}(x), F_{k3}(x)\} = 0$ can be approximated by the following equation:

in the sense that

where

for numbers $a_{i}\in \mathbb{R}$, $i = 1, 2, 3.$

Then we obtain the following approximation of problem (3.1):

Suppose that $x_{\alpha}$ satisfies $\Phi(x_{\alpha}, \alpha) = 0$ for some $\alpha > 0$. Then one has that $\phi_{\alpha}(F_{k1}(x), F_{k2}(x), F_{k3}(x))$, $k = 1, 2, \cdots, n$ is twice continuously differentiable at $x_{\alpha}$ and

where

with $\sum_{i = 1}^{3} \eta_{ki} (x, \alpha) = 1$.

Notice that (3.3) has a solution if and only if the following least square problem has the zero minimum:

It is clear that $f(x, \alpha)$ is continuously differentiable.

Next, the frame structure of neural network is given for solving problem (3.1), which is based on the steepest descent method for the reformulated problem (3.4):

$\tau$ is a scale factor. $\tau > 1$ indicates that a longer step could be taken in simulation. And to simplify our analysis, let $\tau = 1$. A block diagram of the model is shown in the following Figure 1.

We know from Fermat's theorem that for a fixed $\alpha > 0$ if $x(\alpha)$ is an optimal solution of (3.4), then $\nabla_x f(x(\alpha), \alpha) = 0$, which means that $x(\alpha)$ is an equilibrium point of (3.5).

The existence of equilibrium of (3.5) is illustrated by the next theorem.

Theorem 3.1. Suppose $\{F^{1}, F^{2}, \cdots, F^{l}\}$ has $P_{0}$ property, where $F^{i}(x) = (F_{1i}(x), F_{2i}(x),$ $\cdots, F_{ni}(x))^{T},$ $i = 1, 2, \cdots, l$, then for each $\alpha > 0$, (3.5) has an equilibrium point.

Proof. By ^[46,Theorem 3.4], if $\{F^{1}, F^{2}, \cdots, F^{l}\}$ has $P_{0}$ property, then for each $\alpha > 0$, $\Phi(x, \alpha) = 0$ has a unique solution $x(\alpha)$, which means that $\nabla_x f(x(\alpha), \alpha) = 0$. The proof is completed.

4.   Consistency analysis

In this section, the relationship between the solutions of problem (3.1) and the solutions of problem (3.3), the relationship between the solutions of problem (3.1) and the equilibrium point of problem (3.5) are investigated.

Consider the following sets

Lemma 4.1. ^[24,Lemma 4.1] For a solution mapping $\Sigma$ : $\mathbb{R}^{n_{1}} \to\mathbb{R}^{n_{2}}$ defined by

where $\Psi :$ $\mathbb{R}^{n_{2}}\times\mathbb{R}^{n_{1}}\to\mathbb{R}^{n_{3}}$ is continuous at $(x_{0}, p_{0})$, thefunction $\Psi(\cdot, p)$ is locally Lipschitz on $\mathbb{R}^{n_{2}}$ for every $p\in \mathbb{R}^{n_{1}}$, $K$ isa closed convex set in $\mathbb{R}^{n_{3}}$ and the map $(x, p)\longmapsto \partial^{c}_{1}\Psi(x, p)$, where $\partial^{c}_{1}\Psi(x, p)$ denotes the generalized Jacobian of $\Psi(\cdot, p)$ at $x$, is upper semicontinuous at $(x_{0}, p_{0})$. Let $\Psi_0(x) = \Psi(x, p_{0})$ for $x\in \mathbb{R}^{n_{2}}$.If the following regularity condition

holds for every $A\in \partial^{c}\Psi_0(x_{0})$, then there existconstants $\mu > 0, \varepsilon > 0$ and $\delta > 0$ such that

For $\bar{x}\in X_{0}$, let index sets

Next inspired by ^[24], a theorem is summarized about the convergence of the set $X_{\alpha}$ as $\alpha$ tends to zero.

Theorem 4.2. Suppose the regularity condition

holds for any $\bar{x} \in X_{0}$ and any $a\in \mathbb{R}^{3}$ satisfying $\sum_{i = 1}^{3}a_{i} = 1$ and $a_{i} \ge 0$ for each $i$, where $\Xi(\bar{x}, a)\in \mathbb{R}^{n\times n}$ and thek-th row of $\Xi(\bar{x}, a)$ is

with $i_{k}$ is the index satisfying $(k, i_{k}) \in I(\bar{x})$, then

Proof. At first, we show that $\limsup\limits_{\alpha \to 0+}X_{\alpha}\ \subseteq\ X_{0}$. It suffices to prove that if there exist a number sequence $\{ \alpha_{n} \} \to 0$ and a sequence $\{x_{n}\}$ converging to $\bar{x}$ as $n \to \infty$ such that $x_{n}\in X_{\alpha_{n}}$ for each $n$, then $\bar{x}\in X_{0}$. Indeed, by (2.2), we have for each $k$,

which means that $\bar{x} \in X_{0}$.

Next we show that for any $\bar{x}\in X_{0}, \bar{x}\in \liminf\limits_{\alpha \to 0+}X_{\alpha}$. It suffices to show that for any $\alpha_{n} \to 0$, there exists a sequence $\{x_{n}\}$ satisfying $x_{n}\in X_{\alpha_{n}}$ for each $n$ such that $x_{n}\to \bar{x}$. According to Lemma 4.1, if the following condition

holds for any $A(\bar{x})\in \partial^{c}[\Phi(\cdot, 0)](\bar{x})$, where $\Phi$ is defined as in (3.3), then there exist numbers $\mu > 0, \varepsilon > 0$ and $\delta > 0$ such that

Especially, we have

which means for each $n$, $X_{\alpha_{n}}\ne \emptyset$. Therefore, there exists a sequence $\{x_{n}\}$ satisfying $x_{n}\in X_{\alpha_{n}}$ for each $n$ and $x_{n} \to \bar{x}$ as $n\to \infty$. Then under condition (4.2), $\bar{x} \in \liminf\limits_{\alpha \to 0}X_{\alpha}$. As a result, to obtain the conclusion, we only need to show condition (4.1) is the sufficient condition for (4.2). Consider the index

Since for the index $k\in \{1, 2, \cdots, n \} \backslash K(\bar{x})$, there exists only one index $i\in \{1, 2, 3\}$ such that $F_{ki}(\bar{x}) = 0$, we obtain

For index $k \in K(\bar{x})$, by Definition 1, we have

where $J_{k}(\bar{x}) = \left\lbrace i\in\{1, 2, 3\} :\ \exists\ j\ne i \; {\rm{such\; that }}\; \ F_{ki}(\bar{x}) = F_{kj}(\bar{x}) = 0\ \right\rbrace$. So the condition (4.1) implies conidtion (4.2).

According to the Theorem 4.2, under some conditions, we have $\lim\limits_{\alpha\to 0+}X_{\alpha} = X_{0}$. Now a natural question is the relationship between $X_{1\alpha}$ and $X_{0}.$

At the beginning, let us consider the following problem:

where

It is clear that $g_{1}(x)$ is not differentiable, although the squared norm is differentiable, we cannot say the composition $g(x)$ is differentiable by the chain rule in Mathematical Analysis. In fact, $g(x)$ is continuously differentiable.

Lemma 4.3. ^[47,48]The function $g(x)$ is continuously differentiable with thegradient $\nabla g(x) = V^ \mathrm{ T }g_{1}(x)$ for any arbitraryelement $V\in \partial^{c} g_{1}(x)$.

Theorem 4.4. Suppose $x(\alpha)\in X_{1\alpha}$, $\lim\limits_{\alpha\to0+}x(\alpha) = \bar{x}$, if any $V\in \partial^{c} g_{1}(\bar{x})$ is nonsingular, then $\bar{x} \in X_{0}$.

Proof. We know that

Then

Notice that

According to the Definition 4, we have

that is, there exists $V_{0} \in \partial^{c} g_{1}(\bar{x})$ such that

We know from proof of Theorem 4.2 that as $\alpha \to 0+$,

Therefore we have as $\alpha \to 0+$,

That is, $V_{0}^ \mathrm{ T }g_1(\bar{x}) = 0$. Since $V_{0}$ is nonsingular, then $g_1(\bar{x}) = 0,$ i.e., $\bar{x} \in X_{0}$.

We know from the Theorem 4.4 that every cluster point of $\{x(\alpha)\}$ is a solution of generalized vertical complementarity problem (3.1) under conditions in Theorem 4.4, where $x(\alpha)$ is an equilibrium point of the neural network (3.5) for $\alpha > 0.$

In Section 3 and Section 4, for the sake of illustration, consistency analysis is made for problem (1.1) when $l = 3$. In fact, the consistency analysis in this paper can be extended to (1.1) for an arbitrary choice of $l$, just replace the relevant $3$ with $l$ in the corresponding theorems and proofs.

5.   Stability analysis

In this section, asymptotic stability and exponential stability for differential Eq (3.5) are studied.

Let $\alpha > 0$, suppose that $x^{*}$ is an isolated equilibrium point of (3.5), and $\Omega_{*} \subseteq \mathbb{R}^{n}$ is a neighbourhood of $x^{*}$ such that

First, we give a theorem to show the global convergence of solutions of differential Eq (3.5).

Theorem 5.1. (i) For an arbitrary initial state $x_{0}$, there exists exactly one maximal solution $x(t)$, $t\in \left[t_{0}, \tau(x_{0}) \right)$. (ii) If the level set $\Omega(x_{0}) = \left\lbrace x\in \mathbb{R}^{n}\mid f(x, \alpha)\le f(x_{0}, \alpha) \right\rbrace$ is bounded or $F_{ki}(x)$ are Lipschitz continuous, $k = 1, 2, \cdots, n, i = 1, 2, 3$, then $\tau(x_{0}) = +\infty$.

Proof. (i) It is obvious that $\nabla_{x} f(x(t), \alpha)$ is continuous, according to the ^[31,Theorem 2.5], we can get the conclusion easily. (ii) First, we start with the first case, the level set $\Omega(x_{0})$ is bounded. If otherwise, $\tau(x_{0}) < +\infty$. Based on ^[31,Theorem 2.6], we have $\lim\limits_{t\to \tau(x_{0})}\left\|x(t)\right\| = +\infty$. Let

where $\Omega^{c}(x_{0}) = \mathbb{R}^{n}\backslash\Omega (x_{0})$. Because of the continuity of $f$, $\Omega (x_{0})$ is a closed set, and $\Omega (x_{0})$ is bounded by the condition. Consequently, $\Omega (x_{0})$ is a compact set. Hence, we can obtain $x(\tau_{0})\in \Omega (x_{0})$ and $\tau_{0} < \tau(x_{0})$, this implies there exists a $s\in \left[t_{0}, \tau(x_{0}) \right)$, such that

However,

so $f(\cdot, \alpha)$ is not increasing in monotony, this is a contradiction, therefore $\tau(x_{0}) = +\infty$. Then in the second case, if $F_{ki}, k = 1, 2, \cdots, n, i = 1, 2, 3$ are Lipschitz continuous in $\mathbb{R}^{n}$, then $\nabla_{x} f(x, \alpha)$ is Lipschitz continuous in $\mathbb{R}^{n}$. According to ^[31,Theorem 2.5], $\tau(x_{0}) = +\infty$.

Theorem 5.2. For an arbitrary initial state $x_{0}$, if the level set $\Omega(x_{0})$ is bounded or $F_{ki}$, $k = 1, 2, \cdots, n$, $i = 1, 2, 3$ are Lipschitz continuous in $\mathbb{R}^{n}$, then the differential Eq (3.5) has a unique solution on $\left[t_{0}, +\infty \right)$.

Proof. The proof is the same as the proof of Theorem 5.1. In fact, the theorem is an intuitive statement of Theorem 5.1. If the above conditions hold, then the differential Eq (3.5) has global convergence for an arbitrary initial state $x_{0}$.

Lemma 5.3. ^[45,Theorem 2.6] An isolated equilibrium point $x^{*}$ is asymptotically stable ifthere exists a Lyapunov function over some neighbourhood $\varOmega_{*}$ of $x^{*}$, satisfying

Next we show the asymptotic stability of differential Eq (3.5) under mild conditions.

Theorem 5.4. If $x^{*}$ is an isolated equilibrium point of differential Eq (3.5), then $x^{*}$ is asymptotically stable for (3.5).

Proof. First, we need to prove that $f(x, \alpha)$ is a Lyapunov function over the set $\Omega_{*}$ for Eq (3.5). From the definition of $f(x, \alpha)$, we know that $f(x, \alpha)$ is nonnegative over $\mathbb{R}^{n}$. Since $x^{*}$ is an isolated equilibrium point $f(x^{*}, \alpha) = 0$, for any $x \in \Omega_{*} \setminus \{x^{*}\}$, $f(x, \alpha) > 0$. Now we check the second condition in the definition of Lyapunov function ^[45]. Notice that

Hence, the function $f(x, \alpha)$ is a Lyapunov function for (3.5) over the set $\Omega_{*}$. Because of $x^{*}$ being an isolated equilibrium point, we know ${\frac{df(x(t), \alpha)}{dt}} < 0$, $\forall x \in \Omega_{*} \setminus \{x^{*}\}$. It follows from Lemma 5.3 that $x^{*}$ is asymptotically stable for (3.5).

Theorem 5.5. If $J_x \Phi(x^{*}, \alpha)$ is nonsingular for $\alpha > 0$, then $x^{*}$ is exponentially stable for (3.5).

Proof. Since $J_x \Phi(x^{*}, \alpha)$ is nonsingular, $x^{*}$ satisfies $\Phi(x^{*}, \alpha) = 0$. Notice that $x^{*}$ is an isolated equilibrium point of (3.5), therefore, $x^{*}$ is asymptotically stable by Theorem 5.4. Let $\delta > 0$ be sufficiently small such that for any $x(t) \in \mathbb{B}(x^{*}, \delta), x(t) \to x^{*}$ as $t \to +\infty$. Notice that, $J_x\Phi(x, \alpha) J_x\Phi(x, \alpha)^{T}$ is an $n \times n$ nonsingular matrix, hence there exist $\kappa_{1} > 0$ and $\kappa_{2} > 0$ such that

By the smoothness of the function $\Phi(x, \alpha)$, we have the following expansion

Suppose that $\delta$ is small enough, such that

for some $0 < \epsilon < \kappa_{1}$ and $\forall x\in \mathbb{B}(x^{*}, \delta)$. Now let

Then

Let

be the first exit time of the solution from the ball $\mathbb{B}(x^{*}, \delta)$. Combine the above formulas, and $\Phi(x^{*}, \alpha) = \; 0$, then for arbitrary $t \in \bar{I} = \left[t_{0}, \bar{\tau} \right)$,

According to ^[45,Corollary 2.1], the following inequality

is equivalent to the definition of exponential stability

where $\omega = - \kappa_{1} +\epsilon \setminus 2 < 0$. If $\bar{\tau} < + \infty$, then

that is a contradiction. Thus $\bar{\tau} = +\infty$ and we complete the proof of exponential stability.

Theorem 5.6. Assume that the neural network (3.5) is Lyapunov stable, for arbitrary initial state $x_{0}$, for a fixed $\alpha \in (0, +\infty)$, if the level set $\Omega(x_{0})$ is bounded or $F_{ki}(x)$, $k = 1, 2, \cdots, n, i = 1, 2, 3$ are Lipschitz continuous, then the solution trajectory $x_{\alpha}(t)$ of neural network (3.5) is global convergence to the stationary point of (3.4). Furthermore, if $J_{x}\Phi(x^*, \alpha)$ is nonsingular, then $x_{\alpha}(t)$ is global convergence to the solution of (3.4).

Proof. If the condition holds, then the solution interval can be extended to infinity through Theorem 5.1 and neural network (3.5) has a unique solution denoted as $x_{\alpha}(t)$, which satisfies $\lim_{t\to +\infty}x_{\alpha}(t) = x^*$ with $\nabla_{x}f(x^*, \alpha) = J_{x}\Phi(x^*, \alpha)\Phi(x^*, \alpha) = 0$. Hence, the solution trajectory $x_{\alpha}(t)$ of neural network (3.5) is global convergence to the stationary point of (3.4). Furthermore, if $J_{x}\Phi(x^*, \alpha)$ is nonsingular, which means that $\Phi(x^*, \alpha) = 0$, then $x_{\alpha}(t)$ is global convergence to the solution of (3.4).

6.   Application to a generalized bimatrix game and simulation

In this section, an example in a generalized bimatrix game is illustrated to test our neural network.

At first, the generalized bimatrix game is described, which is based on a bimatrix game introduced by ^[49] and a generalized SER-SIT stochastic games model in ^[50]. Let $\mathcal{A}$ and $\mathcal{B}$ be two nonempty sets in $\mathbb{R}^{m \times n}$. If $R_{i} \in \left\lbrace A_{i} : A \in \mathcal{A} \right\rbrace$ for $i = 1, 2, \cdots, m$, then the $m \times n$ matrix $R$ is said to be a row representative of $\mathcal{A}$, where the subscript denotes the corresponding row. In the same way, if $S^{j} \in \left\lbrace B^{j} : B \in \mathcal{B} \right\rbrace, j = 1, 2, \cdots, n,$ then the $m \times n$ matrix $S$ is said to be a column representative of $\mathcal{B}$, where the subscript denotes the corresponding column. Suppose $\mathcal{A} = \left\lbrace C, D \right\rbrace$, $\mathcal{B} = \left\lbrace E, F \right\rbrace$, where

and

Let $\bar{x} \in \mathbb{R}^{m}$ and $\bar{y} \in \mathbb{R}^{n}$, if there exist a row representative $G$ of $\mathcal{A}$, and a column representative $H$ of $\mathcal{B}$ such that

for all probability vectors $u$ and $v$, for all row representative matrices $R$ of $\mathcal{A}$, and for all column representative matrices $S$ of $\mathcal{B}$, then the mixed strategies $(\bar{x}, \bar{y})$ is said to be a generalized Nash equilibrium pair for the generalized bimatrix game.

The game theoretic implication of the above generalized Nash equilibrium pair is as follows. In the game denoted by $\varLambda(\mathcal{A}, \mathcal{B})$, player I deals with the rows of matrices in $\mathcal{A}$ while player II deals with the columns of matrices in $\mathcal{B}$. Player I chooses a row representative $A$ of $\mathcal{A}$ and a probability distribution $x$ on the set $\left\lbrace 1, 2\right\rbrace$. Player II chooses a column representative $B$ of $\mathcal{B}$ and a probability distribution $y$ on the set $\left\lbrace 1, 2\right\rbrace$. Then the first player's cost is $x^{T}Gy$ while the second player's cost is $x^{T}Hy$. The existence of an equilibrium for $\varLambda(\mathcal{A}, \mathcal{B})$ describes the stage at which no player can decrease his cost by unilaterally changing his row/column selection and probability distribution.

By ^[49,Proposition 1], the existence of a pair of probability vectors $(\bar{x}, \bar{y})$ satisfying the (6.1) is equivalent to the existence of the solution $(\widetilde{x}, \widetilde{y})$ to the equation

where $e = (1, -1)^{T}$. Moreover, if $F(\widetilde{x}, \widetilde{y}) = 0$ and $\left\| \widetilde{x} \right\| \left\| \widetilde{y} \right\| \ne 0$, then $(\widetilde{x} /\left\| \widetilde{x} \right\|, \widetilde{y} / \left\| \widetilde{y} \right\|)$ is a generalized Nash equilibrium pair for the generalized bimatrix game. Notice that (6.2) is just a generalized vertical complementarity problem:

where

To solve the above problem, by introducing the log-exponential function and $\alpha > 0$, we obtain a least square problem to approximate (6.3):

where

The Eq (6.3) is

The following neural network is constructed for solving problem (6.4):

The simulation is based on Matlab version 9.5, and the package ode45 in Matlab is used to solve differential equations. The starting point $z_{0}$ is a uniformly distributed random four dimensional vector in $[0, 1]\times[0, 1]\times[0, 1]\times[0, 1]$.

Here are some detailed simulation results in the following tables.

Problem (6.4) has a unique solution $z^{*} = (1, 0, 2, 0)^{T}$. According to Table 1, where $\tau$ is set to be equal to $1000$, $\alpha \le 0.3$, the approximate solutions obtained by neural networks are almost as the same as $z^{*}$, but as $\alpha$ gets bigger, the distance between the approximate solutions and $z^{*}$ become larger. From Table 2, we know where $\alpha$ is set to be equal to $0.01$ and $\tau = 1, 10,100, 1000$, the approximate solutions are almost as the same as $z^{*}$, but only the length of the convergence has changed.

Moreover, we give Figures 2 and 3 about the trajectories of $z(t)$ when $\tau = 1000$ and $\alpha = 0.01, 0.05$.

The following observations can be made through the above tables and figures: (i) All trajectories converge to their corresponding static states, respectively. The convergence is faster when a larger scaling factor is applied. (ii) The smaller $\alpha$ is, the solutions approximate to the solution of the true problem ($\alpha \ge 0.01$). As $\alpha$ gets bigger, the distance between the approximate solutions and the solution of the true problem become larger. These limited numerical experiments verified the stability of the proposed neural network.

7.   Conclusions

In this paper, a neural network is constructed to solve a generalized vertical complementarity problem. The log-exponential function is introduced to reformulate the generalized vertical complementarity problem in terms of an unconstrained minimization problem, and then we construct a neural network based on the unconstrained minimization problem. Some conditions ensuring consistency of equilibrium point of the neural network to the solution of generalized vertical complementarity problem are provided. Moreover, the asymptotical stability and exponential stability of equilibrium point of neural network are studied in detail. Finally, an example of generalized bimatrix game is illustrated to test our neural network.

Acknowledgments

The research is supported by the National Natural Science Foundation of China under Project Grant Nos. 12171219 and 61877032, the Liaoning Revitalization Talents Program No. XLYC2007113, Scientific Research Fund of Liaoning Provincial Education Department under Project No. LJKZ0961 and Liaoning BaiQianWan Talents Program.

Conflict of interest

The authors declare no conflict of interest.