THE UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Mathematics Technical Report No. 1 ONE-DIMENSIONAL PROBLEMS OF OPTIMIZATION Lamberto Cesari - ORA Project.024i6,. submitted for: UNITED STATES AIR FORCE AIR FORCE OFFICE OF SCIENTIFIC RESEARCH GRANT NO. AFOSR-69-1662 ARLINGTON, VIRGINIA administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR August 1969

I" I i ' r *.; d ') - I I i

TABLE OF CONTENTS ]iage 1.A. PROBLEMS OF OPTIMAL CONTROL: THE CANONIC PROBLEM 1 1.1. The Canonic Problem of Optimization 1 1.2. Mayer, Lagrange, Bolza Problems 6 1.3. Free Problems, Isoperimetric Problems, and Further Variants of the Canonic Problem 8 1.4. Examples 11 1.5. Systems Where the Strategy is Uniquely Determined by the Trajectory 12 1.B. THE CANONIC PROBLEM IN TERMS OF ORIENTOR FIELDS 15 1.6. Orientor Fields and the Implicit Function Theorem 15 1.7. General Forms of the Implicit Function Theorem 17 l.C. GENERALIZED SOLUTIONS FOR THE CANONIC PROBLEM OF OPTIMAL CONTROL 22 1.8. Generalized Solutions 22 1.9. More on Generalized Solutions 26 l.D. THE GENERALIZED SOLUTIONS IN TERMS OF ORIENTOR FIELDS 30 1.10. Convex Hull of the Set of Directions 30 1.11. Quasi Solutions 31 iii

1.A. PROBLEMS OF OPTIMAL CONTROL: THE CANONIC PROBLEM 1.1. THE CANONIC PROBLEM OF OPTIMIZATION We shall deal here with a real variable t e En, with a real vector variable x = (xl,...,xn) E E, n > 1, and a real vector variable u = (ul,...,u ) n -- e E, m > 1. Here t is the independent variable and is usually called time, and then x is called the space variable (or state, or phase variable), and u i the control variable. Accordingly, x, i = 1,...,n, are the space, or state, or phase coordinates, or variables, and uj, j = l,...,m, the control coordinates, or variablesl. We shall denote by A a given subset of the tx-space E1 x E, and for each (t,x) e A we shall denote by U(t,x) a given subset of the u-space E. We do m not exclude that A coincides with the whole tx-space, and that U(t,x) coincides with the whole u-space. Often U is a fixed subset of E, or U may depend on t only, or on x only. In any case A is called the time-state space, and U(t,x) the control space at time t and state x. We shall denote by M the set of all (t,x,u) with (t,x) e A, u e U(t,x), thus M c E1 x E x E. Note that A is n m the projection of M on the tx-space, while, for each (t,x) e A, U(t,x) is the intersection of M with the linear subspace (t = t,x = x) of E1 x E xE. We n m shall denote by f(t,x,u) = (fi,...,f ) a given vector function defined (at least) on M. Let B be a given subset of the tlxlt2xl- space E2N+2, xl = ), and let g(t,t ) be a given real-valued (x1,...X1), x2 = (x2,...,x2), and let g(tlxlt2,x2) be a given real-valued function defined on B. We shall consider pairs of functions x(t) = (xl,...x ), u(t) = (ul,...,u ), tl < t < t2, satisfying 1

