UDC 519.3

MATHEMATICS

O. V. VASIL'EV, F. M. KIRILLOVA

ON OPTIMAL PROCESSES IN TWO-PARAMETER DISCRETE SYSTEMS

(Presented by Academician L. S. Pontryagin on 25 VIII 1966)

1. Let, at the nodes \((mh,n\tau)\) of the rectangle
\[ D=\{mh,n\tau:\ m=0,1,\ldots,M,\ n=0,1,\ldots,N\}, \]
the relation between the \(q\)-dimensional vector \(x=x(m,n)\) and the \(r\)-dimensional control vector \(u=u(m,n)\) be given by the equation
\[ R_{h\tau}(x(m,n))=f(x,R_h,R_\tau,u,m,n) \tag{1} \]
and by the initial conditions
\[ x(0,n)=\gamma^n,\quad n=0,1,\ldots,N;\qquad x(m,0)=\beta^m,\quad m=0,1,\ldots,M, \tag{2} \]
where
\[ \begin{aligned} R_{h\tau}(x(m,n))&=[x(m+1,n+1)-x(m+1,n)-x(m,n+1)+{}\\ &\qquad {}+x(m,n)]/h\tau,\\ R_h&=R_h(x(m,n))=[x(m+1,n)-x(m,n)]/h,\\ R_\tau&=R_\tau(x(m,n))=[x(m,n+1)-x(m,n)]/\tau, \end{aligned} \]
\(f(x,R_h,R_\tau,u,m,n)\) is uniquely defined on
\[ E^q\times E^q\times E^q\times E^r\times E^1\times E^1, \]
is continuous, and has there continuous second derivatives with respect to \(x,R_h,R_\tau\).

Define the class of admissible controls \((^{1,2})\) by requiring that \(u(m,n)\in U\), where \(U\) is a given subset of \(E^r\). On the trajectories (1)—(2) define the functional
\[ S(u)=(c\cdot x(M,N)). \]

Problem. Find \(u^0(m,n)\in U\) \((m=0,1,\ldots,M-1;\ n=0,1,\ldots,N-1)\) such that
\[ S(u^0)=\min_{u\in U} S(u). \tag{3} \]
A solution \(u^0\) of problem (3) will be called an optimal control.

2. To the control \(u(m,n)\in U\) there corresponds a solution \(x(m,n)\); to the control
\[ u(m,n)+\Delta u(m,n)\in U \]
there corresponds a solution \(x(m,n)+\Delta x(m,n)\), and
\[ \begin{aligned} R_{h\tau}(\Delta x(m,n))={}&f(x+\Delta x,R_h+\Delta R_h,R_\tau+\Delta R_\tau,u+\Delta u,m,n)\\ &{}-f(x,R_h,R_\tau,u,m,n), \end{aligned} \tag{4} \]
\[ \Delta x(m,0)=\Delta x(0,n)=0, \]
where
\[ \Delta R=R(x(m,n)+\Delta x(m,n))-R(x(m,n))=R(\Delta x(m,n)). \]

For an arbitrary sequence of \(q\)-dimensional vectors \(p(m,n)\),
\[ m=-1,0,\ldots,M-1;\quad n=-1,0,\ldots,N-1, \]
the following equality holds:
\[ \begin{aligned} \sum_{m=0}^{M-1}\sum_{n=0}^{N-1}(p(m,n)\cdot R_{h\tau}(\Delta x(m,n)))h\tau ={}&\sum_{m=0}^{M-1}\sum_{n=0}^{N-1}(\overline{R}_{h\tau}(p(m,n))\cdot \Delta x(m,n))h\tau\\ &{}-\sum_{m=0}^{M-1}(\overline{R}_h(p(m,N-1))\cdot \Delta x(m,N))h\\ &{}-\sum_{n=0}^{N-1}(\overline{R}_\tau(p(M-1,n))\cdot \Delta x(M,n))\tau\\ &{}+(p(M-1,N-1)\cdot \Delta x(M,N)), \end{aligned} \tag{5} \]
where
\[ \overline{R}_{h\tau}(p(m,n))=[p(m,n)-p(m-1,n)-p(m,n-1)+p(m-1,n-1)]/h\tau, \]

\[ \overline{R}_h(p(m,n))=[p(m,n)-p(m-1,n)]/h,\qquad \overline{R}_\tau(p(m,n))=[p(m,n)- \]
\[ {}-p(m,n-1)]/\tau . \]

Put

\[ H(x,p,R_h,R_\tau,u,m,n)=(p(m,n)\cdot f(x,R_h,R_\tau,u,m,n)) \]

