Abstract Generated abstract
This paper studies optimization problems for linear control systems with convex bounded controls, where constraints are imposed on a convex control functional, endpoint deviations, and deviations of selected trajectory components from a prescribed curve at specified times. The authors transform the trajectory constraints into a finite system of linear operator equations and use convexity and supporting hyperplane arguments to derive a necessary and sufficient solvability condition expressed through minimization of a homogeneous dual function. The same framework yields optimality relations analogous to a maximum principle, criteria for uniqueness under a normality condition, continuity properties of optimal bounds and time in nondegenerate cases, and computational procedures based on finite-dimensional minimization or ascent methods for synthesizing optimal controls.
Full Text
R. Gabasov, F. M. Kirillova
Optimization of Convex Functionals on Trajectories of Linear Systems
(Presented by Academician L. S. Pontryagin, 23 I 1964)
1. Let the control process be described by the equations
\[ \frac{dx}{dt}=A_1(t)x+B_1(t)y+C_1(t)u+f_1(t), \]
\[ \frac{dy}{dt}=A_2(t)x+B_2(t)y+C_2(t)u+f_2(t), \tag{1} \]
where \(x,y\) are vectors of phase coordinates in the spaces \(X,Y\); the matrices \(A_i(t), B_i(t), C_i(t)\), the functions \(f_i(t)\), and the control \(u(t)\) \((u\in U,\ U\) a bounded convex set) are such that the solutions \(\{x(t),y(t)\}\) are piecewise continuous and admit the representation (3) with continuous \(F_{ij}(t,\tau)\).
Given are the numbers \(t_0, T, s_k, L_j\) \((T>t_0,\ s_k>s_{k-1},\ k=3,4,\ldots,m-1,\ s_3=t_0,\ s_{m-1}\leq T,\ j=1,2,\ldots,m,\ L_j\geq 0\) for \(j\ne 1)\), a functional convex in \(u\), \(\varphi(u,T)\) \((\varphi(\alpha u+\beta v,T)\leq \alpha\varphi(u,T)+\beta\varphi(v,T),\ \alpha+\beta=1,\ \alpha\geq 0,\ \beta\geq 0;\ u,v\in U)\), such that the set \(R_T=\{r:r=\varphi(u,T),\ u\in U\}\) is bounded. In the space \(Y\) a curve \(\gamma(t)\), \(t\in [t_0,T]\), is given, and points \(x_0,x_1\in X\) are fixed.
Problem\(^*\). Find necessary and sufficient conditions for the existence of a function \(u\in U\) for which
\[ \varphi(u,T)\leq L_1,\qquad \|x(t_0)-x_0\|\leq L_2, \]
\[ \|x(T)-x_1\|\leq L_3,\qquad \|y(s_k)-\gamma(s_k)\|\leq L_{k+1}. \tag{2} \]
A solution \(u=u^0(t)\) of problem (2) is called lower optimal (\(^1\)) if one of the numbers \(L_j,T\) is minimal (under the condition that the others are fixed).
Introduce the operators \(F_{ij}(t,\tau)\), which determine the solution \(\{x(t),y(t)\}\):
\[ x(t)=F_{11}(t,t_0)x(t_0)+F_{12}(t,t_0)y(t_0)+ \]
\[ +\int_{t_0}^{t}\{F_{11}(t,\tau)[C_1(\tau)u(\tau)+f_1(\tau)] +F_{12}(t,\tau)[C_2(\tau)u(\tau)+f_2(\tau)]\}\,d\tau, \]
\[ y(t)=F_{21}(t,t_0)x(t_0)+F_{22}(t,t_0)y(t_0)+ \tag{3} \]
\[ +\int_{t_0}^{t}\{F_{21}(t,\tau)[C_1(\tau)u(\tau)+f_1(\tau)] +F_{22}(t,\tau)[C_2(\tau)u(\tau)+f_2(\tau)]\}\,d\tau. \]
Put
\[ u=u^1,\qquad x(t_0)-x_0=u^2,\qquad x(T)-x_1=u^3, \]
\[ y(t_k)-\gamma(t_k)=u^{4+k},\qquad t_k=s_{k+3},\qquad k=0,1,\ldots,m-4, \]
\[ S_{11}u^1=\int_{t_0}^{T}[F_{11}(T,\tau)C_1(\tau)+F_{12}(T,\tau)C_2(\tau)]u^1(\tau)\,d\tau,\qquad S_{12}=F_{11}(T,t_0), \]
\[ S_{13}=-E,\quad S_{14}=F_{12}(T,t_0),\quad S_{1,4+i}=0,\quad i\geq 1,\quad h^1=x_1-F_{11}(T,t_0)x_0- \]
\(^*\) The results of the paper were reported at L. S. Pontryagin’s seminar on the theory of oscillations and automatic control.
\[ - F_{12}(T,t_0)\gamma(t_0)- \int_{t_0}^{T}\bigl[F_{11}(T,\tau)f_1(\tau)+F_{12}(T,\tau)f_2(\tau)\bigr]\,d\tau, \qquad S_{2+k,1}u^1 = \]
\[ = \int_{t_0}^{t_{k+1}}\bigl[F_{21}(t_{k+1},\tau)C_1(\tau)+F_{22}(t_{k+1},\tau)C_2(\tau)\bigr]u^1(\tau)\,d\tau, \qquad S_{2+k,2}=F_{21}(t_{k+1},t_0), \]
\[ S_{2+k,3}\equiv 0,\qquad S_{2+k,4}=F_{22}(t_{k+1},t_0),\qquad S_{2+k,4+i}=-E\ (k=i-1), \]
\[ S_{2+k,4+i}=0\quad (k\ne i-1), \]
\[ h^{2+k}=\gamma(t_{k+1})-F_{21}(t_{k+1},t_0)x_0-F_{22}(t_{k+1},t_0)\gamma(t_0)- \]
\[ -\int_{t_0}^{t_{k+1}}\bigl[F_{21}(t_{k+1},\tau)f_1(\tau)+F_{22}(t_{k+1},\tau)f_2(\tau)\bigr]\,d\tau. \]
By virtue of (2), (3), the quantities \(u^j,\ j=1,2,\ldots,m,\) satisfy the relations
\[ \sum_{j=1}^{m}S_{ij}u^j-h^i=0,\qquad i=1,2,\ldots,m-3. \tag{4} \]
Here \(u^j,\ j\ne 1,\) are elements of finite-dimensional spaces \(V_j,\ \|u^j\|\le L_j,\ u^1\in U\subset V_1;\) the linear operators \(S_{ij}\) map \(V_j\) into \(X_i\). Suppose the supremum
\[ \sup_{u^1\in U}\left\{\sum_{i=1}^{m-3}(S_{i1}^{*}g^i,u^1)+f\varphi(u^1,T)\right\} = \sup_{u^1\in U}H(g,f,u^1), \qquad g^i\in X_i^{*},\quad f\le 0, \]
is attained for \(u^1\in U\). Put
\[ \lambda(L_1,L_2,\ldots,L_m,T,g,f) = \sum_{j=2}^{m}L_j \left\| \sum_{i=1}^{m-3}S_{ij}^{*}g^i \right\| -L_1f- \]
\[ -\sum_{i=1}^{m-3}g^i(h^i)+\max_{u^1\in U}H(g,f,u^1). \]
It is clear that \(\lambda(L_1,L_2,\ldots,L_m,T,g,f)\) is convex in \(\{g,f\}\).
Assume that the closed set
\[ Q(L_2,L_3,\ldots,L_m,U)= \left\{z:z=(z_1,z_2,\ldots,z_{m-3},\varphi(u^1,T)),\ z_i=\sum_{j=1}^{m}S_{ij}u^j,\ u^1\in U,\ \|u^j\|\le L_j\right\}. \]
Using the fact of the existence of a supporting hyperplane to the convex surface
\(\delta(z_1,z_2,\ldots,z_{m-3})=\inf_{u^1\in U}\varphi(u^1,T)\) under condition (4), we arrive at the following assertion.
Theorem. Problem (2) has a solution if and only if the condition
\[ \Lambda(L_1,L_2,\ldots,L_m,T)\ge 0, \]
\[ \Lambda(L_1,L_2,\ldots,L_m,T) = \lambda(L_1,L_2,\ldots,L_m,T,g^0,f^0) = \]
\[ = \min \lambda(L_1,L_2,\ldots,L_m,T,g,f), \qquad g,\ f\le 0. \tag{5} \]
is satisfied.
The optimal value \(L_j^0(T^0)\) is the smallest number \(L_j\) (respectively \(T\)) satisfying inequality (5). If the function \(\Lambda=\Lambda(L_j)\) \((\Lambda=\Lambda(T))\) is continuous from the left at the point \(L_j^0(T^0)\), then for any optimal control \(u^1=u_0^1\) and quantities \(u_0^j\) the relations
\[ \max_{u^1\in U}H(g^0,f^0,u^1)=H(g^0,f^0,u_0^1), \]
\[ \left(\sum_{i=1}^{m-3}S_{ij}^{*}g^{i0},u^j\right) = L_j\left\| \sum_{i=1}^{m-3}S_{ij}^{*}g^{i0} \right\|, \qquad j\ne 1. \tag{6} \]
hold.
\[
\text{*}
\]
By virtue of the homogeneity of the function \(\lambda\) in \(\{g,f\}\), the quantity \(\Lambda\) depends on an arbitrary multiplier. Therefore, in computing \(\Lambda\) we set \(\|\{g,f\}\|=1\).
The theorem admits a generalization (cf. with \((2)\)) to the case of several constraints \(\varphi_l(u,T)\leqslant L_l,\ l=1,2,\ldots,n\), where the functionals \(\varphi_l(u,T)\) are of the type \(\varphi(u,T)\). Then, for example, condition (6) takes the form
\[ \max_{u^1\in U}\left[\sum_{i=1}^{m-3}(S_i^*g^{i0},u^1)+\sum_{l=1}^n f^{l0}\varphi_l(u^1,T)\right] = \sum_{i=1}^{m-3}(S_i^*g^{i0},u_0^1)+\sum_{l=1}^n f^{l0}\varphi_l(u_0^1,T). \]
We shall call the collection \(\{\varphi(u,T),S_i\}\), for given \(g^i,f\), normal if the function \(u=u^*\) is essentially uniquely determined by the equality
\[ \max_{u\in U} H(g,f,u)=H(g,f,u^*). \]
By virtue of the convexity of \(\lambda(L_1,L_2,\ldots,L_m,T,g,f)\) with respect to \(\{g,f\}\), the minimum \(\Lambda(L_1,L_2,\ldots,L_m,T)\) is unique, although it may be attained at more than one element \(\{g^0,f^0\}\). But if the collection \(\{\varphi(u,T),S_i\}\) is normal at least for one \(\{g^0,f^0\}\), then the optimal control is unique.* Several criteria of normality can be indicated. Questions of uniqueness of the optimal control for \(\varphi\equiv0\) were investigated in \((1)\); normality conditions for one particular problem with \(f\leqslant0\) are given in \((2)\).
Consider the function \(\Lambda(L_1,L_2,\ldots,L_m,T)\). For fixed \(T\) this function is continuous in the arguments \(L_j\). If
\[ \sum_{i=1}^{m-3} S_{ik}^*g^i\ne0 \]
when \(g^i\ne0\), then \(\Lambda(L_1,L_2,\ldots,L_m,T)\) strictly increases in the minimized \(L_k,\ k\ne1\). In this case the quantity \(L_k^0\) is continuous in \(x_0,x_1,\gamma(s_m),L_p,\ p\ne k\); \(L_1^0\) is continuous in \(x_0,x_1,\gamma(s_m),L_p\), since \(f^0<0\) when \(L_1^0=\min_u\). Suppose that, for fixed \(L_i\), the function \(\Lambda(L_1,L_2,\ldots,L_m,T)\) is continuous and strictly increases in \(T,\ T\in(\mu_k,\mu_{k+1})\). Then the optimal time \(T^0\) on the intervals \((\mu_k,\mu_{k+1})\) is a continuous function of the variables \(x_0,x_1,\gamma(s_m),L_i\). The indicated properties are possessed by \(\Lambda(L_1,L_2,\ldots,L_m,T)\), for example, in the following nondegenerate problems \((3)\): \(U=\{u(t): \operatorname{vrai}\max_t |u_k(t)|\leqslant1\}\), \(f_1(t)\equiv f_2(t)\equiv0\); a) \(\varphi(u,T)\equiv0\), the trajectory \(\{x(t),y(t)\}\) is transferred from the prescribed point \(\{x_0,y_0\}\) to the origin; b) if in problem (2) the quantity
\[ M(T)=\max_{u^1\in U} H(g,f,u^1) \]
for any \(g,\ f\leqslant0\) is continuous and strictly increases in \(T,\ T\in(s_k,s_{k+1})\), and \(x(T)=x_1=y(T)=0\); c) \(M(T)\) is continuous, strictly increases in \(T\) on \((s_k,x_{k+1})\); \(x(t_0)=y(t_0)=\gamma(t_0)=x_0=0\). In cases b), c) the operators \(S_{ij}\) and the vectors \(h^i\) change their form.
Remark. Suppose that the functional \(\varphi(u,T)\) satisfies the conditions: \(\varphi(u,T)\geqslant0,\ \varphi(cu,T)\leqslant |c|\varphi(u,T),\ U=\{u(t),\ \|u\|\leqslant1,\ t\in[t_0,T]\}\). We shall call the collection \(w=\{u(t),x(t_0),y(t_0)\}\) a control. For \(w\) one can define a norm in such a way that problem (2) will be equivalent to the \(L\)-problem \((4)\) in an abstract space. The expressions necessary for solving, by this route, the norms of elements of the conjugate space are easily obtained from (5).
- The problem of synthesizing the optimal control is reduced (if it is assumed that a method for computing \(\max_{u\in U} H(g,f,u)\) is known) to finding the extremum (5) of a function of a finite number of variables \(\{g,f\}\): the values \(\{g^0,f^0\}\) obtained in this way determine the initial conditions for the adjoint system in the maximum principle \((1)\).
In computing \(\{g^0,f^0\}\), one may use, for example, the following methods.
\(A_1.\) The time \(T\) is minimized. Suppose that \(\Lambda(L_1,L_2,\ldots,L_m,T)\) is piecewise continuous in \(T\), \(\Lambda(L_1,L_2,\ldots,L_m,+0)<0\), and \(T(0)>0\) are sufficiently
* Situations are not considered here in which nonuniqueness is obvious, for example, \(\Lambda(L_1,L_2,0,L_4,\ldots,L_m,T)>0\) when finding \(L_3=\min\).
small number. The zero approximation \(\{g(0), f(0)\}\) is found from the condition
\[
\lambda(L_1,L_2,\ldots,L_m,T(0),g(0),f(0))
=\min_{g,\,f\leqslant 0}\lambda(L_1,L_2,\ldots,L_m,T(0),g,f)
=\Lambda(0).
\]
If \(T(0)\) is sufficiently small, then \(\Lambda(0)\leqslant 0\), and \(\Lambda(L_1,L_2,\ldots,L_m,T)<0\) for \(T<T(0)\). Let \(\Lambda(0)=0\). Then the problem is solved, and \(T(0)\) is the optimal time. If \(\Lambda(0)<0\), then for the first approximation \(T(1)\) one takes the number \(T(1)=T(0)+\Delta T(0)\), where \(\Delta T(0)>0\) is a small increment; the quantities \(\{g(1),f(1)\}\) are determined from the condition
\[
\lambda(L_1,L_2,\ldots,L_m,T(1),g(1),f(1))
=\min_{g,\,f\leqslant 0}\lambda(L_1,L_2,\ldots,L_m,T(1),g,f)
=\Lambda(1).
\]
If there is no such \(\Delta T(0)>0\) that \(\Lambda(1)<0\), then \(T^0=T(0)\). Otherwise, for sufficiently small \(\Delta T(0)\) we have \(\Lambda(1)\leqslant 0\), and \(\Lambda(L_1,L_2,\ldots,L_m,T)<0\) if \(T<T(1)\). The number \(T(1)\) is the optimal time when \(\Lambda(1)=0\). If \(\Lambda(1)<0\), the process continues. The function \(\lambda(L_1,L_2,\ldots,L_m,T,g,f)\) cannot have local minima; the quantities \(\Lambda(k)\) can be determined by the method of steepest descent.
\(A_2\). Suppose the optimal-speed problem is being solved and the function \(\Lambda(L_1,L_2,\ldots,L_m,T)\) is piecewise continuous, strictly increases in \(T\) on the intervals of continuity \((\mu_k,\mu_{k+1})\), and
\[
\Lambda(L_1,L_2,\ldots,L_m,\mu_k+0)<0,
\]
\[
\Lambda(L_1,L_2,\ldots,L_m,\mu_k-0)>\Lambda(L_1,L_2,\ldots,L_m,\mu_k+0).
\]
As a zero approximation we take arbitrary numbers \(\{g(0),f(0)\}\), \(f(0)\leqslant 0\). We compute \(T(0)\) from the equation
\[
\lambda(L_1,L_2,\ldots,L_m,T(0),g(0),f(0))=0;
\]
the first approximation is found from the condition
\[
\lambda(L_1,L_2,\ldots,L_m,T(0),g(1),f(1))
\]
\[
=\min_{g,\,f\leqslant 0}\lambda(L_1,L_2,\ldots,L_m,T(0),g,f)=\Lambda(0).
\]
If \(\Lambda(0)=0\), then \(T(0)\) is the optimal time and \(g^0=g(0)\), \(f^0=f(0)\); if \(\Lambda(0)<0\), then the process continues, i.e. we find \(T(1)\) from the equation
\[
\lambda(L_1,L_2,\ldots,L_m,T(1),g(1),f(1))=0,
\]
and so on. It is clear that \(T(k)\leqslant T(k+1)\).
\(A_3\). The time \(T=T^0\) in case \(A_2\) satisfies the condition
\[
T^0=\{\max T;\ g,f\leqslant 0\mid \lambda(L_1,L_2,\ldots,L_m,T,g,f)=0\}.
\]
Consequently, one can construct a process of steepest ascent for computing \(g^0,f^0\).
\(A_4\). The methods \(A_1,A_2\) are suitable for minimizing the quantities \(L_j\). But, moreover, the relations
\[
\left(\sum_{i=1}^{m-3}S_{ik}^*g^i\ne 0,\quad g^i\ne 0\right)
\]
hold:
\[
L_k=\left\{\max\left\{\sum_{i=1}^{m-3}g^i(h^i)+L_1f-\sum_{j=2,\,j\ne k}^{m}L_j\left\|\sum_{i=1}^{m-3}S_{ij}^*g^i\right\|
-\max_{u^1\in U}H(g,f,u^1)\right\};\ g^i,f\leqslant 0\ \left|\left\|\sum_{i=1}^{m-3}S_{ik}^*g^i\right\|\right|=1\right\},\quad k\ne 1.
\]
The procedures \(A_2,A_3\), in another interpretation and for problems different from those presented here, were used in \((^5{}^6)\). When writing the article the authors were familiar with the results of T. B. Babunashvili on the synthesis of optimal-speed systems.
Ural Polytechnic Institute
named after S. M. Kirov
Received
20 I 1964
CITED LITERATURE
- L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze, E. F. Mishchenko, Mathematical Theory of Optimal Processes, Moscow, 1961.
- L. W. Neustadt, J. Math. Anal. and Appl., 3, No. 3, 406 (1961).
- N. N. Krasovskii, Prikl. matem. i mekh., 21, No. 5, 670 (1957).
- N. Akhiezer, M. Krein, On Some Questions of the Theory of Moments, Kharkov, 1938.
- L. W. Neustadt, J. Math. Anal. and Appl., 1, No. 1, 484 (1960).
- A. G. Butkovskii, Avtomatika i telemekh., 24, No. 9, 1217 (1963).