An Analytic and Numerical Investigation of a Differential Game

Abstract

In this paper we present an appropriate singular, zero-sum, linear-quadratic differential game. One of the main features of this game is that the weight matrix of the minimizer’s control cost in the cost functional is singular. Due to this singularity, the game cannot be solved either by applying the Isaacs MinMax principle, or the Bellman–Isaacs equation approach. As an application, we introduced an interception differential game with an appropriate regularized cost functional and developed an appropriate dual representation. By developing the variational derivatives of this regularized cost functional, we apply Popov’s approximation method and show how the numerical results coincide with the dual representation.

1. Introduction

In this paper, we present a zero-sum differential game with linear dynamics and a quadratic cost functional. Such games appear in many areas of control theory, for example, robust controllability [1], pursuit-evasion [2,3,4,5], robust tracking [6] and robust investment [7], to name but a few.

The singularity of such a game is caused by the weight matrix of the minimizer’s control cost, meaning that problem of minimization its variational Hamiltonian with respect to the minimizer control has either infinitely many solutions or no solutions. This makes the game challenging, since it can not be solved by some well-known approaches, such as the Isaacs min-max principle [8] and the Bellman–Isaacs equation [8,9,10,11].

Known techniques in the literature involve high order optimality conditions, but their practical usage is quite limited and not general enough [2,5]. Regularization approaches with additional assumption have been studied by several researchers, such as [12]. Other related results include [13,14,15].

In [16] the differential game is tackled by introducing a cost functional containing the minimizer’s control cost. A regularization approach is then considered, yielding an auxiliary differential game with partial cheap control of the minimizer. While differential games with total cheap control of at least one of the players has been studied enough already—see, e.g., [1,6,17,18,19,20]—partial cheap control of at least one of the players has been studied by only a few [16].

In the recent work of the authors [21], a saddle-point reformulation of the zero-sum singular differential game was studied, and two gradient methods were presented and analyzed. This work considering a slightly more general game than [16] and a pursuit–evasion game illustrates the applicability of the numerical methods.

Following the above and as a continuing work of [21], the objectives of this work are as follows:

• Introduce an appropriate cost functional that includes in addition to relative lateral velocity, lateral relative separation.
• For the above functional, develop a dual representation and present its variational derivatives.
• Present numerical calculations of the dual representation that gives the interception.
• Validate the above via Popov’s approximation method.

The paper is organized as follows. We first recall some basic definitions and results in Section 2. In Section 3, an interception game is considered. In Section 4, the dual representation of the game’s cost functional is derived, which follows by numerical validation of the double projection methods for finding saddle points in Section 5. Final conclusions are given in Section 6.

2. Preliminaries

A standard linear zero-sum differential game consists of constraint

$${\displaystyle \frac{dz\left(t\right)}{dt}}=Az\left(t\right)+Bu\left(t\right)+Cv\left(t\right),z\left(0\right)=z_0,t\in [0,t_f],$$

(1)

and a cost functional

$$J(u,v)\triangleq z^T\left(t_f\right)Fz\left(t_f\right)+\underset{0}{\overset{t_f}{\int }}\left[z^T\left(t\right)Dz\left(t\right)+u^T\left(t\right)G_{u}u\left(t\right)-v^T\left(t\right)G_{v}v\left(t\right)\right]dt,$$

(2)

to be minimized by u and maximized by v. The involved parameters in (1) and (2) are: $t_f$, a given final time moment; T, the transpose; ${\mathbb{E}}^n$, an n dimensional Euclidean space; $z\left(t\right)\in {\mathbb{E}}^n$, a state vector; $u\left(t\right)\in {\mathbb{E}}^r$; ($r\le n$); $v\left(t\right)\in {\mathbb{E}}^s$, the players’ controls and quadratic integrable; A, B and C are the given matrices, where B is fully ranked. Moreover, $z_0\in {\mathbb{E}}^n$ is a given initial vector; F, D and $G_u$ are given positive semi-definite symmetric matrices; and $G_v$ is a positive, definite symmetric matrix.

Next we recall several definitions.

Definition 1.

The differential control game (1) and (2) is called singular if all or some of the coordinates of the minimizer’s control are singular, that is, $G_u=0$ or

$$G_u=\mathrm{diag}\left(g_{u_1},\dots ,g_{u_q},\underset{r-q}{\underbrace{0,\dots ,0}}\right),g_{u_j}>0,j=1,\dots ,q,$$

(3)

Definition 2.

The control game (1) and (2) are called regular if the cost functional (2) for a small enough $\epsilon >0$ has one of the following structures:

$$J^{\epsilon }(u,v)=z{\left(t_f\right)}^{T}Fz\left(t_f\right)+\underset{0}{\overset{t_f}{\int }}[z^T\left(t\right)Dz\left(t\right)+{\epsilon }^2{u}^T\left(t\right)u\left(t\right)-v^T\left(t\right)G_{v}v\left(t\right)]dt.$$

(4)

Or