and choose \(p(m,n)\) from the equations

\[ \overline{R}_{h\tau}(p(m,n))=\partial H(x,p,R_h,R_\tau,u,m,n)/\partial x- \]
\[ {}-\overline{R}_h(\partial H(x,p,R_h,R_\tau,u,m,n)/\partial R_h) -\overline{R}_\tau(\partial H(x,p,R_h,R_\tau,u,m,n)/\partial R_\tau) \tag{6} \]

with boundary conditions

\[ p(M-1,N-1)=-c, \tag{7} \]
\[ \overline{R}_h(p(m,N-1))=-\partial H(x,p,R_h,R_\tau,u,m,N-1)/\partial R_\tau, \]
\[ \overline{R}_\tau(p,(M-1,n))=-\partial H(x,p,R_h,R_\tau,u,M-1,n)/\partial R_h . \]

From (4), (6), (7) and identity (5) we obtain

\[ -(c\cdot \Delta x(M,N))= \sum_{m=0}^{M-1}\sum_{n=0}^{N-1} h\tau \bigl[H(x,p,R_h,R_\tau,u+\Delta u,m,n)- \]
\[ {}-H(x,p,R_h,R_\tau,u,m,n)\bigr] +\sum_{m=0}^{M-1}\sum_{n=0}^{N-1} h\tau \bigl[H(x+\Delta x,p,R_h+\Delta R_h,R_\tau+\Delta R_\tau, \]
\[ u+\Delta u,m,n)-H(x,p,R_h,R_\tau,u+\Delta u,m,n)- \]
\[ {}-\sum_{m=0}^{M-1}\sum_{n=0}^{N-1} h\tau \left[\left(\frac{\partial H(x,p,R_h,R_\tau,u,m,n)}{\partial x}\cdot \Delta x(m,n)\right)+\right. \]
\[ \left. {}+\left(\frac{\partial H(x,p,R_h,R_\tau,u,m,n)}{\partial R_h}\cdot \Delta R_h(m,n)\right) +\left(\frac{\partial H(x,p,R_h,R_\tau,u,m,n)}{\partial R_\tau}\cdot \Delta R_\tau(m,n)\right)\right]. \]

Hence

\[ \Delta S\equiv S(u+\Delta u)-S(u)\equiv (c\cdot \Delta x(M,N))= \]

\[ =-\sum_{m=0}^{M-1}\sum_{n=0}^{N-1}h\tau [H(z,p,u+\Delta u,m,n)-H(z,p,u,m,n)]-\eta,\qquad \eta+\eta_1+\eta_2, \]

\[ \eta_1= \sum_{m=0}^{M-1}\sum_{n=0}^{N-1}h\tau \left(\left[ \frac{\partial H(z,p,u+\Delta u,m,n)}{\partial z} -\frac{\partial H(z,p,u,m,n)}{\partial z} \right]\cdot \Delta z(m,n)\right), \]

\[ \eta_2=\frac{1}{2}h\tau \sum_{m=0}^{M-1}\sum_{n=0}^{N-1} \left(\Delta z(m,n)\times \right. \]
\[ \left. {}\times \frac{\partial^2 H(z+\theta\Delta z,p,u+\Delta u,m,n)}{\partial z^2} \Delta z(m,n)\right),\qquad 0\leqslant \theta(m,n)\leqslant 1 . \]

Here \(z=\{x,R_h,R_\tau\}\) is a \(3q\)-dimensional vector.

For the variation

\[ \Delta^*u(m,n)= \begin{cases} u^*-u(k,l), & m=k,\ n=l,\\ 0, & m\ne k,\ n\ne l, \end{cases} \]

we have

\[ \Delta^*S\equiv S(u+\Delta^*u)-S(u) =-h\tau\{[H(z,p,u^*,k,l)-H(z,p,u,k,l)]-\eta^*\}, \]

\[ \eta^*=\frac{1}{2} \sum_{m=k+1}^{M-1}\sum_{n=l+1}^{N-1} \left(\Delta z(m,n)\cdot \frac{\partial^2 H(z+\theta\Delta z,p,u,m,n)}{\partial z^2} \Delta z(m,n)\right),\qquad \eta_1^*=0. \]

It is not difficult to show that

\[ |\eta^*|\leqslant \frac{1}{2}(h\tau)^2\|f(z,u^*,k,l)-f(z,u,k,l)\|^2\times \]
\[ {}\times \sum_{m=k+1}^{M-1}\sum_{n=l+1}^{N-1} L_{m,n}\left\|\frac{\partial^2 H(m,n)}{\partial z^2}\right\| =\overline{\eta}. \tag{8} \]

1. Let \(f(z,u,m,n)\) be differentiable with respect to \(u\). Introduce the set \(a(\alpha,k,l)\):

\[ a(\alpha,z,p,k,l,u(k,l),\ldots,u(M-1,N-1),h,\tau)=\{u^*:|\eta^*|\leq \alpha\} \]

and the quantity \(\delta_u H\)

\[ H(z,p,u+\Delta u,m,n)-H(z,p,u,m,n)=\delta_u H(z,p,u,m,n)+o(\|\delta u\|). \]

Definition. The control \(u\) at the node \((k,l)\) satisfies the quasimaximum condition with number \(\mu(k,l)\) and set \(\omega(k,l)\), if:

1) \(H(z,p,u,k,l)\geq H(z,p,u^*,k,l)-\mu(k,l)\) for all \(u^*\in\omega(k,l)\);

