Modified nonmonotonic projection Barzilai-Borwein gradient method for nonnegative matrix factorization

1.   Introduction

In the literature, there are many works that are concern with the study of differential game problem in the Hilbert spaces such as ${\mathbb{R}^{n}}$ and ${\ell_2}$ (see, for example ^{[5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]}). In particular, the space ${\ell_2},$ consists of elements of the form $\alpha = (\alpha_{1}, \alpha_{2}, \dots)$, such that $\sum_{k = 1}^{\infty}\alpha_{k}^{2} < \infty.$ The inner product and norm are defined as follows:

where $, \alpha, \beta, \varrho \in {\ell_2}.$

The works cited above can be categorized into three groups. The first group are the woks ^{[1,6,10,12,14,16,17,20,25,26,27,28,29]} and ^[30] concern with finding conditions for completion of pursuit. Whereas, the works ^{[13,16,17,23,27]} and ^[28] are concern with evasion problems. Problems of finding the value of the game and construction of optimal strategies of the players are considered in ^{[5,7,8,9,11,15,18,22]} and ^[24]. The last category is of special interest in this research.

Among the last category, the problems considered in the papers ^{[1,9,11,18,22]} and ^[24] involve first order differential equations describing the motion of the players. On the other hand, problems involving second order differential equations are contained in ^[5,7] and ^[1]. The works ^[1] and ^[29] in the first category, are concern with problems in which dynamic equations of the players given as a combination of first and second order differential equations.

In another point of view, the references can be grouped into two. Those works with pursuer's and evader's dynamic equations are given as differential equations of the same order in one group. These works include ^{[5,6,7,8,9,10,11,12,13,15,17,18]} and ^{[22,23,24,25,26,27,28,29,30]}. The other group consists of the works ^[1] and ^[29] in which pursuer's and evader's dynamic equations are given as differential equations of different orders.

In ^[7], Ibragimov and Salimi investigated a differential game with infinitely many inertial players with integral constraints on the control functions of the players. Players' motion described by second order differential equations in the Hilbert space ${\ell_2}$. Duration of the game is fixed. Payoff functional is the infimum of the distance between the evader and the pursuers when the game is terminated. The pursuer's goal is to minimize the payoff, and the evader's goal is to maximize it. Under certain condition, the value of the game is found and the optimal strategies of players are constructed. Subsequently, this result was improved and reported in the paper ^[15].

Ibragimov and Kuchkarov in ^[8] examined pursuit-evasion differential game of countably many pursuers and one evader. Players move according to first order equations. Control of the pursuers and evader are subject to integral restrictions. The duration of the game is fixed and the payoff functional is the infimum of the distance between the evader and the pursuers when the game is terminated. The pursuer's goal is to minimize the payoff, and the evader's goal is to maximize it. Optimal strategies of the players are constructed, and value of the game is found.

Inertial Pursuit-evasion game with a finite or countable number of pursuers and evader in Hilbert space ${\ell_2}$ was studied by Ibragimov et al. in ^[13]. Dynamic of the players is described by second order differential equations in a Hilbert space. Control of the pursuers and evader are subject to integral restrictions. The period of the game is fixed. They formulated the value of the game and identified explicitly optimal strategies of the players. They assumed that there is no relation between the control resource of any pursuer and that of the evader.

Salimi, M. and Ferrara, M. in ^[24] studied differential game in which a finite or countable number of pursuers pursue a single evader. Game is described by an infinite system of differential equation of first order in Hilbert space. The control function of the players satisfy the integral constraints. The period of the game is pre-defined. The farness between the evader and the closest pursuer when the game is finished is the payoff function of the game. They introduce the value of the game and identify optimal strategies of the pursuers.

The game of boy and crocodile is studied by Siddiqova et. al. in ^[29]. The boy(evader) moves according to first order differential equation with its control subject to geometric constraint and is not allowed to leave a closed ball in ${\mathbb{R}^{n}}$ during the game. The pursuer(crocodile) moves according to second order differential equation with integral constraint on its control function. Sufficient conditions for completion of pursuit from all initial positions are obtained.