$$J^{\epsilon }(u,v)=z^T\left(t_f\right)Fz\left(t_f\right)+\underset{0}{\overset{t_f}{\int }}\left(z^T\left(t\right)Dz\left(t\right)+u^T\left(t\right)\left(G_u+\mathcal{E}\right)u\left(t\right)-v^T\left(t\right)G_{v}v\left(t\right)\right)dt,$$

(5)

where

$$G_u+\mathcal{E}=\mathrm{diag}\left(g_{u_1},\dots ,g_{u_q},\underset{r-q}{\underbrace{{\epsilon }^2,\dots ,{\epsilon }^2}}\right).$$

(6)

Such regular cheap/partial cheap control games were analyzed in [12,16,22,23] using the study of the Riccati matrix differential equation for a finite-horizon game, and the Riccati matrix algebraic equation fora n infinite-horizon game.

In this work we study an interception game, which is a special regular differential game, in order to minimize with respect to u and maximize with respect to v the associated regularized cost functional. This then suggested exploring the equivalent saddle-point reformulation.

Consider the Hilbert space $L_2[0,t_f]$ and let $Q\subseteq L_2[0,t_f]$ and $R\subseteq L_2[0,t_f]$ be two closed, convex and bounded sets of admissible controls. Then, solving (1)–(4) is equivalent to solving the following min-max problem.

$$\underset{u\in Q}{min}\underset{v\in R}{max}{J}^{\epsilon }(u,v)$$

(7)

where $J^{\epsilon }$ is continuous, convex–concave (convex in u and concave in v) and differentiable. See [24] for further details.

A saddle-point reformulation of the min-max problem (7) is formulated as finding a point $\left(u^{*},v^{*}\right)\in Q\times R$ such that

$$J^{\epsilon }(u^{*},v)\le J^{\epsilon }(u^{*},v^{*})\le J^{\epsilon }(u,v^{*})$$

(8)

for all $v\in R$ and $u\in Q$.

Another known relationship with the above assumptions on $J^{\epsilon }$ is the following variational inequality reformulation. The saddle-point problem (8) is equivalent to finding a point $\left(u^{*},v^{*}\right)\in Q\times R$ such that

$$〈\left(\genfrac{}{}{0pt}{}{\frac{\delta J^{\epsilon }}{\delta u}(u^{*},v^{*})}{-\frac{\delta J^{\epsilon }}{\delta v}(u^{*},v^{*})}\right),\left(\genfrac{}{}{0pt}{}{u}{v}\right)-\left(\genfrac{}{}{0pt}{}{u^{*}}{v^{*}}\right)〉\ge 0\mathrm{for}\mathrm{all}(u,v)\in Q\times R$$

where $\langle ·,·\rangle$ is an appropriate inner product and $\delta J^{\epsilon }/\left(\delta u\right)$ and $\delta J^{\epsilon }/\left(\delta v\right)$ are the variational derivatives of the functional $J^{\epsilon }$, as will be explained later (can be thought of as partial derivatives in the case of real functions).

Saddle-point problems (as well as variational inequalities) stand at the core of many real-world applications in convex programming, game theory and many more instances; see, e.g., Rockafellar [25]. In [21] we considered two gradient methods for solving saddle-point problems, the Arrow–Hurwicz–Uzawa algorithm [26] and Korpelevich’s extragradient method [27]; see also [28,29,30,31,32] and the many references therein.

These methods use gradients in each of their update rules. Thus we recall the variational/functional derivative definition next (see, for example, [33]).

Definition 3.

Consider an integral functional $J\left(x\right(t\left)\right)$ of an argument $x\left(t\right)$. The variational/functional derivative of $J\left(x\right(t\left)\right)$ with respect to $x\left(t\right)$, $\frac{\delta J}{\delta x}:[0,T]\mapsto {\mathbb{R}}^n$ is defined as

$$\delta J\left(x\left(t\right)\right)h\left(t\right)={\int }_0^{t_f}\frac{\delta J}{\delta x\left(t\right)}h\left(t\right)dt.$$

(9)

Recall that for a function $f:{\mathbb{R}}^n\mapsto \mathbb{R}$, the gradient $\nabla f$ is defined by

$$\frac{d}{dϵ}f(x+ϵh)\left|{}_{{}_{ϵ=0}}\right.=\nabla f\left(x\right)·h$$

Thus the variational derivative works similarly as such; that is,

$$\frac{d}{dϵ}J(x+ϵh)\left|{}_{{}_{ϵ=0}}\right.=\delta J\left(x\right)·h,$$

and with (9), we get

$$\frac{d}{dϵ}J(x+ϵh)\left|{}_{{}_{ϵ=0}}\right.={\int }_0^{t_f}\frac{\delta J}{\delta x}h\left(t\right)dt.$$

(10)

Remark 1.

In a more general setting, where the zero-sum differential cost functional is not differentiable, subdifferentials/subgradients are needed; see [24,25,34] and references therein.