2) \(\delta_u H\leq 0\) if \(U\) is convex,

3) \(\delta_u H=0\) at interior points of \(U\).

Theorem 1. The optimal control \(u^0=u^0(m,n)\) for problem (3) satisfies the conditions:

1) quasimaximum with \(\mu(k,l)=\alpha,\ \omega(k,l)=a(\alpha,k,l)\cap U,\ k=0,1,\ldots,M-2;\ l=0,1,\ldots,N-2;\)

2)

\[ H(z,p,u^0,k,l)\geq H(z,p,u,k,l),\qquad u\in U \tag{9} \]

for \(k=M-1;\ l=0,\ldots,N-1\) and \(k=0,\ldots,M-1;\ l=N-1\).

Remark. For convenience of computation, the set \(a(\alpha,k,l)\) may be replaced by the set \(a'(\alpha,k,l)\):

\[ a'(\alpha,k,l)=\{u^*:|\overline{\eta}|\leq \alpha\}, \]

where \(\overline{\eta}\) is some upper estimate for \(\eta^*\), for example (8).

From the definition of the set \(a(\alpha,k,l)\) it follows that the local-maximum principle is valid at the node \((k,l)\) if the set \(a(0,k,l)\) contains points distinct from \(u^0(k,l)\).

Thus, the quasimaximum condition singles out some set \(U^*\subset U\) of points \(u(k,l)\) suspected of optimality. The narrowing of the set \(U^*\) is carried out by varying \(\alpha\) and by the local conditions \(\delta_u H\leq 0,\ \delta_u H=0\).

Let \(h\to0,\ \tau\to0\); then the number \(\alpha^*\) from \(a'(\alpha^*,k,l)\supseteq U\) tends to zero, and the quasimaximum condition passes into the condition of the absolute maximum, with respect to \(u\), of the function \(H\).

1. For the linear variant

\[ R_{h\tau}(x(m,n))=A(m,n)x(m,n)+B(m,n)R_h(x(m,n))+ \]
\[ +C(m,n)R_\tau(x(m,n))+\varphi(m,n,u(m,n)) \tag{10} \]

of equation (1), we have \(\eta=0\).

Theorem 2. In order that the control \(u^0\in U\) for (10) be optimal, it is necessary and sufficient that condition (9) be fulfilled at the nodes \((m,n)\), \(m=0,1,\ldots,M-1;\ n=0,1,\ldots,N-1\).

1. For the case

\[ R_{h\tau}(x(m,n))=A(m,n,u(m,n))x(m,n)+B(m,n,u(m,n))R_h(x(m,n))+ \]
\[ +C(m,n,u(m,n))R_\tau(x(m,n))+\varphi(m,n,u(m,n)) \]

it is not difficult to see that \(\eta^*=0\).

Theorem 3. If \(u^0=u^0(m,n)\) is an optimal control, then at each node \((k,l)\), \(k=0,1,\ldots,M-1;\ l=0,1,\ldots,N-1\), (9) is fulfilled.

1. Let \(U\) be convex and let equation (1) have the form

\[ R_{h\tau}(x(m,n))=\sum_{i=1}^{r}u_i(m,n)\cdot f_i(x,R_h,R_\tau,m,n)+g(x,R_h,R_\tau,m,n). \]

Theorem 4. For the optimal control \(u^0\), condition (9) is fulfilled at all nodes of the rectangle \(D\).

Ural Polytechnic Institute
named after S. M. Kirov

Received
10 VI 1966

CITED LITERATURE

1. L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze, E. F. Mishchenko, Mathematical Theory of Optimal Processes, Moscow, 1961.
2. L. I. Rozonoer, Automation and Remote Control, 20, Nos. 10–12 (1959).