A game problem in which pursuers move according to first order differential equation and evader moves according to second order differential equation is studied in ^[1]. Control function of pursuers and evader are subject to integral and geometric constraints respectively. Theorems each of which provides sufficient conditions for completion of pursuit are stated and proved.

There are several other pursuit-evasion scenarios involving multiple pursuers and one evader studied in the literature, with dynamic equations not necessarily in the aforementioned groups. For instance; scenarios involving attackers, defenders and one evader are considered in ^[3,4], scenarios where the multiple pursuers and evader are constrained within a bounded domain are analyzed in ^{[2,19,21,31,32]}.

In view of the literature presented above and the references therein, there is no study that belongs to the third category and deals with the problem in which dynamic equations of the players are given as combination of first and second order differential equations. That is, problem of finding values of the game and construction of optimal strategies of the players with players having dissimilar laws of motion. Therefore, the need to contribute to the literature in that direction.

In the present paper, we study pursuit-evasion differential game problem in a Hilbert space ${\ell_2}$, in which motion of the pursuers and evader described by first and second order differential equations respectively. Control functions of both the pursuers and evader are subject to integral constraints.

2.   Statement of the problem

In the space $\ell_2,$ we define a ball with center at $a$ and radius $r$ by $B(a, r) = \{x\in {\ell_2}:||x - a||\leq r\},$ and a sphere with center at $a$ and radius $r$ by $S(a, r) = \{x\in {\ell_2}:||x - a|| = r\}.$ Control function of the $i^{th}$ pursuer $P_i,$ is the function $u_i(\cdot)\in {\ell_2},$ with Borel measurable coordinates $u_k: [0, \theta] \rightarrow {\mathbb{R}^1}.$ In a similar way, we define control function $v(\cdot)$ of the evader $E.$

Suppose that motion of the players is described by the equations:

where $x_{i}, x_{i0}, u_{i}, y, y^{0}, y^{1}, v \in {\ell_2}, \ u_{i} = (u_{i1}, u_{i2}, \dots)$ and $v = (v_{1}, v_{2}, \dots)$ are control functions of the $i^{th}$ pursuer $P_{i}$ and evader $E$ respectively. It is required that the control functions $u_i(\cdot)$ and $v(\cdot)$ satisfy the inequalities

where $\rho_i, \ i \in I = \{1, 2, \dots \}$ and $\sigma$ are given positive numbers. The stoppage time of the game is fixed and is denoted by $\theta.$ In what follows in the paper, we shall refer to the control of the $i^{th}$ pursuer $u_i(\cdot)$ satisfying the inequality (2.2) and that of the evader $v(\cdot)$ satisfying the inequality (2.3) as admissible control of the $i^{th}$ pursuer and admissible control of the evader respectively.

Definition 2.1. A function $U_{i}(t, x_{i}, y, v(t))$, $U_{i}: [0, \infty) \times {\ell_2} \times {\ell_2} \times {\ell_2} \rightarrow {\ell_2},$ such that the system

has a unique solution $(x_{i}(\cdot), \ y(\cdot))$ with continuous components $x_{i}(\cdot), \ y(\cdot)$ in ${\ell_2}$, for an arbitrary admissible control $v = v(t), \ 0 \leq t \leq \theta,$ of the evader $E$ is called strategy of the pursuer $P_{i}$. A strategy $U_{i}$ is said to be admissible if each control formed by this strategy is admissible.

Definition 2.2. Strategies $\bar{U}_{i}$ of the pursuers $P_{i}$ are said to be best (optimal) if

where

and $U_{i}$ are admissible strategies of the pursuers $P_{i}$ and $v(\cdot)$ is an admissible control of the evader E.