Now we recall the Arrow–Hurwicz–Uzawa method [26] and Korpelevich’s extragradient method [27], which we applied in our previous paper [21]. For simplicity we present the algorithms for solving variational inequalities, and clearly the translation to min-max and saddle-point problems can be easily derived.

Let ${\mathcal{H}}_1,{\mathcal{H}}_2$ be two real Hilbert spaces and a bifunction $F:{\mathcal{H}}_1\times {\mathcal{H}}_2\to \mathbb{R}$ with partial derivatives ${\nabla }_{u}F$ and ${\nabla }_{v}F$. Choose an arbitrary starting point $(u_0,v_0)\in Q\times R$ and step-size $\alpha >0$. Given the current iterate $(u_k,v_k)$, the Arrow–Hurwicz–Uzawa update rule is formulated as follows:

$$\begin{array}{c}\hfill \left\{\begin{array}{cc}{u}_{k+1}=\hfill & {\mathcal{P}}_Q\left(u_k-\alpha {\nabla }_{u}F(u_k,v_k)\right)\hfill \\ v_{k+1}=\hfill & {\mathcal{P}}_R\left(v_k+\alpha {\nabla }_{v}F(u_k,v_k)\right)\hfill \end{array}\right.\end{array}$$

(11)

where ${\mathcal{P}}_Q$ and ${\mathcal{P}}_R$ are the orthogonal projection operators for the sets Q and R, respectively.

A related modification with weaker convergence assumptions is Korpelevich’s method, in which additional mid-points computations are done, corresponding to gradients, and thus its known name is the extragradient method:

$$\begin{array}{c}\hfill \left\{\begin{array}{cc}\overline{u_k}=\hfill & {\mathcal{P}}_Q\left(u_k-\alpha {\nabla }_{u}F(u_k,v_k)\right)\hfill \\ \overline{v_k}=\hfill & {\mathcal{P}}_R\left(v_k+\alpha {\nabla }_{v}F(u_k,v_k)\right)\hfill \\ u_{k+1}=\hfill & {\mathcal{P}}_Q\left(u_k-\alpha {\nabla }_{u}F(\overline{u_k},\overline{v_k})\right)\hfill \\ v_{k+1}=\hfill & {\mathcal{P}}_R\left(v_k+\alpha {\nabla }_{v}F(\overline{u_k},\overline{v_k})\right)\hfill \end{array}\right.\end{array}$$

(12)

Although convergence of the extragradient method is guaranteed under weaker assumptions than the Arrow–Hurwicz–Uzawa method, there is still the need to calculate two evaluations of $\nabla F=({\nabla }_{u}F,{\nabla }_{v}F)$ and two projections onto Q and R. One step in the direction of simplifying the extragradient method with respect to the double projections is Censor et al.’s [30,31] subgradient extragradient method. In this method, the second orthogonal projection onto R is replaced by an easy computed projection onto some constructible set $T_k$.

$$\begin{array}{c}\hfill \left\{\begin{array}{cc}\overline{u_k}=\hfill & {\mathcal{P}}_Q\left(u_k-\alpha {\nabla }_{u}F(u_k,v_k)\right)\hfill \\ \overline{v_k}=\hfill & {\mathcal{P}}_R\left(v_k+\alpha {\nabla }_{v}F(u_k,v_k)\right)\hfill \\ u_{k+1}=\hfill & {\mathcal{P}}_{T_k}\left(u_k-\alpha {\nabla }_{u}F(\overline{u_k},\overline{v_k})\right)\hfill \\ v_{k+1}=\hfill & {\mathcal{P}}_{T_k}\left(v_k+\alpha {\nabla }_{v}F(\overline{u_k},\overline{v_k})\right)\hfill \end{array}\right.\end{array}$$

(13)

For avoiding the extra evaluations of $\nabla F$ per each iteration, Popov [35] proposed the following modification introducing the so-called “leading” point:

$$\left\{\begin{array}{cc}\overline{u_k}=\hfill & {\mathcal{P}}_Q\left(u_k-\alpha {\nabla }_{u}F(u_k,v_k)\right)\hfill \\ \overline{v_k}=\hfill & {\mathcal{P}}_R\left(v_k+\alpha {\nabla }_{v}F(u_k,v_k)\right)\hfill \\ u_{k+1}=\hfill & {\mathcal{P}}_Q\left(\overline{u_k}-\alpha {\nabla }_{u}F(u_k,v_k)\right)\hfill \\ v_{k+1}=\hfill & {\mathcal{P}}_R\left(\overline{v_k}+\alpha {\nabla }_{v}F(u_k,v_k)\right)\hfill \end{array}\right.$$

A standard assumption, which we also use, for the convergence of the above methods, is the so-called roundedness of the derivatives, which means that the functional derivatives of $J^{\epsilon }(u_k,v_k)$ and $J^{\epsilon }(u_k,v_k)$ with respect to u and v, respectively, are uniformly bounded; i.e., there is a constant $M>0$ such that

$$\left|\left|\frac{\delta J^{\epsilon }(u_k,v_k)}{\delta u\left(t\right)}\right|\right|\le M,\left|\left|\frac{\delta J^{\epsilon }(u_k,v_k)}{\delta v\left(t\right)}\right|\right|\le M,$$

(14)

for all $k\ge 0$.

Since the introduction of the above methods, many modifications and extensions have been offered using various techniques—inertial, hybrid, viscosity and more; see, e.g., [36,37] and the references therein.

3. Interception Game

In this section we consider a particular singular problem (1)–(4), namely, $n=2$, $r=1$, $s=1$. The matrices of coefficients in (1) and (2) are

$$A=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right),D=\left(\begin{array}{cc}0& 0\\ 0& 0\end{array}\right),F=\left(\begin{array}{cc}{f}_1& 0\\ 0& f_2\end{array}\right)$$

(15)

$$B^T=(0,1),C^T=(0,1),G_v=g$$

(16)

with the scalars $g,$$f_1,f_2>0$.

The initial position $z_0$ is

$$z_0^T\left(0\right)=(0,1).$$

(17)

The system (1) subject to the data (15), (16) has the following form:

$$\left\{\begin{array}{cc}\frac{d{z}_1\left(t\right)}{dt}\hfill & =z_2\left(t\right)\hfill \\ \frac{d{z}_2\left(t\right)}{dt}\hfill & =u\left(t\right)+v\left(t\right)\hfill \end{array}\right.$$

(18)

The solution of (18) with initial position (17) has the following integral form:

$$z\left(t\right)=\left(z_1{\left(t\right)}^T\mid z_2{\left(t\right)}^T\right)=M\left(t\right)M{\left(0\right)}^{-1}{z}_0\left(0\right)+{\int }_0^{t}M\left(t\right)M{\left(s\right)}^{-1}f\left(s\right)ds,$$

(19)

where

$$M\left(t\right)=\left(\begin{array}{cc}1& t\\ 0& 1\end{array}\right)$$

(20)

is a fundamental matrix solution of the corresponding homogeneous system

$$\left\{\begin{array}{cc}\frac{d{z}_1\left(t\right)}{dt}\hfill & =z_2\left(t\right)\hfill \\ \frac{d{z}_2\left(t\right)}{dt}\hfill & =0\hfill \end{array}\right.$$

(21)

and

$$f\left(s\right)=\left(\begin{array}{c}0\\ u\left(s\right)+v\left(s\right)\end{array}\right).$$

(22)

Thus, the analytical solution (after some technical calculations in (19) with (20) and (22)) can be written as

$$\begin{array}{ccc}\hfill z_1\left(t\right)& =& t+{\int }_0^t\left(t-s\right)(u\left(s\right)+v\left(s\right))ds\hfill \end{array}$$

(23)

$$\begin{array}{ccc}\hfill z_2\left(t\right)& =& 1+{\int }_0^t(u\left(s\right)+v\left(s\right))ds\hfill \end{array}$$

(24)

The system (18), with (17) is a linearized kinematic model of a planar engagement between two vehicles—an interceptor (pursuer) and a target (evader) where both vehicles are directly controlled by their lateral accelerations $u\left(t\right)=-a_p\left(t\right)$ and $v\left(t\right)=a_e\left(t\right)$, respectively. The coordinates of the state vector $z\left(t\right)=(z_1\left(t\right),z_2\left(t\right))$ are the relative lateral separation and the relative lateral velocity of the vehicles. The basic schematic view of the planar engagement geometry is shown in Figure 1, where:

• The x-axis of the coordinate system is aligned with the initial line of sight;
• The points $(x_p,y_p)$, $(x_e,y_e)$ are the current coordinates;
• The origin is collocated with the initial pursuer position;
• $V_p$ and $V_e$ are the velocities;
• $a_p$ and $a_e$ are the lateral accelerations;
• ${\phi }_p$ and ${\phi }_e$ are the respective aspect angles between velocities vectors and reference line of sight;
• $y=y_e-y_p$ is the relative lateral separation normal to the initial sight of line;
• r is the current range between the vehicles;
• The line-of-sight angle $\lambda$ is the angle between the current and initial lines of sight.

More details of such an engagement can be found, for instance, in [38,39].

The behavior of each player in this singular game is evaluated by the following regularized cost functional.

$$J^{\epsilon }(u,v)=f_1{z}_1^2\left(t_f\right)+f_2{z}_2^2\left(t_f\right)+{\int }_0^{t_f}\left({\epsilon }^2{u}^2\left(t\right)-g{v}^2\left(t\right)\right)dt.$$

(25)

The cost functional (25) has to be minimized by the pursuer $u\left(t\right)$ and maximized by the evader $v\left(t\right)$.

The game, consisting of the dynamics (1), with the data (15) and (16), initial condition (17) and cost functional (25) is called the interception differential game.

By combining the above data and definitions and substituting in the functional (25) we obtain:

$$\begin{array}{ccc}\hfill J^{\epsilon }(u,v)& =& f_1\left(t_f+{\int }_0^{t_f}\left(t_f-t\right)(u\left(t\right)+v\left(t\right))dt\right)\hfill \\ & & +f_2{\left(1+{\int }_0^{t_f}(u\left(t\right)+v\left(t\right))dt\right)}^2+{\int }_0^{t_f}\left({\epsilon }^2{u}^2\left(t\right)-g{v}^2\left(t\right)\right)dt.\hfill \end{array}$$

(26)

For the numerical validation of the saddle-point approximation of this functional, we next develop the appropriate variational derivatives.

Theorem 1.

The variational derivatives of (26) are given by:

$$\begin{array}{ccc}\hfill \frac{\delta J^{\epsilon }}{\delta u}& =& 2f_1(t_f-t)\left(t_f+{\int }_0^{t_f}(t_f-t)(u\left(t\right)+v\left(t\right))dt\right)\hfill \\ & & +2f_2\left(1+{\int }_0^{t_f}(u\left(t\right)+v\left(t\right))dt\right)+2{\epsilon }^{2}u\left(t\right),\hfill \end{array}$$

(27)

and

$$\begin{array}{ccc}\hfill \frac{\delta J^{\epsilon }}{\delta v}& =& 2f_1(t_f-t)\left(t_f+{\int }_0^{t_f}(t_f-t)(u\left(t\right)+v\left(t\right))dt\right)\hfill \\ & & +2f_2\left(1+{\int }_0^{t_f}(u\left(t\right)+v\left(t\right))dt\right)-2gv\left(t\right).\hfill \end{array}$$

(28)

Proof. 

Our functional $J^{\epsilon }$ has two dependent variables of t (u and v), and we have to find the variational derivative with respect to u and v. In the view of above arguments, we have

$${\int }_0^{t_f}\frac{\delta J^{\epsilon }}{\delta u}{h}_1\left(t\right)dt=\delta J^{\epsilon }\left(u\right)·h_1=\frac{\partial }{\partial {ϵ}_1}{J}^{\epsilon }(u+{ϵ}_1{h}_1,v+{ϵ}_2{h}_2)\left|{}_{({ϵ}_1,{ϵ}_2)=(0,0)}\right.,$$

(29)

and

$${\int }_0^{t_f}\frac{\delta J^{\epsilon }}{\delta v}{h}_2\left(t\right)dt=\delta J^{\epsilon }\left(v\right)·h_2=\frac{\partial }{\partial {ϵ}_2}{J}^{\epsilon }(u+{ϵ}_1{h}_1,v+{ϵ}_2{h}_2)\left|{}_{{}_{({ϵ}_1,{ϵ}_2)=(0,0)}}\right..$$

(30)

Equations (29) and (30) will render the functional derivatives $\frac{\delta J^{\epsilon }}{\delta u}$ and $\frac{\delta J^{\epsilon }}{\delta v}$, respectively. Therefore, we start with the (29):

$$\begin{array}{ccc}& & \frac{\partial }{\partial {ϵ}_1}{J}^{\epsilon }(u+{ϵ}_1{h}_1,v+{ϵ}_2{h}_2)\left|{}_{{}_{({ϵ}_1,{ϵ}_2)=(0,0)}}\right.\hfill \\ & =& \frac{\partial }{\partial {ϵ}_1}\left[f_1{\left(t_f+{\int }_0^{t_f}(t_f-t)(u\left(t\right)+{ϵ}_1{h}_1\left(t\right)+v\left(t\right)+{ϵ}_2{h}_2\left(t\right))dt\right)}^2\right]\left|{}_{{}_{({ϵ}_1,{ϵ}_2)=(0,0)}}\right.\hfill \\ & & +\frac{\partial }{\partial {ϵ}_1}\left[f_2{\left(1+{\int }_0^{t_f}(u\left(t\right)+{ϵ}_1{h}_1\left(t\right)+v\left(t\right)+{ϵ}_2{h}_2\left(t\right))dt\right)}^2\right]\left|{}_{{}_{({ϵ}_1,{ϵ}_2)=(0,0)}}\right.\hfill \\ & & +\frac{\partial }{\partial {ϵ}_1}\left[{\int }_0^{t_f}({\epsilon }^2{(u\left(t\right)+{ϵ}_1{h}_1\left(t\right))}^2-g{(v\left(t\right)+{ϵ}_2{h}_2\left(t\right))}^2)dt\right]\left|{}_{{}_{({ϵ}_1,{ϵ}_2)=(0,0)}}\right.\hfill \\ & =& 2f_1\left(t_f+{\int }_0^{t_f}(t_f-t)(u\left(t\right)+{ϵ}_1{h}_1\left(t\right)+v\left(t\right)+{ϵ}_2{h}_2\left(t\right))dt\right){\int }_0^{t_f}(t_f-t)h_1\left(t\right)dt\left|{}_{{}_{({ϵ}_1,{ϵ}_2)=(0,0)}}\right.\hfill \\ & & +2f_2\left(1+{\int }_0^{t_f}(u\left(t\right)+{ϵ}_1{h}_1\left(t\right)+v\left(t\right)+{ϵ}_2{h}_2\left(t\right))dt\right){\int }_0^{t_f}{h}_1\left(t\right)dt\left|{}_{{}_{({ϵ}_1,{ϵ}_2)=(0,0)}}\right.\hfill \\ & & +{\int }_0^{t_f}2{\epsilon }^2(u\left(t\right)+{ϵ}_1{h}_1\left(t\right))h_1\left(t\right))dt\left|{}_{{}_{({ϵ}_1,{ϵ}_2)=(0,0)}}\right.\hfill \\ & =& 2f_1\left(t_f+{\int }_0^{t_f}(t_f-t)(u\left(t\right)+v\left(t\right))dt\right){\int }_0^{t_f}(t_f-t)h_1\left(t\right)dt\hfill \\ & & +2f_2\left(1+{\int }_0^{t_f}(u\left(t\right)+v\left(t\right))dt\right){\int }_0^{t_f}{h}_1\left(t\right)dt+{\int }_0^{t_f}2{\epsilon }^{2}u\left(t\right)h_1\left(t\right)dt\hfill \\ & =& 2f_1\left(t_f{\int }_0^{t_f}(t_f-t)h_1\left(t\right)dt+{\int }_0^{t_f}(t_f-t)(u\left(t\right)+v\left(t\right))dt{\int }_0^{t_f}(t_f-t)h_1\left(t\right)dt\right)\hfill \\ & & +2f_2{\int }_0^{t_f}\left(1+{\int }_0^{t_f}(u\left(t\right)+v\left(t\right))dt\right)h_1\left(t\right)dt+{\int }_0^{t_f}2{\epsilon }^{2}u\left(t\right)h_1\left(t\right)dt\hfill \\ & =& 2f_1\left(t_f{\int }_0^{t_f}(t_f-t)h_1\left(t\right)dt+{\int }_0^{t_f}(t_f-t)\left\{{\int }_0^{t_f}(t_f-t)(u\left(t\right)+v\left(t\right))dt\right\}{h}_1\left(t\right)dt\right)\hfill \\ & & +2f_2{\int }_0^{t_f}\left(1+{\int }_0^{t_f}(u\left(t\right)+v\left(t\right))dt\right)h_1\left(t\right)dt+{\int }_0^{t_f}2{\epsilon }^{2}u\left(t\right)h_1\left(t\right)dt.\hfill \end{array}$$

The above expression together with (10) yield

$${\int }_0^{t_f}\frac{\delta J^{\epsilon }}{\delta u}{h}_1\left(t\right)dt={\int }_0^{t_f}[2f_1{t}_f(t_f-t)+2f_1(T-t)\left\{{\int }_0^{t_f}(t_f-t)(u\left(t\right)+v\left(t\right))dt\right\}$$

$$+2f_2\left(1+{\int }_0^{t_f}(u\left(t\right)+v\left(t\right))dt\right)+2{\epsilon }^{2}u\left(t\right)]h_1\left(t\right)dt.$$

It follows that the variational derivative of $J^{\epsilon }$ with respect to u is given by

$$\begin{array}{ccc}\hfill \frac{\delta J^{\epsilon }}{\delta u}& =& 2f_1{t}_f(t_f-t)+2f_1(t_f-t)\left\{{\int }_0^{t_f}(t_f-t)(u\left(t\right)+v\left(t\right))dt\right\}\hfill \\ & & +2f_2\left(1+{\int }_0^{t_f}(u\left(t\right)+v\left(t\right))dt\right)+2{\epsilon }^{2}u\left(t\right).\hfill \end{array}$$

with some simplifications, we obtain (27), and in a similar way we derive (28); and the proof is complete. □

4. Duality Representation

We consider the functional (26) with the constants $f_1,$$f_2,$$g>0$ and a small parameter $\epsilon >0$, and present its variational derivatives.

Theorem 2.

The dual representation of the functional (26) is given by:

$$u^{*}\left(t\right)=-{\displaystyle \frac{1}{2{\epsilon }^2}}{h}^T\left(t\right){\ell }^{*},$$

(31)

$$v^{*}\left(t\right)={\displaystyle \frac{1}{2g}}{h}^T\left(t\right){\ell }^{*},$$

(32)

where

$${\ell }^{*}=arg\underset{\ell \in {\mathbb{E}}^2}{max}\left[{\ell }^{T}d-\frac{1}{4}{\ell }^{T}G\ell \right].$$

(33)

or equivalently in scalar form

$${\ell }^{*}=arg\underset{\ell \in {\mathbb{E}}^2}{max}\left[{\ell }_1{t}_f+{\ell }_2-\frac{1}{4}\left(\frac{{\ell }_1^2}{f1}+\frac{{\ell }_2^2}{f_2}\right)-\frac{1}{4}{t}_f\left({\displaystyle \frac{1}{{\epsilon }^2}}-{\displaystyle \frac{1}{g}}\right)\left({\ell }_1^2{\displaystyle \frac{t_f^3}{3}}+{\ell }_1{\ell }_2{t}_f+{\ell }_2^2\right)\right]$$

(34)

and all the coefficients will be presented in the proof itself.

Proof. 

In the lines of [40], let us calculate the program maxi-min:

$$\rho =\underset{v(·)\in L_2[0,t_f]}{max}\underset{u(·)\in L_2[0,t_f]}{min}{J}^{\epsilon }$$

(35)

Using [41]

$$z^{T}Rz=\underset{\ell \in \mathbb{E}{}^n}{max}\left({\ell }^{T}z-{\displaystyle \frac{1}{4}}{\ell }^T{R}^{-1}\ell \right),$$

(36)

where R is symmetric positive definite matrix. Note that

$$f_1{z}_1^2\left(t_f\right)+f_2{z}_2^2\left(t_f\right)=z^T\left(t_f\right)Fz\left(t_f\right),$$

(37)

in (25) where $z={(z_1,z_2)}^T$,

$$F=\left[\begin{array}{cc}{f}_1& 0\\ 0& f_2\end{array}\right].$$

(38)

Then,

$$J^{\epsilon }=\underset{\ell \in {\mathbb{E}}^2}{max}\phi (\ell ,u(·),v(·)),$$

(39)

where

$$\phi (\ell ,u(·),v(·))={\ell }^{T}z\left(t_f\right)-{\displaystyle \frac{1}{4}}{\ell }^T{F}^{-1}\ell +\underset{0}{\overset{t_f}{\int }}\left({\epsilon }^2{u}^2\left(t\right)-g{v}^2\left(t\right)\right)dt,$$

(40)

$$F^{-1}=\left[\begin{array}{cc}{\displaystyle \frac{1}{f_1}}& 0\\ 0& {\displaystyle \frac{1}{f_2}}\end{array}\right].$$

(41)

Consequently,

$$\rho =\underset{v(·)}{max}\underset{u(·)}{min}\underset{\ell \in {\mathbb{E}}^2}{max}\phi (\ell ,u(·),v(·)).$$

(42)

Then (40) becomes:

$$\phi (\ell ,u(·),v(·))={\ell }_1\left(t_f+\underset{0}{\overset{t_f}{\int }}\left(t_f-t\right)(u\left(t\right)+v\left(t\right))dt\right)+{\ell }_2\left(1+\underset{0}{\overset{t_f}{\int }}(u\left(t\right)+v\left(t\right))dt\right)$$

$$-{\displaystyle \frac{1}{4}}\left({\displaystyle \frac{1}{f_1}}{\ell }_1^2+{\displaystyle \frac{1}{f_2}}{\ell }_2^2\right)+\underset{0}{\overset{t_f}{\int }}\left({\epsilon }^2{u}^2\left(t\right)-g{v}^2\left(t\right)\right)dt=$$

$${\ell }_{1}T+{\ell }_2-{\displaystyle \frac{1}{4}}\left({\displaystyle \frac{1}{f_1}}{\ell }_1^2+{\displaystyle \frac{1}{f_2}}{\ell }_2^2\right)+{\phi }_u(\ell ,u(·))+{\phi }_v(\ell ,v(·)),$$

(43)

where

$${\phi }_u(\ell ,u(·))\triangleq \underset{0}{\overset{t_f}{\int }}\left[\left({\ell }_1(t_f-t)+{\ell }_2\right)u\left(t\right)+{\epsilon }^2{u}^2\left(t\right)\right]dt,$$

(44)

$${\phi }_v(\ell ,v(·))\triangleq \underset{0}{\overset{t_f}{\int }}\left[\left({\ell }_1(t_f-t)+{\ell }_2\right)v\left(t\right)-g{v}^2\left(t\right)\right]dt,$$

(45)

In (42), the operations of maximum over $\ell \in {\mathbb{E}}^2$ and minimum over $u(·)\in L_2[0,t_f]$ commute. Therefore,

$$\rho =\underset{\ell \in {\mathbb{E}}^2}{max}\underset{v(·)}{max}\underset{u(·)}{min}\phi (\ell ,u(·),v(·))=$$

$$\underset{{\ell }_1,{\ell }_2\in \mathbb{E}}{max}\left[{\ell }_1{t}_f+{\ell }_2-{\displaystyle \frac{1}{4}}\left({\displaystyle \frac{1}{f_1}}{\ell }_1^2+{\displaystyle \frac{1}{f_2}}{\ell }_2^2\right)+\underset{u(·)}{min}{\phi }_u(\ell ,u(·))+\underset{v(·)}{max}{\phi }_v(\ell ,v(·))\right].$$

(46)

The inner minimizer and maximizer in (46) are

$$u^{*}(t,\ell )=-{\displaystyle \frac{{\ell }_1(t_f-t)+{\ell }_2}{2{\epsilon }^2}},$$

(47)

$$v^{*}(t,\ell )={\displaystyle \frac{{\ell }_1(t_f-t)+{\ell }_2}{2g}}.$$

(48)

Substituting (47) and (48) into (43),

$$\chi (\ell )=\phi (\ell ,u^{*}(·,\ell ),v^{*}(·,\ell ))=$$

$${\ell }_{1}T+{\ell }_2-{\displaystyle \frac{1}{4}}\left({\displaystyle \frac{1}{f_1}}{\ell }_1^2+{\displaystyle \frac{1}{f_2}}{\ell }_2^2\right)+{\phi }_u(\ell ,u^{*}(·,\ell )+{\phi }_v(\ell ,v^{*}(·,\ell ))=$$

(49)

$${\ell }^{T}d-{\displaystyle \frac{1}{4}}{\ell }^{T}G\ell ,$$

where

$$d={(T,1)}^T,$$

(50)

$$G=F^{-1}+\mu \underset{0}{\overset{t_f}{\int }}h\left(t\right)h^T\left(t\right)dt,$$

(51)

$$\mu ={\displaystyle \frac{1}{{\epsilon }^2}}-{\displaystyle \frac{1}{g}},$$

(52)

$$h\left(t\right)={(t_f-t,1)}^T.$$

(53)

Thus,

$$G=\left[\begin{array}{cc}\frac{1}{f1}+{\displaystyle \frac{\mu t_f^3}{3}}& {\displaystyle \frac{\mu t_f^2}{2}}\\ & \\ {\displaystyle \frac{\mu t_f^2}{2}}& \frac{1}{f2}+\mu t_f\end{array}\right]$$

(54)

Observe that the above is associated with the theory of symmetrical matrices [42]. Moreover, note that the studied interception differential game is solvable if the matrix G given by (54) is positive definite. Hence, the desired result has been obtained. □

5. Numerical Validation

In this section we examine the numerical behavior of the double projection methods described in Section 2 (Arrow–Hurwicz–Uzawa [26], Korpelevich’s extragradient [27] and Popov [35]). We show that under boundedness of the derivatives assumption (14) the results such as $\epsilon \to 0^{+}$ coincide with the dual development of the previous section. We choose $g=4$, $f_1$, $f_2=0.5$, $t_f=4$ and present the results for $\epsilon =0.1,0.01,0.001$. Observe that the

Table 1. Duality.

$\mathit{\epsilon }$	${\mathit{\ell }}_1$	${\mathit{\ell }}_2$	${\mathit{\ell }}^{*}$
$0.1$	$0.007417428195$	$-0.00977333591$	$0.009948188435$
$0.01$	$0.00007499156434$	$-0.00009997687968$	$0.00009999468885$
$0.001$	$7.499991563\times {10}^{-7}$	$-9.999976875\times {10}^{-7}$	$9.999994680\times {10}^{-7}$

,

Table 2. The inner minimizer and maximizer for varying $\epsilon$.

$\mathit{\epsilon }$	${\mathit{u}}^{*}\left(\mathit{t}\right)$	${\mathit{v}}^{*}\left(\mathit{t}\right)$
$0.1$	$-0.9948188435+0.3708714098·t$	$0.002487047109-0.0009271785245·t$
$0.01$	$-0.9999468885+0.3749578217·t$	$0.00002499867221-0.000009373945540·t$
$0.001$	$-0.9999994690+0.3749995782·t$	$2.499998672\times {10}^{-7}-9.374989455\times {10}^{-8}·t$

and

Table 3. Numerical calculations for varying $\epsilon$.

$\mathit{\epsilon }$	${\mathit{z}}_1\left(4\right)$	${\mathit{z}}_2\left(4\right)$	the Cost Functional (26)
$0.1$	$0.007417429$	$-0.009773335$	$0.009948188431$
$0.01$	$0.000074991$	$-0.000099977$	$0.00009999468883$
$0.001$	$7.49\times {10}^{-7}$	$-0.000001$	$9.999994685\times {10}^{-7}$

and Figure 2, Figure 3, Figure 4, Figure 5 and Figure 6 show that for $\epsilon \to 0^{+}$, the values $z_1\left(4\right)$ and $z_2\left(4\right)$ go to zero, meaning that the relative lateral velocity $z_2$ and relative lateral separation $z_1$ of the vehicles tend to zero at the end of the game, and the objective of the interception control is achieved. Observe also that the graphs of the inner minimizer and maximizer in Figure 2 coincide with the results in Table 2. Moreover, the values of the cost functional (26) decrease to 0.

Since we barely noticed any major differences between the numerical methods, we decided to present only the results of Popov [35].

6. Conclusions

In this work we presented a singular, zero-sum, linear-quadratic differential game in which the weight matrix of the minimizer’s control cost in the cost functional is singular. As an application we focused on an interception differential game and introduced a regularized cost functional; we examined its dual representation and validated it via numerical schemes for finding saddle points.