UDC 62-50

CYBERNETICS AND CONTROL THEORY

R. GABASOV, F. M. KIRILLOVA

APPLICATION OF THE MAXIMUM PRINCIPLE FOR COMPUTING OPTIMAL CONTROLS OF DISCRETE SYSTEMS

(Presented by Academician L. S. Pontryagin on 16 V 1969)

1. A powerful means of optimizing discrete systems may be the discrete analog of L. S. Pontryagin’s maximum principle \((^1)\). In those cases where its application is justified \((^{2-4})\), the maximum principle makes it possible to replace a multidimensional minimization problem by a sequence of problems of smaller dimension. Unfortunately, in the general case the discrete analog of the maximum principle does not hold \((^{4,5})\).

Below we propose a method for using the maximum principle, based on replacing the original problem by auxiliary ones, on solving the latter by the maximum principle, and subsequently constructing an approximate solution of the original problem. The idea of this work is consonant with the idea of sliding modes \((^6)\).

2. In order not to go into “end effects,” consider the optimization problem with a free right endpoint

\[ \begin{gathered} x(t+h)=x(t)+h f(x(t),u(t),t),\\ t\in T=[t_0,t_0+h,\ldots,t_1=t_0+Nh],\\ x(t_0)=x_0,\quad u(t)\in U,\quad J(u)=\varphi(x(t_1))\to \min_u . \end{gathered} \tag{1} \]

Here \(x=\{x_1,\ldots,x_n\}\) is the state vector of the object being optimized; \(u=\{u_1,\ldots,u_r\}\) is the control vector; \(t\) is time (discrete); \(h\) is the sampling period of time; \(T\) is the control interval; \(U\) is the set of admissible values; \(f(x,u,t)\), \(\varphi(x)\) are functions continuous together with \(\partial f(x,u,t)/\partial x\), \(\partial\varphi(x)/\partial x\).

To all possible sequences of admissible controls \(u(t)\), \(t\in T\), there correspond trajectories \(x(t)\) of system (1). We shall assume that these trajectories are uniformly bounded with respect to \(u(t)\in U\), \(t\in T\), \(h\le h_0\).

We shall call a control \(\tilde u^0(t)=\tilde u^0(t,h)\), \(t\in T\), a quasi-optimal control if \(J(\tilde u^0)-J(u^0)\le kh\), where \(u^0(t)\), \(t\in T\), is an optimal control; \(k\) is a constant independent of \(h\).

3. Consider the auxiliary problem

\[ x(t+h)=x(t)+h g(x(t),v(t),\alpha(t),t),\quad t\in T, \tag{2} \]

\[ g(x,v,\alpha,t)=\sum_{i=1}^{n+1}\alpha_i f(x,u^i,t),\quad x(t_0)=x_0,\quad v(t)=\{u^1(t),\ldots,u^{n+1}(t)\}, \]

\[ u^i(t)\in U,\quad \alpha(t)=\{\alpha_1(t),\ldots,\alpha_{n+1}(t)\},\quad \alpha_i(t)\ge 0,\quad \sum_{i=1}^{n+1}\alpha_i(t)=1, \]

\[ I(v,\alpha)=\varphi(x(t_1))\to \min_{v,\alpha}. \]

The optimal control \(v^0(t),\alpha^0(t)\), \(t\in T\), of this problem satisfies the maximum condition

\[ H(x^0(t),\psi^0(t),v^0(t),\alpha^0(t),t) = \max_{\substack{u^i\in U,\ \alpha_i\ge 0,\ \sum_{i=1}^{n+1}\alpha_i=1}} H(x^0(t),\psi^0(t),v,\alpha,t). \tag{3} \]

