Authors
Richard BellmanIrving GlicksbergOliver Gross
Topics
Quantum chaos and dynamical systemsSummary. Let S be a physical system whose state at any time is described by an n-dimensional vector x(t), where x(t) is determined by a linear differential equation dz/dt = Az, with A a constant matrix. Application of external influences will yield an inhomogeneous equation, dz/dt = Az + /, where f, the "forcing term", represents the control. A problem of some importance in the theory of control circuits is that of choosing / so as to reduce z to 0 in minimum time. If / is restricted to belong to the class of vectors whose ith components can assume only the values ± bt , the control is said to be of the "bang-bang" type.Various aspects of the above problem have been treated by McDonald, Bushaw, LaSalle and Rose. We shall consider here the case where all the solutions of dz/dt = Az approach zero as < -». In this case we prove that the problem of determining / so as to minimize the time required to transform the system into the rest position subject to the requirement that fi , the ith component, satisfies the constraint | /< | < may be reduced to the case where /^ = ± b{. Furthermore, we show that if all the characteristic roots of A are real and negative, /, need change value only a finite number of times at most, dependent upon the dimension of the system.Finally, an example is given for n = 2, illustrating the procedure that can be followed and the results that can be obtained.Let z be an n-dimensional vector function of t satisfying the linear differential equation jt = Az + /, z( 0) = c, (where we assume that: a. A is a real, constant matrix of order n, whose characteristic roots all have negative real parts; b. / is restricted to be real, measurable, and to have components satisfying the constraints, I fi I < 1.The first condition is the necessary and sufficient condition that all the solutions of (1.1) approach zero as t ->°°.The problem we wish to consider is that of determining the vectors / which, subject to the constraint (b), reduce z to zero in minimum time. This is a problem of Bolza of rather unconventional type, and the techniques we shall employ are quite different from the classical ones.We shall establish two results: The statement in Theorem 1 has been assumed in the past on an intuitive basis, see McDonald, [3] , and has been established in various cases by Bushaw [1] , LaSalle [2] , and Rose [4] . The only paper we have had access to is that by Rose, and his methods are distinct from ours. In addition, he is primarily interested in the case where the condition in (a) is not satisfied.Problems of this type arise in connection with many different types of control processes. A discussion of the connection with servomechanisms is sketched in [2] .2. Proof of Theorem 2. We shall consider in detail only the case of Theorem 2, where the characteristic roots of A are real and negative. It will be clear from the treatment of this case how the proof of Theorem 1 goes.Let X be a square matrix whose columns are the n linearly independent eigenvectors Xj of A, and let X,-(j = 1, • • • , n) be the corresponding n distinct, negative eigenvalues of A; clearly, X is non-singular and all its elements are real. Finally, denote by A the diagonal matrix whose jth diagonal element is X, . We have Axj = XjXj , (whence we see that AX = X A; henceX~'AX = A. (2.2)If now in (2.1) we make the transformation z = Xy, we obtain using (2.2), 2/'(0) = X~\ y'(t) = A y{t) + X"'/(*), (2.3) or, componentwise,y'M) = hyM + £ «.,•/,(<), (2.4)where the «'s are the elements of X-1. Solving for ?/<(£), we obtain yXt) = 2/,(0) exp (X.O + exp (X,<) f exp (-X,s) atif,(s) ds.JO j-1Since z(t) = 0 is equivalent to y(t) = 0, we wish to find the least t for which, for somef, y&) = 0, i = 1, • • • , n, i.e., for which a( n -2/i(0) = / exp (-X,s) E ««/,(•) ds, i = 1, ••• ,n (2.6) Jo i-lOur first observation is that, given any starting value y(0) 0 there exists a t > 0 and an /, such that (2.6) is satisfied. In fact, there is a constant vector /(s) = k which does the trick for some t sufficiently large. For substituting /,(s) = k, in (2.6), we obtain i. y<(Q) Q) 12 It. BELLMAN, I. GLICKSBERG AND O. GROSS [Vol. XIV, No. 1 Theorem 2. If the characteristic roots of A are real, distinct, and negative, a minimizing f exists with components /,• for which \ f{ | = 1, and each /, changes sign at most (n — 1) times. The statement in Theorem 1 has been assumed in the past on an intuitive basis, see McDonald, [3], and has been established in various cases by Bushaw [1], LaSalle [2], and Rose [4]. The only paper we have had access to is that by Rose, and his methods are distinct from ours. In addition, he is primarily interested in the case where the condition in (a) is not satisfied. Problems of this type arise in connection with many different types of control processes. A discussion of the connection with servomechanisms is sketched in [2]." ' -Jo' exp ( -XjS) cfe exp ( -X,£) -1 ' whence, by virtue of the definition of the a's, eg (-M-1-<2'7)Since -A, > 0 the right member of (2.7) can be made as small in magnitude as we please for sufficiently large t, and hence we can insure that | k,-| < 1.For each ( > Owe have a linear mapping p, taking / into the n-dimensional vector with ith component f exp (-X,s) X) «<./.(«) ds, (2.8) Jo i and this mapping clearly takes our basic convex set of f's onto a convex subset C(t) of euclidean n-space. For any / in our basic set there is another, f± in the set which agrees with / for s < t and vanishes for s > t, so that, for t' > t, prf = p,f = p,f, by (2.8), and p,f is in C(t'). Thus C(t) increases with t. Now our desired least time is, by (2.6), the least t > 0 for which C{t) contains the vector -2/(0). Since C{t) increases, we have an interval (t0, 00) for which C(t) contains this vector, while for t < t" this is not the case. We can see that C(t0) also contains this vector as follows.Denoting for any vector x = (xi , x2 , • • • , xn) the euclidean norm (2< a;<)1/2 by || x ||, we obtain, using (2.8), a constant k = k(t0) with the property that for all / and t, t' in a finite interval [0, <0] we have || p,f -prf || < k \ t -t' |; thus, for | t -t' | small every point of C(t') is close to a point of C(t). Since -y{0) is in C(t) for all t > t0 , -2/(0) must be at zero distance from C(t0) so that if we show this set is closed -y(0) must actually be in it. But each C(t) is closed, since by a well known fact about Banach spaces [5] , our basic set of f's may be topologized so as to be compact and render each Pi continuous. Thus C(t), as the continuous image of a compact set, is compact, hence closed.Let us return to the fact that -y(fl) is not in C(t) for t < t0 . From the theory of convex sets [6] this implies that we have a vector 6' of unit norm, for which, in the usual inner product notation, (01, p,f) < [d'; -2/(0)] for every /. Since the vectors of unit norm are compact in the euclidean topology, we may select a sequence tn increasing to to for which d'" converges to some vector 6 of unit norm. But since p,J converges to Pt J, (0, Pi J) = I™ (6'", p,J) < lim [0ln, -t/(0)] = [8, -2/(0)]. Thus if f* denotes an / for which puf* = -y(0) we have (0, p,J) < (0, p,"/*) for all /, hence constants 0, , • • • , 0", not all zero for which /* maximizes the expression X! 0. [ exp (-X,s) X ds = 2Z / (H exp [-X,s])/,(s) ds. (2.9) as one can readily verify by working out the integrals. Moreover, the curve defines an optimal path, since the solution of the differential equation is, with fi = f2= 1 identically, and 2/i(0), 2/2(0) defined as above, precisely a sub-arc of a! beginning at y{0) and terminating at the origin. We shall treat case (3.8c) in detail. Case (3.8d) can be treated similarly, but is a trifle more involved, albeit elementary, and will be omitted on those grounds.We have, upon substituting in (3.6) for case (c):Under the above conditions, an f which reduces z to zero in minimum time exists, and has components for which | /< | = 1. •Received December 10, 1954; revised manuscript received March 14, 1955. It. BELLMAN, I. GLICKSBERG AND O. GROSS [Vol. XIV, No. If the characteristic roots of A are real, distinct, and negative, a minimizing f exists with components /,• for which \ f{ | = 1, and each /, changes sign at most (n -1) times.Fig. 1.Fig. 2.+ 02 < 0, (3.15) 0,x* + 202 > 0, 2/i(0) = 1 -(02/0.)2, 2/2(0) = 3 + 2(02/00 -x*.
About
PublishedApr 1, 1956
TypeArticle
Citations321
References2