(a) x(t) is absolutely continuous (AC) in [tl,t2], that is, each component x (t) is AC in [tl,t2]; (b) u(t) is measurable in [tl,t2], that is, each component u (t) is measurable in [tl,t2]; (c) (t,x(t)) e A for every t e [tlt2]; (d) u(t) E U(t,x(t)) almost everywhere (a.e.) in [tl,t2]; (e) dx/dt = f(t,x(t),u(t)) a.e. in [tl,t2], that is, dx /dt = fi(t,x(t),u(t)), i = l,...,n, a.e. in [tl,t2]; (1.1.1) (f) (tl,x(tl),t2,x(t2)) e B. Since x(t) is AC, that is, each x (t) is AC in [tl,t2], we conclude that i all dx /dt, and hence all fi(t,x(t),u(t)), i = l,...,n, are L-integrable in [tl,t2]. A pair x(t), u(t), tl < t < t2, as above is said to be admissible, and for such a pair x(t) is called a trajectory, and u(t) a stategy, or control, or steering function. It is then said that u(t) transfers, or steers the state variable x from the value x(ti) at time tl to the value x(t2) at time t2. Also we may say that the trajectory x(t) is generated by the strategy u(t). If x,u is any admissible pair, then we may well say that x is an admissible trajectory, and that u is an admissible strategy. In many applications U depends on t only, the point (tl,(x(tl)) is given and is an interior point of A, and the differential system dx/dt = f(t,x,u(t)) with u(t) measurable and values u(t) e U(t) satisfies local conditions for existence and uniqueness of the solution x(t), at least in a right neighborhood of tl. In this situation (and analogous ones) u(t) determines x(t) 2

uniquely, at least in a right neighborhood of tl. In any case we shall use the terminology above (u transfers x(tl) to x(t2), x is generated by u) even if conditions for uniqueness theorems do not hold. Often U(t,x) is defined for every (t,x) E A by inequalities, as in the examples: (1) m = 1, 0 < u < 1; (2) m = 2, a u1 + b u2 + c < O, s = 1,2,3, S S S I with a, b, c, s = 1,2,3, real given numbers, or real functions of t and x s s s in A. More generally, U(t,x) may be defined by means of inequalities F (t,x,u) s < 0, s = 1,...,N. Because of these and analogous examples, condition (d) is often called a unilateral condition on the control variable u = (ul,...,u ). Often A itself is defined by means of inequalities, as in the examples: (4) 0 < t < 1, x E E; (5) n = 1, a < t < b, c < x < d; (6) n = 2, e t + f xl -- - - n.9 s s + g x2 + h < O, s = 1,2,3, with e, f, gs, h given constants. More gen's s- S S S s erally A may be defined by equalities of the form G (t,x) < 0, s = 1,...,P. Because of these and analogous examples, condition (c) is often denoted as a unilateral constraint on the time-state variables t,x. Condition (f) concerns the end values (tl,x(tl),t2,x(t2)) of the trajectories, in particular the initial values tl,x(tl), and the terminal values t2, x(t2). We shall often denote by r(x) = (tl,x(tl),t2,x(t2)) the ends of the trajectory x. Thus, condition (f) is an abstract form of the boundary conditions for the trajectories. Often B is of the form B1 x B2, and then requirement (f) separates into requirements (tl,x(tl)) E B1, (t2,x(t2)) E B2 concerning initial and terminal values. Often (tl,x(tl)) is a fixed point, that is, B1 is a single point of the tlxl-space. Also, B2 may be called a target. In particular, if t2 is 3

fixed, say t2 = t2o, then B2 = (t2) x B20, where B20 is a subset of the x2-space En, and we may perfer to call B20 a target, to be reached at a fixed time t2 = t20. If t2 is not fixed, assume that B2 can be thought of as the set of all (t,x) with t' < t < tf, x c B(t) c En, B(t) a given subset of E depending on t. Then B2(t) is a "moving target" to be reached in the time interval [tt,tt]. If B2(t) is a single point, say x2(t) E, then we have the problem of joining a given fixed initial point (ti = tlo,xl = x1o) to a given "curve" x = x2(t), t2 < t < te. Often, boundary conditions are assigned by means of a set of inequalities and equalities concerning the (2n+2)-vector T(x)=(tl,x(tl),t2,x(t2)), say b (tl,x(tl),t2,x(t2)) = 0, e = 1,...,kl, e b (t1,x(t1),t2,x(t2))< 0, e = kl + l,...,k1 + k2. Then B is the set of all (2n+2)-vectors (tl,xl,t2,x2) satisfying the same set of kl + k2 relations. The question as to whether we can satisfy the boundary conditions and all the constraints is sometimes a very difficult one. Often it means whether a certain task can be performed at all with the given constraints, that is, in applications, within the limitation inherent to a certain physical plant. The question is often referred to as to whether a given system is controllable. Given all the constraints, say A, B, and U above, the question of controllability is equivalent to the question as to whether the corresponding class of all admissible pairs is not empty. Questions of controllability will be discussed in [ ]. In existence theorems we shall often assume that the class of 4

admissible pairs is not empty, and we shall consider nonempty subclasses Q of admissible pairs. Once a nonempty class Q of admissible pairs x(t), u(t), tl < t < t2, is assigned, we may consider the values taken by the functional I[x,u] = g(tl,x(tl),t2,x(t2)) (1.1.2) in the class Q. Clearly the value of this functional depends only upon the ends r(x) of the trajectory, or I[x,u] = g(r(x)). The functional I[x,u] is often called cost functional, or cost, or performance index. For instance, we may assume tl and xl = x(ti) as fixed, we may leave t2 undetermined, and we may try to minimize the distance of the end point x(t2) from a fixed point x of E. Then g = |x(t2) - x | is of the form (1.1.2). o n o We shall say that a given pair x,u in 92 is optimal, or that x,u gives an absolute minimum for the cost functional I[x,u] in, if I[x,u] < I[x,u] for all pairs x,u in Q. An equivalent way to describe this property is as follows. Let i denote the infimum of I[x,u] in the class 2, or i = Inf I[x,u]. Then an element x,u of the class Q is optimal if and only if, (a) i is finite, and (b) I[x,u] = i. There may be more than one element (x,u) in a which is optimal (for I[x,u] in 2) but the value taken by I[x,u] is the same, namely i. Analogous definitions hold for absolute maxima, but problems of maximum can be reduced to problems of minimum by replacing g by -g. Thus, for the sake 5

of simplicity, we shall always refer to problems of minimum. We have described above the canonic problem of optimization, often referred to as a Mayer problem of optimal control. 1.2. MAYER, LAGRANGE, BOLZA PROBLEMS First, a particular case of the canonic problem above is of interest, that is, the case in which g = t2 - tl or, tl being fixed, simply g = t2. Then the problem of the minimum of I[x,u] = g = t2, is called a problem of minimum time, or a brachistochrone problem. Often the cost functional I[x,u] is given in the form t2 I[x,u] = ft2 f (t,x(t),u(t))dt (1.2.1) tJ 0 where fo(t,x,u) is a real-valued single-valued function defined in M, and? is then restricted to only those admissible pairs for which fo(t,x(t),u(t)) is L-integrable. This is said to be a Lagrange problem of optimization. These problems are readily reduced to Mayer problems by introducing a new state variable x, the new state vector x = (x,x) = (x,x,...,x ), an additional differential equation dx~/dt = f (t,x(t(t)(t)), 0 and an additional initial condition x (tl) = O. Then the functional above becomes I[x,u] = x~(t2), and we have now a Mayer problem with g = x~(t2), and the(n+l)-vector x replacing n-vector x. Again, if we take f = 1 in (1.2.1), 0 then the functional (1.2.1) reduces to I = Jt dt = t2 - tl, and we have a problem of minimum time. 6

Often the cost functional I[x,u] is given in the form I[x,u] = ft2 f (t,x(t),u(t)) + g(tl,x(tl),t2,x(t2)) with fo and g as above. This is said to be a Bolza problem of optimization. Again the same change of variables as above yields I[x,u] = x (t2) + g(tl,x(tl),t2,x(t2)), and we have a Mayer problem concerning the (n+l)-vector x and a new function g = x (t2) + g(tl,x(tl),t2,x(t2)). Actually, Mayer, Lagrange, and Bolza problems are equivalent. Indeed, Mayer and Lagrange problems are obviously particular cases of the Bolza problems above, since they can be obtained by taking fo = O, or g = 0, respectively, in (1.1.4). We have already shown that both Lagrange and Bolza problems can be reduced to Mayer problems. It remains only to prove that Mayer problems can be reduced to Lagrange problems. This can be obtained by introducing an auxiliary variable x, an additional differential equation dx /dt = 0, the boundary condition x0(tl) = (t2 - tl)1 g(tlx(tl),t2,x(t2)), (1.2.5) and the functional J= t2 x (T)dT. tl Since x (T) is constant in [tl,t2] with value (1.2.3), then J = g(tl,x(tl),t2,x(t2)). The canonic (Mayer) control variable u, and functional (1.1.2), is now reduced to a Lagrange problem with state variable x = (x,x) 0 1 n = (x,x,...,x ), control variable u, functional J, and differential system (11.1. ) plus the equation dx0/dt = 0. 7

1.3. FREE PROBLEMS, ISOPERIMETRIC PROBLEMS, AND FURTHER VARIANTS OF THE CANONIC PROBLEM Often problems of optimization are written in terms of the trajectory x only (assumed always to be an AC vector function), and its derivative x', the functional being of the form I[x] = ft2 f (t,x(t),x'(t))dt. (1 1) In this situation we shall retain possible unilateral constraints on the time-state variables, or (t,x(t)) e A, where A is a given subset of the txspace E but we do not require constraints on the values of the derivatives n+l' x'(t). Such a problem is said to be a free problem. For instance, if we take f= (1 + 1u2)/2, u = (u....,u), then I[x] = f2 (1 + Ix'(t)/2)12 dt l~x] = dt, ti and we are looking for a path of minimum length (if any) of the type C: x = x(t), tl < t < t2, x AC in [tl,t2], satisfying the constraints (t,x(t)) C A, and (tl,x(tl),t2,x(t2)) E B. These problems are readily reduced to Lagrange problems by introducing the control variable u =(u,...,u ), (thus m = n), the control space U = E, and the differential system dx /dt = u, i = l,...,n, or dx/dt = u, in other i words, f(t,x,u) = u, or f.(t,x,u) = u, i = l,...,n. Then we have a Lagrange problem with I[x,u] = ft fo(t,x(t),u(t))dt and differential system and constraints (t,x(t)) E A, u(t) e U = E, dx/dt = u n 8

This problem is finally reduced to a Mayer problem as mentioned above. See below for more details and examples. Often, constraints are assigned in the form Ij[x,u] = ft2 gj(t,x(t),u(t))dt = c., j = 1,...,N, that is, by requiring that certain additional functionals take on given fixed values c., j = 1,...,N. These are called isoperimetric problems (or isoperimetric requirements). Again these problems can be reduced to Mayer form by i introducing N additional state variables y, j = 1,...,N, additional differential equations dy /dt = gj(t,x(t),u(t)), j = 1,...,N, and additional boundary conditions yJ(ti) = O, yJ(t2) = c j =1,...,N. Then we have again problems as above concerning the (n+N)-vector x /i n y N = (xl,...,x,y,...,y ). Finally, let us mention that classes Q of admissible pairs are often defined by many kinds of restrictions besides boundary conditions. For instance, we may require that certain components xj(t) take given values at certain fixed points Tlr2,...,TM other than end points, or that the trajectory x(t) passes through given points xl,...,xM at certain fixed points T1,T2,...,TM as before. More generally we may assume that the trajectory x(t) passes through given sets B1,...,BM at certain fixed points T1,...,TM as before, or tK < T1 < T2 <... < TM < t2, x(T ) E B, s =,..,M. jyi s s 9

Finally, the points T1,...,TM may be variable and required to satisfy certain requirements. It happens that these requirements can be often expressed in the abstract form (to, T1,...TM, t2,X(tl),X(T1),...X(TM),X(t2)) E B, where B is a given subset of a Euclidean space of suitable dimension. The differential system (1.1.1) relates trajectories and strategies to each other. In applications, a given physical system is said to be monitored, or regulated, by the differential system (1.1.1), and in some cases (1.1.1) is said to represent the physical plant, or briefly the plant. Note that the differential system (1.1.1) may be linear in u, dx/dt = B(t,x) u + C(t,x), or linear in x, dx/dt = A(t,u) x + C(t,u) or may take more particular forms, as dx/dt = A(t) x + B(t) u + C(t), or dx/dt = Ax + Bu + C(t), where A,B,C here represent matrices of the types n x n, n x m, n x 1. respectively, whose entries may be constant or depending upon the variables just indicated. 10

For free problems, as mentioned, the differential system is reduced to dx/dt = u (or f = u with m = n, U = E ). 1.4. EXAMPLES The problem of the (nonparametric) curve of minimum length of the tx-plane E2 joining two given points 1 = (tl,xl), 2 = (t2,x2), tl < t2, is usually written as a free problem with functional I = t2 (1 + X2)1/2 dt tl and boundary conditions x(tl) = xl, x(t2) = x2 tl,t2, xl,x2 fixed, tl < t2. The same problem can be written as a Lagrange problem with n = 1, m = 1, functional I = t2 (1 + u2) 1dt tI and differential equation and boundary condition dx/dt = u, x(tl) = xl, x(t2) = x2 The same problem can be written as a Mayer problem with n = 2. m = 1, functional I = y(t2), and differential equations and boundary conditions dx/dt = u, dy/dt = (1 + u2)1/, x(tl) = xl, x(t2) = x2, y(tl) = 0. Any Mayer problem of minimum time (I = t2 - tl, or I = t2 if tl is fixed) is equivalent to a corresponding Lagrange problem with f (tx,u) = 1. The isoperimetric problem with n = N = 1, x(tl) = O, x(t2) = 0, tl < t2, A = [tl < t < t2, x > O], I = 2 x dt maximum, J =t2 (1 + x'2) dt = L, _ —ti tt with t2 - tl < L < i(t2 - t1)/2, is equivalent to the Mayer problem with n = 3, m = 1, x(tl ) = O, x(t2) = 0, y(tl) = O, z(t2) = O, A = Itl < t < t2, 11

1/2 x > 0, y > 0, z > O], U = [-oo < u < + o], dx/dt = u, dy/dt = (1 + u2) dz/dt = x, I = z(t2) = maximum. 1.5. SYSTEMS WHERE THE STRATEGY IS UNIQUELY DETERMINED BY THE TRAJECTORY Let us note first that, given an admissible pair x(t), u(t), t1 < t < t2, the trajectory x may not determine uniquely the strategy u. This occurs, for instance, for x' = u2 with n = m = 1, and control space U = [-1 < u < 1]. The trajectory x(t) = t, 0 < 1 < 1, is generated by the strategy u(t) = 1, 0 < t < 1, but also by u(t) = -1, 0 < t < 1, as well as by any other measurable function u(t), 0 < t < 1, with values u(t) = ~1. There are important situations, however, where the trajectory x of any admissible pair x(t), u(t), t1 < t < t2, determines uniquely the strategy u (a.e. in [tl,t2]). In other words, an admissible trajectory x determines uniquely the corresponding strategy u. These systems, or problems, may be denoted sometime as systems TDS (trajectory determining the strategy). This certainly occurs for (usual solutions) of free problems (m = n, f = u, U = E ) since then (1.1.1) reduces to u = dx/dt, and the strategy u = x' is uniquely determined by the trajectory (a.e.). This does not mean that the trajectory x is arbitrary, even in free problems! For instance, in the free problem of the minimum of I= f1 x. 2 dt with = = 1, A = E2, x(O) =, x(l) = 1, the AC function x = tl/2, 0 < t < 1, is not an admissible trajectory since x'2 is not L-integrable in [0,1]. Another case of TDS systems is represented by problems monitored by a differential equation of order n, say linear and of the form, 12

dyn/dtn + al(t) dn1 y/dtn-1 +...+ a (t) y = u in the scalar functions y, and where u is a scalar strategy. By the canonic n (n-i) substitution x' = y, x2 = y',.. = y, we obtain a system (1.1.1) of the form dx /dt = x2,..., dxn/dt = x-an(t)x -...- al(t)x + u, and again the strategy u is uniquely determined by the trajectory x, u(t) = dxn/dt + a (t)xl +...+ al(t)x (a.e.) An analogous case of systems TDS is represented by problems depending on higher derivatives, or the problem of the minimum of I = t2 fo(t, y(t), y'(t),...,y(n)(t))dt ti 0 (n-i) for scalar functions y which are AC together with y',...,y, satisfying constraints of the form (t, y(t),...,yy (t)) E A, and (tl,y(tl),..., y(1)(tl), t2, y(t),...,y(n-)(t2)) e B where ACEn, BCEn +2 are fixed sets, (n) and there are no constraints on y ion x 2 = yl...~n (n-l)= 1= y(n) By the canonic substitution x= y x = yl,...,x = y, u = y( (t), we see that the problem above is transformed into a Lagrange problem concerning the minimum of the functional I = t2 f (t, x(t), u(t))dt, with state variable x = (xl,...,x ), control variable u, m = 1, U = El, differential system dxl/dt = x2.. dx /dt = x dx /dt = u, constraints (t, x(t)) E A, (tlt(tl),t2,x(t2)) E B. Thus any admissible trajectory deter

mines the corresponding strategy uniquely u(t) = dx /dt. An example of an analogous situation is the problem of the minimum of I = t f (t, y(t), (Lg)(t))dt, tc o with constraints analogous to those of the previous case, and where L is a differential operator of order n. Then the cost functional can be written in the usual form I = t2 f (t, y(t), u(t))dt, tj 0 with the same constraints and differential equation (Lx)(t) = u(t). Again an admissible strategy certainly determines the strategy u uniquely. Another case of TDS systems occurs whenever m < n, systems (1.1.1) has the linear form dx/dt = B(t,x) u + C(t,x), tl < t < t2, (1.5.1) and the n x m matrix B(t,x) has always maximal rank m. Then, for t in [tl,t21 (a.e.), u(t) = (u,...,u ) can be recovered by linear operations from the nvector dx/dt - C(t, x(t)) and the n x m matrix B(t, x(t)). In harmony with the previous considerations, we assume here x(t) AC and the matrices B and C with continuous entries.

1.B. THE CANONIC PROBLEM IN TERMS OF ORIENTOR FIELDS 1.6. ORIENTOR FIELDS AND THE IMPLICIT FUNCTION THEOREM Let us consider again the canonic problem of optimization of (1.1). For every (t,x) e A let us denote by Q(tx) the set of all z = (zl,...,z ) E E such that z = f(t,x,u) for some u E U(tx), or z = f.(t,x,u), u e U(t,x), in symbols Q(t,x) = [z E E Iz = f(t,x,u), u E U(t,x)] = f(t,x,U(t,x)). The last notation is most common, since it states that Q(t,x) is the image in E of the set U(t,x) of E, image obtained by means of the vector function n m f(t,x,u) = (f,...,fn). For every admissible pair x(t), u(t), tl < t < t2, we have dx/dt = f(t,x(t),u(t)), u(t) E U(t,x(t)) a.e. in [t,t2], (t,x(t)) E A for all t E [tl,t2], and these relations obviously imply dx/dt E Q(t,x(t)) a.e. in [tl,t2], (t,x(t)) E A for all t E [tl,t2] This remark obviously suggests that instead of the differential system and constraints dx/dt = f(t,x,u), (t,x) E A, ue U(t,x), (1.6.1) we simply write 15

dx/dt e Q(t,x), (t,x) e A. Relations (1.6.1) and (1.6.2) mean that at every point (t,x) E A we can choose any direction dx/dt of the set Q(t,x). In other words, x at every point (t,x) E A we have a possible set of dix.- rections dx/dt e Q(t,x) instead of only one direction, 1.~ say dx/dt = F(t,x) as for usual differential systems. t ~t ~ We say that (1.6.2) defines an orientor field in A. This term is the analogue of "direction field" as defined by usual differential systems (in normal form). We have shown above that for every admissible pair x(t), u(t), t < t < t2, the trajectory x(t), ti < t < t2, can be interpreted as an (AC) solution of the orientor field (1.6.2) (satisfying boundary conditions (f)). Conversely, every AC solution of the orientor field (1.6.2) (satisfying (f)) can be interpreted as a solution of the differential system (1.6.1), precisely, there exists a measurable vector function u(t), ti < t < t2, with u(t) e U(t,x(t)), dx/dt = f(t,x(t),u(t)) a.e. in [tl,t2]. In other words, to every solution x of the orientor field (1.6.2) (satisfying (f)) we can always associate some measurable vector function u such that x, u is an admissible pair. This statement can be proved under very mild hypotheses, indeed it suffices to know that both A and M are closed sets, (A c E +1,M c E+ ). Precisely, we shall prove below the simple statement: (1.6.i) Implicit Function Theorem for Orientor Fields. If A is a closed subset of the tx-space En+l if U(t,x) is a subset of E for every (t,x) e A, and the set M of all (t,x,u) E E+m with (t,x) e A, ue U(t,x) is closed, if n+l+m 16

x(t), t1 < t < t2, is an AC vector function such that (t,x(t)) e A for all t e [tl,t2] and x'(t) e Q(t,x(t)) for almost all t e [tl,t2], then there exists a measurable function u(t), t1 < t < t2, such that u(t) E U(t,x(t)) and x'(t) = f(t,x(t),u(t)) for almost all t e [tl,t2]. Note that A is the projection of M on the tx-space, and that for every (t,x) e A the set U(t,x) is the intersection of M with the subspace [t = t,x = x] in E+l+m Thus, the assumption that M is closed certainly implies that U(t,x) is a closed subset of E. Thus, for every (t,x) E A, the set U(t,x) is necm essarily closed. The above shows that, under very mild hypothesis (f continuous on M and M closed) the usual requirements (1.6.1) can be written in the equivalent form of an orientor field (1.6.2), and vice versa. Statement (l.6.i) will be proved in (1.7) below. 1.7. GENERAL FORMS OF THE IMPLICIT FUNCTION THEOREM A real single-valued function f(x) defined on a metric space x is said to be lower [upper] semicontinuous at the point x e X provided f(x ) < lim f(x) as x + x in X[f(x ) > lim f(x) as x + x in X]; in other words, provided, given ~ > 0, there is some 6 = b(~,x ) > 0 such that f(x) > f(x ) - E [f(x) < f(x ) + E] for all x e X whose distance from x is < s. The same function o o - f is said to be lower [upper] semicontinuous in X if f is lower [upper] semicontinuous at every point of X. (1.7.i) Every real single-valued function f(x) lower [or upper] semicontinuous in the metric space X is B-measurable. Indeed, for every real number a the set of points x E X where f(x) > a 17

[f(x) < a] is open in X (cfr. Kelley [ ], p. 119 and p. 40). (1.7.ii) Every function f(x) lower [upper] semicontinuous in the compact metric space X has an absolute minimum [absolute maximum] in X. Proof. Suppose f(x) is lower semicontinuous in the compact metric space X, let m = Inf f(x) for all x E X and let [x k] by any sequence of points xk E X with f(xk) + m as k oo. Since X is compact, there is at least one point x c X k o and a subsequence [x ] such that x + x as s oo. Since f(x) is lower semiks ks o continuous at x, given E > 0 there is some & > 0 such that f(x) > f(x ) - E O' o for all x E X at a distance < 5 from x. Thus f(x ) > f(x ) - for all s o ks o sufficiently large, and f(xk ) m implies m > f(x ) - ~, and thus m is finite. Since this relation holds for all E > O, we have m > f(x ). On the other hand, x e X, and hence m < f(x ). By comparison, we conclude that m = f(x ), and thus f has an absolute minimum in X. Analogous reasoning holds for upper semicontinuity and the existence of an absolute maximum. (l.7.iii) Given any two metric spaces X, Y of which X is the countable union of compact subspaces of X, let f: X - Y be any continuous mapping, and let Y = f(X) be the image of X in Y. Then, there is a B-measurable map c: Y + X such that fcp is the identity map on Y, that is,f[p(y)] = y for every y E Y. Proof. (a) Let us suppose that X is replaced by a closed set L c [O,+oo]. In this situation, let T(y) = Inf f-l(y) for y E Y. Here f-l(y) is a nonempty set of real nonnegative numbers, and the operator Inf applies. Actually, f is a continuous map, hence f-l(y) is a closed nonempty subset of [0,+oo], and hence f-l(y) has a minimum, or T(y) = Min f-l(y), hence T(y) E f-(y), and

f[Ty)] = y for every y E Y. Let us prove that T: Y - L is a lower semicontinuous 0 ^f""^7<^"^ (real single-valued) function. Suppose this X = L T is not the case. Then, there is a point y e Yo a number E > 0, and a sequence [yk] such that yk E Y, yk - y, T(Yk) < T(Yo) - e, or < Xk < x - ~, with xk = T(k), f(xk) = k X = T(Y), f(x) = y Here [xk] is a bounded sequence, hence there is a subsequence, say [xk ] with xk - x s s with 0 < x < x - ~. Here xk = T(Yk ) e L, and thus x E L since L is closed. - - o k k s s Also, f(xk f(T(k )) =k + Y Xk x, hence f(x) =y since f is conS S s S tinuous on L. Thus, x e fl(y ) < x - ~, a contradiction, since x = Min 0 - 0 0 fl(y ). We have proved that T: Y + L is lower semicontinuous in Y, hence 0o o0 B-measurable because of (1.4.i), and f(T(y)) = y for every y E Y. Statement (1.4.iii) is proved for X replaced by any closed subset L of [0,+oo]. (b) Let us consider now the general case. By hypothesis X = U X, where X, a = 1,2,..., is a sequence of compact subsets of X. By general topology (Hocking and Young [ ], Th. 3.28) we know that each X is the continuous image i L -+ X, a 1,2,..., of some closed subset L of [0,1], say L c [~,1 - E] a a a a 1a for some ~ > O. Let us denote by L the set which coincides with L' = a + L a a in [a,a + 1], that is, the displacement L' of L in [a,a + 1]. Then L is a closed subset of [0,+oo) and we shall denote by i: L X the map which coincides with ~ on L'. Then I is a continuous map of L onto X. We have the situation T L > fY L -> X -> Y, 19

and, by force of (a), there is a B-measurable map T: Y + L such that (f~)(T(y)) = y for every y E Y, or (f~T)(y) = y, since f~ is a continuous map, and Y = f(X) = f(e(X)) = (f~)(X). If we take = T, cp: Y + X, we have o 0 f(cp(y)) = y for every y E Y. Obviously, cp is a B-measurable map as the superposition of a continuous map I on the B-measurable map T. Statement (1.7.iii) is now completely proved. (c) We are now in a position to prove the implicit function theorem (l.6.i). As usual we denote by M the set of all (t,x,u) with (t,x) e A and u e U(t,x), hence M c E+n+m. Also, we denote by N the set of all (t,x,z) with (t,x) e A, z = f(t,x,u), u e U(t,x), hence N c E1+2. Let F: M - N denote the continuous map defined by (t,x,u) + (t,x,z) with z = f(t,x,u). Here M and N are metric spaces since M E+n+m N c E+2n; also, M is closed by hypothesis, and M is the countable union of compact subsets, say M = [(t,x,u) e M |t[ + Jx| + Jul < a], a = 1,2,.... Finally, N = F(M). By force of (1.7.iii), there is a B-measurable map p: N -+ M such that Fcp is the identity map, that is, Fp(t,x,z) = (t,x,z) for every (t,x,z) e N. Now, let us consider the map a: I - N on (^ —P ~I = [tl,t2], defined by t - (t,x(t),x'(t)), M ----- N k F 1 where x(t), t1 < t < t2, is an AC solution of lz\ /ao~ ~ the orientor field x' E Q(t,x) = f(t,x,U(t,x)). ^~I ~ Then = cpa: I+M, and * maps t into some (t,x(t),u(t)) E M, with F(t,x(t),u(t)) = (t,x(t),x'(t)), or x'(t) = f(t,x(t),u(t)). Actually, a is defined not on all of I, but in the subset I of I where x'(t) exists, and meas I = meas I = t2 - tl, and thus the concluding relation holds in I, that is '(t) = f(t,x(t),u(t)) a.e. in n the other hand, x'(t) is measis, x'(t) = f(t,x(t),u(t)) a.e. in [tl,t2]. On the other hand, x'(t) is meas 20

urable, that is, a is measurable, cp is B-measurable, hence u(t) is measurable. The implicit function theorem (l.6.i) is thereby proved. Statement (l.6.i) we have just proved is the form we shall use in this exposition of a type of statementswhich have been given the name of implicit function theorems. Statements (1.7.iv) and (1.7.v) below are two more examples of such statements. (1.7.iv) Let M be a topological space which is the countable union of compact metrizable subsets, let N be a Hausdorff space, and I a measure space. Let f: M > N be a continuous map, and a: I - N a measurable map such that a(I) c f(M). Then there exists a measurable map 4: I - M such that f(r(x)) = a(x) for all x e M. (1.7.v) Same as (1.7.iv) when M is a separable metric space. For the proof of these statements we refer to E. J. McShave and R. B. Warfield F ]. For other inplicit function theorems see C. Castaing [ ]. 21

1.C. GENERALIZED SOLUTIONS FOR THE CANONIC PROBLEM OF OPTIMAL CONTROL 1.8. GENERALIZED SOLUTIONS Often a given problem has no optimal solution, but the mathematical problem and the corresponding set of solutions can be modified in such a way that an optimal solution exists and yet neither the system of trajectories, nor the corresponding values of the cost functional are essentially modified. The modified (or generalized) problem and its solutions are of interest in themselves, and have often relevant physical interpretations. Besides, generalized solutions can be thought of as limits of usual solutions in a suitable topology. Here we introduce generalized solutions as usual problems involving a finite number of ordinary strategies which are thought of as being used at the same time according to some probability distribution (Gamkrelidze's chattering states). Briefly, instead of considering the usual cost functional, differential system, boundary conditions, and constraints I[x,u] = g(tl,x(t),t2, x(t2)), dx/dt = f(t,x(t),u(t)), f = (fl,.,fn) (1.8.1) (tl,x(tl),t2,x(t2)) e B, (t,x(t)) E A, u(t) E U(t,x(t)), we shall consider new cost functional differential system, boundary conditions, and constraints I[x,p,v] = g(tl,x(t1),t2,x(t2)), 22

dx/dt = h(t,x(t),p(t),v(t)), h = (hl,...,hn ), (1.8.2) (tl,x(tl),t2,x(t2)) e B, (t,x(t)) E A, v(t) E V(t,x(t)), p(t) e r Precisely, v(t) = (u ),...,u )represents a system of some y ordinary strategies u(1)(t),...,u()(t), each u(j)(t) having its values in U(t,x(t)) c E. m Thus, we think of v = (u( ),...,u() are themselves vectors u with values in U(t,x). In other words, (u(1) (7)) (J) E U(t,),...,, v = (u,...,u ), u U(x), j =, or v e V(t,x) = [U(t,x)]7 = U x *'. xU c E, (1.8. my where the last term is the product of U by itself taken y times, and thus V is a subset of the Euclidean space E. In (1.8.2) p = (pi,...,P ) represents a probability distribution. Hence, p is a point of the simplex F of the Euclidean space E defined by pj > 0, pi + *- + p = 1. Finally, in (1.8.2) the new control variable is (p,v) with values (p,v) e r x V(t,x) c E. In (1.8.2) y+my7 h = (hl,...,h ) and all gi are defined by h (t,x,p,v) = Z p fi(txu ), i,2,...,n. j=1 or o 7 (j) h(t,x,p,v) = p.f(t,x,u(). (1.8.4) j=l The new control variable (p,v) is thus an (my+7)-vector. Note that h in (1.8.4) can be thought of as a convex combination of f(t,x,u(j)), j = 1,...,y, with coefficients pj. On the other hand, Pi,...,P can be thought of also as with~~~ 7ofiinsp 23

probabilities. A generalized solution x(t), p(t), v(t), t1 < t < t2, or an admissible system, is now a system of functions x, p, v satisfying (a) x(t) is AC in [tl,t2]; (b) p(t), v(t) are measurable in [tl,t2]; (c) (t,x(t)) e A for every t e [tlt2]; (d) p(t) E r, u(j)(t) E U(t,x(t)) for almost all t e [tl,t2]; (e) dx/dt = h(t,x(t),p(t),v(t)) for almost all t E [tl,t2]; (f) (tl,x(tl),t2, x(t2)) C B. Then x(t) is said to be a generalized trajectory generated by the generalized strategy p(t), v(t), that is, by the y usual strategies u( (t) with probability distribution p(t), tl < t < t2. It is essential to show that every usual solution can be interpreted as a generalized solution. Indeed, if we take pi = 1, P2 = * = p = O, u = u() then obviously all relations (1.8.2), (1.8.3) reduce to relations (1.8.1). If ve denote by Q the class of all usual admissible pairs x(t), u(t), t1 < t < t2, and by Q* the class of all admissible generalized systems x(t), p(t), v(t), t1 < t < t2, then we have just proved that 2 c ~*. If j denotes the infimum of I[x,p,v] = g(q(x)) in Q), then j < i. As we shall see in the future we have j = i under very weak assumptions (usually satisfied in most applications)' Under the same hypotheses we shall prove also that generalized trajectories can be uniformly approximated by usual trajectories, and that the family of generalized solutions represents the closure in a suitable topology of the family of usual solutions. Under suitable hypotheses, the set of generalized solutions will be proved to be compact

the same topology [(2.7) and App. F]. We shall denote by R(t,x) the set of all z = (z,...,z ) e E with z = h(t,x,p,v) for p e r, v e V(t,x). In view of (1.8.4) R(t,x) is made up of convex combinations of y points of Q(t,x). We shall choose for 7 the minimum integer such that R(t,x) is the "convex hull" of Q(t,x), or R(t,x) = co Q(t,x) for all (t,x) e A Such number y is always < n + 1. Any higher values of y will give rise to the same set R(t,x) and, as we shall see below, will not produce essentially any new trajectory. An Example. We give here an example of a problem which has no optimal usual solution but one well determined optimal generalized solution. Let m = 1, n = 2, A = E2, U made up of the two points u = +1 and u = -1. Let us consider the differential equations dx/dt = y2, dy/dt = u, boundary conditions x(O) = 0, y(O) = y(l) = 0, and functional I[x,y,u] = g = x(l). Since x(O) = 0, dx/dt = y > 0, we have x(l) > 0. If i denotes the infimum of I[x,y,u] in the class Q of all admissible pairs x(t), y(t), u(t), 0 < t < 1, then i > 0. On the other hand, let xk(t), yk(t), uk(t), 0 t < 1, k = 1,2,..., be the sequence of admissible pairs defined by uk(t) = +1 for j/k < t < j/k + 1/2k, uk(t) = -1 for j/k + 1/2k < t < (j + 1)/k, j = 0,1,...,k - 1, hence yk(t) = t - j/k and Yk(t) = (j + 1)/k - t for t in the corresponding intervals, then 0 < Yk(t) < 1/2k, 0 < y2(t) < 1/4k2 for all 0 < t < 1, and xk(l) < 1/4k2. Thus 1/2k, 0 - k K 0 < I[xk, Yk,uk] < 1/4k2 and I[xk, Yk, Uk] > as k + +0. This proves that i = O. For no admissible pair x(t), y(t), u(t), 0 < t < 1, we can have I[x,y,u] = 0, since this would imply x(l) = 0, x(t) = 0 for all 0 < t < 1, 25

y(t) = 0 for all 0 < t < 1, and finally u(t) = 0 a.e. in [tl,t2], a contradiction, since u = -1. We have proved that the problem above has no optimal usual solution. The corresponding generalized problem with y = 2 has now differential equations dx/dt = y2, dy/dt = plu )+ p2u, boundary conditions x(O) = 0, y(O) = y(l) = 0, functional J = g = x(l), and here u () u ) l= 1 P > 0, P2 > 0, pi + P2 = 1. Since w = plu() + 2u() takes on all possible values between -1 and +1, we can replace the second equation by dy/dt = w with w = W = [-1 < w < 1]. The obvious optimal solution is here x(t) = 0, y(t) = 0, w(t) = 0 for all 0 < t 1, or u() = -1, u() = +1, pi = 1/2, P2 = 1/2 for all 0 < t < 1. Here the infimum of J is still zero, and J _ —~~~~~ - ~~~~min = j = i = 0. 1.9 MORE ON GENERALIZED SOLUTIONS We have given above the definitions concerning generalized solutions for the canonic, or Mayer, problem. For solutions written in the Lagrange form I[x,u] = Jt2 f (t,x,u)dt, U 0 dx/dt = f(t,x,u), (t,x) c A, u e U(t,x), r(x) E B, x = (x1,.,x ), f= (f,...,f ), u = (u1,...,u the corresponding generalized problem is I[x,p,v] = Jt2 h (t,x,p,v)dt, (1.9.1) dx/dt = h(t,x,p,v), (t,x) e A, (p,v) E x V(t,x), T(x) e B, (1.9.2) where x = (x1,...,x ), h = (hl,...,h) n) 26

v (U),,U). u(, = (uj,...,um) e U(t,x), j = 1,...,, P = (P1,...,P ) r - [PPj > O, j = 1,...,7, Pi + + P 1] 7 (j) hO(t,x,u) = Z pfo(t0xK u ), j=l 7 (j) h(t,x,u) = Z p.f(t,x,u j=l J By reducing this problem to the Mayer form by the device mentioned in (1.2) we obtain a generalized Mayer problem as in (1.5) above. Analogously, for free problems I[x] = t2 f (t,x,u)dt, x' = u E U = E tjo n m = n, x = (xl,...,x ), (x) e B, we obtain the corresponding generalized free problem by taking t2 I[x,p,v] = Jt2 h (t,x,p,v)dt, (1.9.3) dx/dt = plu(i).+ p u() (1.9.4) where n x = (x1,...x), (p,v) e r x En, r(x) E B, P = (Pi,-,P P,) E r = [pip > 0, j =,...,7, Pi + p = 1] v = (u)...,u (), u(j) U = E, j = 1,...,, n~ h (t,x,p,v) = Z p.f (t,x,u. j=l 27

Note that, while for usual solutions of free problems the trajectory determines the strategy since dx/dt = u (that is, they form a TDS system (1.5)), this is not the case for generalized solutions of free problems, where the strategy p(t) = (Pl,...,P ), v(t) = (u (Jt), j = 1,...,y), tl < t < t2, is certainly not determined by the relation dx/dt = pu( +... + p u(, with p e r, u e E. For instance, again for the free problem of the minimum of n I = J x'2 dt, the trajectory x = 0 can be generated by any generalized strategy p(t) = (p,P2), v(t) = (u 1),u )) with 0 = pi ul + P2 u, say pi p2 = 1/2, u(1) = 1, as well as say byp = 1/5, P2 = 2/, u() = 2, (2) U^ = -1. An Example. We consider here the free problem of minimum of I = j1 (x2 + Ix'2 -1|)dt 0 with n = 1, x(O) = O, x(l) = O. Here x2 + Jx'2 -l| > 0, hence I > 0, and, if i denotes the infimum of I in the class Q of all AC functions x(t), 0 < t < 1, with x(O)-= O, x(l) = 0, and such that I is finite, then certainly i > O. Let us consider now the sequence [xk] of trajectories defined by xk(t) = t - j/k for j/k < t < j/k + 1/2k, xk(t) = (j + l)/k - t for j/k + 1/2k < t < (j + l)/k, j = O,l,...,k - 1, then 0 < xk(t) < 1/2k, x'(t) = +1 a.e. in [0,1], and 0 < I [xk] < 1/4k2. Thus I[x ] > 0 as k * o, and hence i = O. Obviously there k k is no AC function x(t), 0 < t < 1, with x(O) = x(l) = 0 and I[x] = O, since this would imply x(t) = 0 for 0 < t < 1, x'(t) = +1 a.e. in [0,1] a contradiction. This proves that the problem above has no absolute minimum in n. The corresponding generalized problem concerns the minimum of J = (x2 + l(u )) - 11 + p ((2)u)2 - l)dt 0 28

with x(O) = O, x(l) = 0, pi > 0, P2 > O, pi + P2 = 1, and differential equation (1) (2) (i) U(2) dx/dt = plu1) + p2u, u,u E E1. Obviously w = plu () + p2u(2) can take any possible value in E1 as u = x' in the original free problem. If j denotes the infimum of the new functional J then obviously j > 0 since the integrand is still nonnegative. On the other hand, j < i = 0 since the class Q of generalized solutions contains the class Q of usual solutions. Thus, j = i = O. An optimal solution is obviously given by u(1)(t) = 1, u (t) = -1, pl(t) = 1/2, p2(t) = 1/2, 0 < t < 1, hence dx/dt = O, x(t) = 0 in [0,1], and J = j = i =. 29

1.D. THE GENERALIZED SOLUTIONS IN TERMS OF ORIENTOR FIELDS 1.10. CONVEX HULL OF THE SET OF DIRECTIONS We consider now generalized solutions for the canonic problem as defined in (1.8), where we have already introduced the sets R(t,x) = co Q(t,x), (t,x) e A, with R(t,x) = h(t,x,,V(t,x)). For every admissible generalized system x(t), p(t), v(t), tl < t < t2, we have dx/dt = h(t,x(t),p(t),v(t)), p(t) E r, v(t) E [U(t,x(t))]7 a.e. in [tl,t2], (t,x(t)) e A for all t E [tlt2], and these relations obviously imply dx/dt E co Q(t,x(t)) a.e. in [t,t2], (t,x(t)) E A for all t E [tl,t2] In other words, instead of the differential equations and constraints dx/dt = h(t,x,p,v), (t,x) E A, v e [U(t,x)]7, p e r, (1.10.1) we simply write the orientor field dx/dt e co Q(t,x), (t,x) E A. (1.10.2) We have shown that for any admissible generalized system x(t), p(t), v(t), tl < t < t2, the generalized trajectory x(t), tl < t < t2, can be interpreted as an (AC) solution of the orientor field (1.10.2) (satisfying boundary conditions (f)). Conversely, every AC solution of the orientor field (1.10.2)

(satisfying (f)) can be interpreted as a solution of the differential system (1.10.1), precisely, there exist measurable vector functions p(t), v(t), tl < t < t2, with p(t) E r, v(t) E U(t,x(t)) = [U(t,x(t))]7, dx/dt = h(t,x(t), p(t),v(t)) a.e. in [tl,t2], or x(t), p(t), v(t), t1 < t < t2, is an admissible generalized system. This can be proved under very mild hypotheses. Precisely, the following statement holds: (1.10.i) Implicit function theorem for the orientor fields of generalized solutions (1.10.2). If A is a closed subset of the tx-space E+1' if U(t,x) is a subset of E for every (t,x) e A, and the set N of all (t,x,p,v) e m Enl+mm with (t,x) e A, p e F, v e V(t,x) = (U(t,x))7, is closed, if x(t), t1 < t < t2, is an AC vector function such that (t,x(t)) e A for all t E [tl,t2] and dx/dt E co Q(t,x(t)) for almost all t e [tl,t2], then there exist measurable functions p(t), v(t), t t t, such that p(t) (t), v(t) V(t,x(t)) = (U(t,x(t))7, and dx/dt = h(t,x(t),p(t),v(t)) for almost all t e [tlt2]. This statement is simply a corollary of (1.6.1) and is obtained by applying (1.6.1) to the generalized problem (1.10.1). We have shown that, under mild hypotheses (A closed, N closed) the generalized solutions can be written in the equivalent form of the orientor field (1.10.2), and vice versa. 1.11. QUASI SOLUTIONS Relations (1.6.2) and (1.10.2) lead to the following further extension of the concept of trajectory. Let us denote by S(t,x) the closed convex hull of Q(t,x), or

S(t,x) = cl R(t,x) = cl co Q(t,x), so that obviously S(t,x) D R(t,x) D Q(t,x). Whenever R(t,x) is known to be closed, then S = R. In particular, if Q(t,x) is compact, then R(t,x) = co Q(t,x) is known to be compact, hence closed, and S = R. In general, S(t,x) may well be larger than R(t,x). We shall say that x(t), t1 < t < t2, is a quasi solution provided (a) x(t) is AC in [tl,t2], (b) (t,x(t)) e A for all t e [tl,t2], and (c) dx/dt e cl co Q(t,x(t)) for almost all t e [tl,t2] It is clear that a generalized solution is a quasi solution. Whenever R(t,x) is closed, hence S(t,x) = R(t,x), then any quasi solution is a generalized solution. In general it may well occur that a quasi trajectory is not a generalized trajectory. For instance, if S(t,x(t)) is actually larger than R(t,x(t)) for all t of a set H c [tlt2] of positive measure and dx/dt e S(t,x(t)) - R(t,x(t)) for all t e H, then clearly x(t) cannot be a generalized trajectory. A simple example of this occurrence is as follows. Let n = 1, m = 1, and consider differential equations, boundary conditions, and constraints: dx/dt = (u + l)-1, x(O) = 0, u e U = [0 < u < +o] and let us seek the minimum of the functional I[x,u] = x(l). Here Q(t,x) is the half closed half open segment Q(t,x) = [z|O < z < 1], hence Q is convex but not closed. Hence R(t,x) = Q(t,x) is also convex and not closed. Finally S(t,x) = [z|O < z < 1] is the corresponding closed segment. The problem has

no usual optimal solution since I is positive, can be made as small as we want, but not zero. The problem clearly has no optimal generalized solution either, but there is an optimal quasi solution, namely x(t) = 0, 0 < t < 1, for which I = 0. 33

UNIVERSITY OF MCHAN 3 9015 02844 9356