Definition 2.3. A function $V(t, x_{i}, \dots, x_{m}, \dots, y)$, $V:[0, \infty) \times {\ell_2}\times, \dots, \times {\ell_2}\times, \dots, \times {\ell_2} \rightarrow {\ell_2},$ such that the system

has a unique solution $(x_{1}(\cdot), \dots, x_{m}(\cdot), \dots, y(\cdot))$ with continuous components $x_{1}(\cdot), x_{2}(\cdot), \dots, y(\cdot)$ in ${\ell_2}$, for an arbitrary admissible control $u_{i} = u_{i}(t), \ 0 \leq t \leq \theta,$ of the pursuers $P_{i}$, is called strategy of the evader $E$. A strategy $V$ is said to be admissible if each control formed by this strategy is admissible.

Definition 2.4. Strategy $\bar{V}$ of the evader $E$ is said to be best (optimal) if

where

and $u_{i}(\cdot)$ are admissible control of the pursuers $P_{i}$ and $V$ is an admissible strategy of the evader E.

In the paper ^[9], it is reported that the game has the value $\phi$ if

Research question: What is the game value for the game problem (2.1)- (2.3)?

If the pursuer $P_{i}$ and evader $E$ choose their admissible controls $u_{i}(t) = (u_{i1}(t), u_{i2}(t), \dots)$ and $v(t) = (v_{1}(t), v_{2}(t), \dots)$ respectively, then by (2.1) their corresponding motion is given by

where

It is clear that $x(\cdot)$ and $y(\cdot)$ belongs to the space of continuous functions in the norm of ${\ell_2}$ for $0 \leq t \leq \theta,$ where the component $x_{k}(t)$ and $y_{k}(t)$ are absolutely continuous.

2.1.   Attainability domains

Proposition 2.5. The attainability domain of

(a) the pursuers $P_{i}$ from the initial state $x_{i0}$ at time $t_{0} = 0$ is the ball $H_{P_{i}}(x_{i0}, \rho_{i}\sqrt{\theta})$.

(b) the evader $E$ from the initial state $y_{0}$ at time $t_{0} = 0$ is the ball $H_{E}\left(y_{0}, \sigma\left(\frac{\theta^{3}}{3}\right)^{\frac{1}{2}}\right).$

Proof. For the proof of (a), using (2.11) we have

Let $\bar{x} \in H_{P_{i}}(x_{i0}, \rho_{i}\sqrt{\theta}).$ If the pursuer $P_{i}$ uses the control

Then we have

The prove of (b) is similar, for the evader's control $v(t) = \frac{3(\theta-t)}{\theta^{3}}(\bar{y}-y_{0})$, $0\leq t \leq \theta$.

3.   Auxiliary differential game

In this section, we consider a game with a single pursuer and a single evader by dropping the index $i$ in the game problem (2.1)-(2.3). In view of this, we have the solutions of the dynamic equations of the players (2.1) are given by

where $y_0 = y^{0}+ \theta y^1.$

We define the set

The goal of the pursuer $P$ is to ensure the equality $x(\theta) = y(\theta)$ and that of evader $E$ is the opposite. The problem is to construct a strategy for the pursuer that ensure the equality $x(\theta) = y(\theta)$ for any admissible control of the evader.

Lemma 3.1. If $y(\theta)\in{\Omega}$ then there exist a strategy of the pursuer $P$ such that $x(\theta) = y(\theta)$ in the game (2.1)-(2.3).

Proof. Let the pursuer's strategy be defined by

To show the admissibility of the strategy (3.3), we use the fact that $y(\theta)\in\Omega,$ which means that

From this inequality we have

Therefore,

Using (3.3) and the inequality (3.4) we have

This shows that the strategy (3.3) of the pursuer is admissible.

We now show that the equality $x(\theta) = y(\theta)$ is achievable, if the pursuer uses the strategy (3.3). Indeed,

The proof of lemma (3.1) is complete.

4.   Main result

