T HE U N I V E R S I T Y OF M I C H I G A N COLLEGE OF LITERAT'URE, SCIENCE, AND THE ARTS Department of Mathematics Technical Report No. 1 PROBLEMS OF OPTIMIZATION Lamberto Cesari ORA Project 010582 submitted for: UNITED STATES AIR FORCE AIR FORCE OFFICE OF SCIENTIFIC RESEARCH GRANT NO. AFOSR-71-2122 ARLINGTON, VIRGINIA administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR November 1971

-I "it if.V/ e ", A, i i I I A.-I, ",% b - v ---,)- "I"Y" , <_', 11 e_

1.1 1. PROBLEMS O1' OPTIMIZATION 1.1 Problems of optimization We shall be concerned with a real variable t c E1 (time, the independent 1 n variable), with a real vector variable x = (x,...,x ), x c E, n 1, (state variable), and with a real vector variable u = ( u, E, m > 1, (control variable). In a canonic, or Mayer problem we seek the minimum, or the maximum, of a functional I[x,u] g(tl, x(tl), t2, x(t2)) (1.1.1) 1 n ut)in a suitable class Q of pairs of functions x(t) = (x,...,x ), u(t) = 1 m (u,...,u ), t < t < t2, satisfying a system of ordinary differential equations dx/dt = f(t, x(t), u(t)), t c [tl,t2] (ae.), constraints (t, x(t)) c A, t E [tl,t2] (1.1.3) u(t) c U(t, x(t)), t [t,t2] (a.e.), ( and boundary conditions

1.2 Here A is a given subset of the tx-space E (which may coincide with n +1 the whole space IF +1)' 1 a given subset of the t lt x 2-space 14' 1 n 1 n x1 -(x,...,xl), x2 (x,...,x2), and for every (t,x) c A a subset U(t,x) of the u-space E is given (which may actually be fixed, or coincide with the m whole space E, or depend on t only, or on x only). If M denotes the set of all (t,x,u) with (t,x) c A, u c U(t,x), then f(t,x,u) = (fl,...,f ) is a given n function on M, while g is a real scalar function on B. The differential system (1.1.2) can be written equivalently in the form dxi/dt = f.(t, x(t), u(t)), i = n,... 1 1 A pair x(t) = (x,..., u(t) =(,...,um) t < t < t, is said to be admissible provided x is absolutely continuous (AC), u is measurable, and relations (1.1.2-5) hold. Then O is a class of admissible pairs. If (x,u) is an admissible pair, we say that x is an (admissible) trajectory, and that u is an (admissible) strategy, or control function. The point I(x) = (tl, x(tl), t2, x(t2)) is denoted as the ends of the trajectory. In Mayer problems, therefore, the functional has the form I[x] = g(q(x)). Mayer problems in which we seek the minimum of the functional I[x,u] = g = t2 - tl (or g = t2 if tl is fixed) are said to be problems of minimum time. Mayer problems where f(x,u) is independent of t, and U is fixed, or depend on x only, are said to be autonomous. In a Lagrange problem we seek the minimum, or the maximum, of a functional I[x,u] = of f (t, x(t), u(t))dt (1.1.6)

1.3 1 n 1 m in a class Q of pairs x(t) = (x,...,x ), u(t) = (u,...,u ),t < t < t 1- -2' satsifying a system of ordinary differential equations (1.1.2) constraints (1.1.3), (1.1.4), and boundary conditions (1.1.5). HIere fo(t,x,u) is a scalar function defined on M, and A, B, U, M are as before. A pair x(t), u(t), t <t t2, is said to be admissible under the same requirements as before, and the additional one that f (t, x(t), u(t)) be L-integrable in [tl,t2]. For f = 1, we have I = t tl, and we deal again with a problem of minimum 0 2 time. A Lagrange problem is said to be autonomous if f (x,u), f(x,u) (fl,...,f ) do not depend on t, and U is fixed, or depend on x only. n In a Bolza problem we seek the minimum or the maximum of a functional t 2 t I[x,u] = f fo(t, x(t), u(t))dt + g(tl, x(t) t x(t) (117) n. n in a class 0 of pairs x(t) =(x,...,x ), u(t) (u,.,u), t < t < t2, satisfying the same requirements as for a Lagrange problem. In each of the problems above isoperimetric constraints may be required of the form t 7 = f h (t, x(t), u(t))dt = C, s 1,...,N, (1.1.8) s s s for given functions h (t,x,u) defined on M, and given constants C, s = 1,...,N. s We shall see below that these constraints can be rewritten so as to be included in the general requirements (1.1.2-5). In a free problem we seek the minimum or the maximum of a functional t I[x] = f fo(t, x(t), x'(t))dt (1.1.9) tl