Here \(H(x,\psi,v,a,t)=\psi' g(x,v,a,t)\); \(x^0(t)\) is the optimal trajectory in problem (2); \(\psi^0(t)\) is the solution of the system

\[ \psi^0(t-h)=\psi^0(t)+h\,\partial H(x^0(t),\psi^0(t),v^0(t),a^0(t),t)/\partial x, \]

\[ \psi^0(t_1-h)=-\partial\varphi(x^0(t_1))/\partial x. \]

4. Let \(v^0(t),a^0(t)\), \(t\in T\), be a solution of the auxiliary problem (2). We construct the control \(\tilde u^0(t)\) for problem (1) in the following way. If, for \(\theta\in T\), the condition \(a_k^0(\theta)=1\) is satisfied, then we set \(\tilde u^0(\theta)=u^k0(\theta)\). If, for \(\theta\in T\), the inequalities

\[ 0<a_i^0(\theta)<1,\qquad i=i_1,\ldots,i_m,\quad m\le n+1, \tag{4} \]

hold, then we divide the interval \([\theta,\theta+h]\) into \(lN\) parts, where \(l\) is some number independent of \(h\). We define the control \(\tilde u^0(t)\) on \([\theta,\theta+h]\) by the equalities \((\tau=h/lN)\):

\[ \tilde u^0(t)=u^{i_1 0}(\theta),\qquad t=\theta,\theta+\tau,\ldots,\theta+[a_{i_1}^0(\theta)lN]\tau, \]

\[ \tilde u^0(t)=u^{i_2 0}(\theta),\qquad t=\theta+[a_{i_1}^0(\theta)lN]\tau+\tau,\ldots, \theta+\left[\sum_{k=1}^{2}a_{i_k}^0(\theta)lN\right]\tau, \tag{5} \]

\[ \cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots \]

\[ \tilde u^0(t)=u^{i_m 0}(\theta),\qquad t=\theta+\left[\sum_{k=1}^{m-1}a_{i_k}^0(\theta)lN\right]\tau+\tau,\ldots,\theta+h-\tau. \]

The constructed control \(\tilde u^0(t)\) will be quasi-optimal not only in problem (1) with the indicated \(h\), but also in problem (1) with quantization period \(\tau=h/lN\).

Remark. To construct the quasi-optimal control \(\tilde u^0(t)\) of problem (1), it is sufficient to know the solution of the auxiliary problem (2) only at the points \(t_0,t_0+h,\ldots,t_1-h\).

5. The additional subdivision of the period \(h\) for constructing \(\tilde u^0(t)\) is caused by property (4) of the solution of problem (2). Since it follows from (3) that

\[ \psi^{0'}(t)f(x^0(t),u^{i0}(t),t)= \max_{u\in U}\psi^{0'}(t)f(x^0(t),u,t) \tag{6} \]

for all \(i=1,\ldots,n+1;\ t\in T\), case (4) is possible only when the set \(f(x,U,t)\) is not strictly convex. In this situation the maximum condition (3) becomes ineffective, since by virtue of (6) the control \(v^0(t),a^0(t)\) is singular with respect to the components \(a^0(t)\), i.e., the function \(H(x^0(t),\psi^0(t),v^0(t),a,t)\) does not depend on the parameters \(a_1,\ldots,a_{n+1}\) on the set

\[ a_i\ge 0,\quad \sum_{i=1}^{n+1}a_i=1. \]

Let us formulate an additional necessary condition of optimality for problem (2). Suppose that, in addition to the assumptions made, the functions \(\partial^2 g/\partial x^2\), \(\partial^2\varphi/\partial x^2\) are continuous.

Theorem 1. If \(v^0(t),a^0(t)\), \(t\in T\), are optimal controls in problem (2), then for all \(a\), \(a=\{a_1,\ldots,a_{n+1}\}\), \(a_i\ge 0\), \(\sum_{i=1}^{n+1}a_i=1\), on the interval \(T\) the inequality

\[ \Delta_\alpha g'(x^0(t),v^0(t),a^0(t),t)\Psi^0(t) \Delta_\alpha g(x^0(t),v^0(t),a^0(t),t)\le 0, \]

is satisfied, where \(\Delta_\alpha g(x,v,\beta,t)=g(x,v,\alpha,t)-g(x,v,\beta,t)\); \(\Psi^0(t)\) is an \(n\times n\) matrix-valued function solving the system

\[ \Psi^0(t-h)=\Psi^0(t)+h[\partial g(x^0(t),v^0(t),a^0(t),t)/\partial x]'\Psi^0(t)+ \]

\[ +h\Psi^0(t)\partial g(x^0(t),v^0(t),a^0(t),t)/\partial x+ \]

\[ +h^2[\partial g(x^0(t),v^0(t),a^0(t),t)/\partial x]'\Psi^0(t) [\partial g(x^0(t),v^0(t),a^0(t),t)/\partial x]+ \]

\[ +\frac{1}{2}h\psi^0{}'(t)\frac{\partial^2 g(x^0(t),v^0(t),a^0(t),t)}{\partial x^2}, \]
\[ \Psi^0(t_1-h)=-\frac{1}{2}\frac{\partial^2\varphi(x^0(t_1))}{\partial x^2}. \]

6. Sometimes, in computing the optimal controls of problem (1), it is expedient to pass to the auxiliary problem
\[ \begin{gathered} x(t+h)=x(t)+h f(x(t),v(t),t),\quad t\in T,\\ x(t_0)=x_0,\quad v=\{v_1,\ldots,v_r\},\quad v(t)\in V, \end{gathered} \tag{7} \]
\[ V=\left\{v:\ v=\sum_{i=1}^{r+1}\alpha_i u^i,\ \alpha_i\geq 0,\ \sum_{i=1}^{r+1}\alpha_i=1,\ u^i\in U\right\}, \]
\[ J(v)=\varphi(x(t_1))\to \min_v . \]

If, in addition to the assumptions of item 2, the function \(f(x,u,t)\) is differentiable with respect to \(u\), then the optimal control \(v^0(t)\) of problem (7) satisfies the maximum condition
\[ \frac{\partial H'(x^0(t),\psi^0(t),v^0(t),t)}{\partial u}\,v^0(t) = \max_{v\in V} \frac{\partial H'(x^0(t),\psi^0(t),v^0(t),t)}{\partial u}\,v, \tag{8} \]
\[ H(x,\psi,v,t)=\psi' f(x,v,t). \]

From the control \(v^0(t)\), a quasi-optimal control \(\tilde u^0(t)\) of problem (1) is constructed as follows. If, for \(\theta\in T\), the condition \(v^0(\theta)\in U\) is satisfied, we set \(\tilde u^0(\theta)=v^0(\theta)\). If, for \(\theta\in T\), the control \(v^0(\theta)\in \overline{U}\), then vectors \(u^i\in U\) and numbers \(\alpha_i,\ \alpha_i>0,\ i=i_1,\ldots,i_k\), will be found,
\[ \sum_{m=1}^{k}\alpha_{i_m}=1, \quad\text{such that}\quad v^0(\theta)=\sum_{m=1}^{k}\alpha_{i_m}u^{i_m}. \]
We divide the interval \([\theta,\theta+h]\) into parts by the points
\(\tau_1=\theta+h/lN,\ \tau_2=\theta+2h/lN,\ldots,\tau_{lN-1}=\theta+h-h/lN\), and set
\[ \tilde u^0(t)= \begin{cases} u^{i_1}, & \text{for } t=\theta,\ \theta+\dfrac{h}{lN},\ldots,\theta+\dfrac{[\alpha_{i_1}lN]h}{lN},\\[1.2em] u^{i_2}, & \text{for } t=\theta+\dfrac{[\alpha_{i_1}lN]+1}{lN}h,\ldots,\theta+\dfrac{\left[\sum_{m=1}^{2}\alpha_{i_m}lN\right]h}{lN},\\ \cdots & \cdots\\ u^{i_m}, & \text{for } t=\theta+\dfrac{\left[\sum_{m=1}^{k-1}\alpha_{i_m}lN\right]+1}{lN}h,\ldots,\theta+h-\dfrac{h}{lN}. \end{cases} \]

7. The maximum condition (8) in terms of the given set has the form
\[ \frac{\partial H'(x^0(t),\psi^0(t),v^0(t),t)}{\partial u}\,v^0(t)= \]
\[ = \max_{\substack{u^i\in U,\ \alpha_i\geq 0,\\ \sum_{i=1}^{r+1}\alpha_i=1}} \sum_{i=1}^{r+1} \alpha_i \frac{\partial H'(x^0(t),\psi^0(t),v^0(t),t)}{\partial u}\, u^i . \]

It follows from this that when \(v^0(\theta)\in \overline{U}\), or in the case where \(U\) is not a strictly convex set, condition (8) becomes ineffective, since the function
\[ \sum_{i=1}^{r+1} \alpha_i \frac{\partial H'(x^0(t),\psi^0(t),v^0(t),t)}{\partial u}\, u^{i_0}(t) \]
does not depend on the parameters \(\alpha_i,\ i=1,\ldots,r+1;\ \alpha_i\geq 0,\ \sum_{i=1}^{r+1}\alpha_i=1.\)

Let us formulate additional conditions which the optimal values of the parameters \(a_i\), \(i=1,\ldots,r+1\), must necessarily satisfy. Suppose that the functions \(f(x,u,t)\), \(\varphi(x)\) satisfy all the conditions imposed above and, in addition, that \(f(x,u,t)\) is twice differentiable with respect to \(u\).

Theorem 2. If \(v^0(t)\) is an optimal control in problem (7), then for all \(a_i \geqslant 0\), \(\displaystyle \sum_{i=1}^{r+1} a_i = 1\), and \(t \in T\), the inequality

\[ \left[\sum_{i=1}^{r+1}\left(a_i-a_i^0(t)\right)u^{i0}(t)\right]' Q(t)\sum_{i=1}^{r+1}\left(a_i-a_i^0(t)\right)u^{i0}(t) \leqslant 0. \]

holds.

Here \(a_i^0(t)\), \(u^{i0}(t)\) are such that

\[ v^0(t)=\sum_{i=1}^{r+1} a_i^0(t)u^{i0}(t), \]

\[ Q(t)= \frac{\partial f'(x^0(t),v^0(t),t)}{\partial u}\, \Psi^0(t)\, \frac{\partial f(x^0(t),v^0(t),t)}{\partial u} + \frac{1}{2} \frac{\partial^2 H(x^0(t),\psi^0(t),v^0(t),t)}{\partial u^2}, \]

\(\psi^0(t)\), \(\Psi^0(t)\) being defined as above for \(g(x,v,\alpha,t)\equiv f(x,v,t)\).

Belorussian State University
Minsk

Institute of Mathematics
Academy of Sciences of the BSSR
Minsk

Received
13 V 1969

REFERENCES

1. L. S. Pontryagin, V. G. Boltyanskii et al., The Mathematical Theory of Optimal Processes, Moscow, 1961.
2. L. I. Rozonoer, Automation and Remote Control, 20, No. 12, 1561 (1959).
3. A. I. Propoi, ibid., 26, No. 7, 1477 (1965).
4. R. Gabasov, Journal of Computational Mathematics and Mathematical Physics, 8, No. 7, 780 (1968).
5. A. G. Butkovskii, Automation and Remote Control, 24, No. 8, 1056 (1963).
6. R. V. Gamkrelidze, DAN, 143, No. 6, 1243 (1962).