In this section, we present the main result of the paper. Firstly, we present some important results that are useful in the presentation of the main result.

Lemma 4.1. (see ^[15], Lemma 9) If there exists a nonzero vector $\gamma_{0}$ such that $\langle y_{0}- x_{i0}, \gamma_{0} \rangle \geq 0,$ for all $i \in I$, and $H\left(y_{0}, r\right) \subset\bigcup_{i\in I}H\left(x_{i0}, R_{i}\right)$ then ${H(y_{0}, r)\subset\bigcup_{i\in I_{0}} X_{i}, }$ where

Lemma 4.2. (see ^[9], Assertion 5) Let $\inf_{i\in i}R_{i} = R_{0} > 0$, If there exists a nonzero vector $\gamma_{0}$ such that $\langle y_{0}-x_{i0}, \gamma_{0} \rangle\geq0$ for all $i\in I$ and for any $\varepsilon > 0$ the set $\bigcup_{i\in I}H(x_{i0}, R_{i}-\varepsilon)$ does not contain the ball $H(y_{0}, r)$, then there exist a point $\bar{y}\in S(y_{0}, r)$ such that $\left|\left|\bar{y}- x_{i0}\right|\right|\geq R_{i}$ for all $i\in I$.

We define a positive number $\phi$ by

Theorem 4.1. If there exists a nonzero vector $\gamma_{0}$ such that $\langle y_{0} - x_{i0}, \gamma_{0} \rangle \geq 0,$ for all $i \in I$, then the number $\phi$ defined by (4.1) is the value of the game (2.1)-(2.3).

Proof. To prove this theorem, we first introduce dummy pursuers whose state variables are $z_{i}$, $i\in I$ and motion described by the equations

where the control function $w_{i}(t)$ is such that

The attainability domain of the dummy pursuer $z_{i}$ from the initial state $x_{i0}$ is the ball

Let strategies of the dummy pursuers $z_{i}, i \in I$ be defined as follows:

For $x_{i0} \neq y_{0},$ we set

where $\vartheta$ is the time such that

For $x_{i0} = y_0,$ we set

Now, we define the strategy of the real pursuers by

In accordance with the payoff of the game, the number $\phi$ is the value of the game if the following inequalities hold

In view of this, we prove the inequalities in (4.5). Firstly, we show that left hand side inequality of (4.5). By definition of $\phi$, we have

By lemma (4.1), we have

where

Consequently, the point $y(\theta)\in H_{E}\left(y_{0}, \sigma\left(\frac{\theta^{3}}{3}\right)^{1/2}\right)$ belong to some half space $X_{j}$, $j\in \bar{I}.$

If $x_{j0}\neq y_{0}$ and by the lemma (3.1) for strategy (4.2) of pursuers $z_{j}$ then we have the equality $z_{j}(\theta) = y(\theta)$ holding and

For the other case, if $x_{j0} = y_{0}; \bar{\rho}_{j} = \rho_{j}+\frac{\phi}{\sqrt{\theta}}\geq \sigma\left(\frac{\theta^{3}}{3}\right)^{1/2}$ and the dummy pursuer uses the strategy (4.3) then it is easy to show that $z_{j}(\theta) = y(\theta).$ This means that for each case, the equality $z_{j}(\theta) = y(\theta)$ is achieved.

Now suppose that the real pursuers uses the strategies (4.4), we show that $\left|\left|y(\theta)- x_{j}(\theta)\right|\right|\leq\phi.$ Indeed,

This proves the left hand inequality in (4.5). Which means that the value $\phi$ is guaranteed for the pursuers.

Secondly, we prove the right hand inequality in (4.5). That is, we prove that the value $\phi$ is guaranteed for the evader. If $\phi = 0,$ then the inequality follows for any admissible control of the evader. Suppose that $\phi \neq 0$ and if $\epsilon$ be a non zero positive number such that $\epsilon < \phi$ then by definition of $\phi$ the ball $H_{E}\left(y_{0}, \sigma(\theta^{3}/3)^{1/2}\right)$ is not contained in the set