1n in a class,0 of function x(t) = (x,...,x ), t < t < t2, satisfying constraints 1- 22 and boundary conditions. (t, x(t)) e A, t C [tl,t2], (1.1.10) (tl, x(tl), t2, X(t2)) B(1.1.11) As before, A and B are given subsets of E and of E2n+2, respectively, n+l 2n+2 f and f (t,x,u) is a given scalar function on M = A x E. A function 0 n x(t) = (x,...,xn), t < t < t2, is said to be admissible provided x is absolutely continuous (AC), relations (1.1.10), (1.1.11) are satisfied, and f (t, x(t), x'(t) is L-integrable in [tl,t], where x' = dx/dt. We shall consider classes 2 of admissible functions x. Here, too, isoperimetric constraints may be required of the form t r! = f h (t, x(t), x'(t))dt = C, s = 1,...,N, (1.1.12) t for given functions h (t,x,u) defined on M = A x E, and given constants C,.S5n s s = 1,...,N. We shall see below that free problems, with or without isoperimetric constraints, can be written as particular Lagrange and Mayer problems. 1.2 Some relations among the problems above Mayer, Lagrange, and Bolza problems are equivalent. On one hand, we see that Mayer and Lagrange problems can be thought of as particular Bolza problems with f = 0 and g = O, respectively. On the other hand, Lagrange and Bolza problems can be reduced to Mayer problems by the introduction of an additional variable x, the (n+l)-vector x = (x0,x) = (x, x,...,x ), and auxiliary

1.5 0 0 differential equation dx /dt = f and boundary condition x (t) -. Then, 0 I.agrange problems are reduced to the Mayer problem I[x,u] = x (t2), 0 dx/dt = f(t, x(t), u(t)), dx /dt = fo(t, x(t), u(t)), (t, x(t)) A A A x E1, u(t) C U(t, x(t)), (tl, u(tl), t2, x(t2)) A, x (tl) = o. Anologously, Bolza problems are reduced to the same Mayer problem with functional I[x,u]:= x (t2) + g(t, x(t ), t2, x(t2)). Finally, Mayer problems can be reduced to Lagrange problems in the 0 01 n state variable x = (x,x) = (x,x,...,x ), t 2 0 I[xyu] = x (t)dt t dx/dt = f(t, x(t), u(t)), dx /dt = 0, (t, x(t)) E A = A x E1, u(t) e U(t, x(t)), (tl X(tl) t2, x(t)) B (t2-tl)x t) - g(t (t) t (t)) = The equivalence of Mayer, Lagrange, and Bolza problems is thus proved. Isoperimetric constraints (1.1.9) can be included in the Mayer, Lagrange, n+s Bolza problems above by simply introducing additional variables x, s = 1,...

1.6 auxiliary differential equations and boundary conditions n+s dx /dt =h (t, x(t), u(t)), s n+s n+s x (tl) = O, x (t2) = C, s = 1,..,N. 1 2 s Free problems can be written as Lagrange problems t I[x,u] = f f (t, x(t), u(t))dt, dx/dt = u(t), (t, x(t)) c A, u(t) c U = E, (tl, x(tl), t2, x(t)) E B. Thus, free problems are Lagrange problems with m = n, f = u, U = E n i (thus, fi = u, i = 1,...,n). Possible isoperimetric constraints (1.1.10) can be written as above in the form (1.1.12) by the use of auxiliary variables n+s x, s = 1,...,N. 1.3 Examples 1. For instance, the simple problem of the path of minimum length between two sets B1 and B2 in E2 is a free problem of the form I[x] = f2 (1 + lx'(t) 2)l/2dt, x(t) = (xl,.x ) t1 t < t tl (t, x(tl)) c B1, (t2, x(t2)) 2 B with B1, B2 c En+l. As a Lagrange problem it becomes

1.7 t I[xu] = J2 (1 + (t) 1/2dt dx/dt = u(t), (tl, x(t)) B1, t (t (t2)) B2, u(t) E U = E 1 1 2 2 2 n' 1 n n x(t) = (x,...,x ), u(t) = (u,...,u ), t1 < t2. As a Mayer problem it becomes I[x,y,u] = Y(t2), dx/dt = u(t), dy/dt = (1 + lu(t)| ), (t, x(tl)) c B1 (t2, x(t2)) E B2, u(t) c U = E 1 1 2 2 29 n 1 n 1 n x~t) = y(t) u(t) = (u,...u ), t < t < t. 2. As another example, let us consider the Lagrange problem in E n t I[x,u] = 2 (Ix(t)1 + 2u(t)1 )dt t dx/dt = Ax + Bu, u c U, (tl, x(ti) 1 (t2, x(t2)) c B2x n1 ~~x) t tm x(t) = (,...,x), (t) (u...u ) t 1 2 where A, B are constant matrices of the types n x n, n x m, U a fixed subset of Em, and BlB2 subsets of En+l. In Mayer form it becomes m 1 ~

I[x,y,u] = y(t), 2 dx/dt = Ax + Bu, dy/dt = Ix(t)| + |u(t)|, (t, x(tl)) C B1 (t2 x(t2)) c B2 Y(t) 1 n 1 m x(t) = (x,...x), y(t), u(t) =(u m),u), t t < t2 3. As a further example we consider the problem of the maximum of the integral t I[x] = 2 x(t)dt, t with constraints and boundary conditions 2 2 1/2 x(t) > 0, 1 (1 + x' (t))/dt = L x(t ) = O, x(t2) = O, t < t2 fixed. The same problem can be written in the Mayer form I[x,y,t,u] = Y(t2), dx/dt = u, dy/dt = x, dz/dt = (1 + u (t)) l/2, x(tl) = O, x(t2) = O, Y(tl) = O, z(tl), z( z(t2) = L, tl < t2 fixed, u(t) c U = E1, (t, x(t)) A = [(t,x)l tl < t < t2, x > 0].

1.9 4. Let us consider finally the Bolza problem t 2 2 I[xu] = x (t ) + x (t2) + (t)dt t1 dx/dt = u, dy/dt = x dx/d(tl) - Ou, u(t) E U = [1 u < 2], n = 2, m = 1. An equivalent Lagrange problem is as follows: 2 2 I[x,y,u] = (x t) + (t))dt + tl 2 x 2 2 dx/dt =- u, dy/dt = O (tl-t ) Y(tl) = x (tl) + x (t), u(t) < U = [1 < u < 2], 2I[XjPu1 n = 21, m = y(t) n = 2, m = 1.

UNIVERSITY OF MICHIGAN 3 9015 02656 6482 3 9015 02656 6482