Therefore, the existence of a point $\bar{y}\in S\left(y_{0}, \sigma(\theta^{3}/3)^{1/2}\right)$, such that $\left|\left|\bar{y}- x_{i0}\right|\right|\geq \rho_{i}\sqrt{\theta}+\phi, i \in I,$ is guaranteed by the lemma (4.1). On another note, it is easy to show that

Consequently, we have

This means that if the evader can be at point $\bar{y}$ at time $\theta,$ then the right hand side of (4.5) is proved. Indeed, evader's control exists that takes it to the point $\bar{y}$ for the time $\theta,$ since the point is contained in the attainability domain of the evader. In particular, let the evader's control be defined by

Then we have

Therefore, the value $\phi$ is guaranteed for the evader. This proves the right hand inequality of (4.5). The proof of the theorem is complete.

5.   Example

Consider the game problem (2.1)-(2.3) and let $\rho_i = 1;\ \sigma = \frac{1}{\sqrt{3}}; \ \theta = 9.$ We also assume the following initial positions of each of the $i^{th}$ pursuer and evader:

where the number $\sqrt{19}$ is the $i^{th}$ coordinate of the initial position of the $i^{th}$ pursuer. Observe that $\rho_i\sqrt{\theta} = 3$ and $\sigma\left(\frac{\theta^3}{3}\right)^{1/2} = 9$.

The goal is to show the value of the game (2.1)-(2.3) is given by $\phi = 7.$ To show this, it is sufficient to show that

1. the following inclusion holds for any $\epsilon > 0:$ $H_E(\mathbf{0}, 9) \subset \bigcup_{i \in I}H_{P_i}(x_{0i}, 10 + \epsilon);$

2. the ball $H_E(\mathbf{0}, 9)$ is not contained in the set $\bigcup_{i \in I}H_{P_i}(x_{0i}, 10).$

To show (1), we let $y^* = (y^*_1, y^*_2, \dots) \in H_E(\mathbf{0}, 9).$ Therefore, we must have $\sum_{i \in I}(y^*_i)^2 \leq 81.$ Then the vector $y^*$ has a nonnegative coordinate or all the coordinates of the vector are negative.

We consider the first case in which the vector $y^*$ has a nonnegative coordinate $y^*_k.$ Then we have

This means that $y^* \in H_{P_k}(x_{0k}, 10 + \epsilon).$ For the second case, since $\sum_{i \in I}(y^*_i)^2 < \infty,$ then $\lim_{k \rightarrow \infty}y^*_k = 0.$ Therefore, for the index $k,$ we have

This also means that $y^* \in H_{P_k}(x_{0k}, 10 + \epsilon).$

To show (2), it is obvious that for any index $i,$ that

This means that any vector $y^* \in S_E(\mathbf{0}, 9)$ with negatives coordinates does not belong to $\bigcup_{i \in I}H_{P_i}(x_{0i}, 10).$ In view of the this and according to theorem 4.1, the game (2.1)-(2.3) has the value

6.   Conclusion

The pursuit-evasion differential game problem of countably many pursuers and one evader has been studied in the Hilbert space ${\ell_2}$. Control functions of the pursuers and the evader are subject to integral constraints. The value of the game is found and optimal strategies of the players are constructed. The problem considered in this work is uncommon in the literature but represent many real problems. It is a representation of pursuit problems involving objects with different dynamics and possibly information about the acceleration of one of the objects is not available. For further research, the evasion problem concerning the problem considered in this paper can be investigated.

Acknowledgments

The second author was financially supported by Rajamangala University of Technology Phra Nakhon (RMUTP) Research Scholarship. We also acknowledged the valuable comments, suggestions and observations of the reviewers of the draft article.

Conflict of interest

The authors declare that they have no competing interests in this paper.