Appl Math Optim 19:11-32 (1989)

Applied Mathematics and Optimization © 1989

Springer-Verlag New

Y o r k Inc.

Optimal Trajectories of Infinite-Horizon Deterministic Control Systems Arie Leizarowitz Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA

Abstract. We study the infinite-horizon deterministic control problem of . . . .

T

minimizing So L(z, ~) dr, T ~ , where L(z,. ) is convex in ~ for fixed z but not necessarily jointly convex in (z, ~). We prove the existence of a solution to the infinite-horizon Bellman equation and use it to define a differential inclusion, which reduces in certain cases to an ordinary differential equation. We discuss cases where solutions of this differential inclusion (equation) provide optimal solutions (in the overtaking optimality sense) to the optimization problem. A quantity of special interest is the minimal long-run average-cost growth rate. We compute it explicitly and show that it is equal to minx L(x, 0) in the following two cases: one is the scalar case n = 1 and the other is' when the integrand is in a separated form l(x)+ g(£c).

I. Introduction We consider an infinite-horizon problem T

of minimizing the

expression

So L(x, ~) dt as T grows to infinity. In the situation where L( -, • ) is jointly convex the problem was studied by Brock and Haurie [1] and Leizarowitz [7] using the overtaking optimality notion. In [7] a certain differential inclusion ~ ~ G(x) was associated with the integrand L and optimality properties of the minimization problem were related to and studied in light of dynamical properties of this differential inclusion. The convexity of L implied the simplification that x ~ G(x) had a convex graph and its dynamical properties be determined by a certain linear differential equation (see [9] for details). In this work we consider a broader situation where rather than the joint convexity of L ( . , • ) we merely require v ~ L(x, v) to be convex for every fixed x. Consideration of the overtaking optimality notion leads again to examining a

12

A. Leizarowitz

related differential inclusion, which reduces in certain cases to an ordinary differential equation. Dynamical properties of this differential inclusion (or equation) are related to optimality properties of the minimization problem: if all the to-limit sets are the same, independent of the solution, then there is a weak overtaking optimal trajectory. If the common to-limit set is a singleton, then there exists an overtaking optimal trajectory. We demonstrate how various optimal quantities can be explicitly computed in certain situations. Thus optimal trajectories can be computed as solutions of the above-mentioned differential inclusion (equation). We remark that when a differential equation is involved it is different from the Euler-Lagrange equation. The latter is, e.g., of order 2n while the one that we consider is of order n. A quantity of special interest is the minimal long-run average-cost growth rate. We shall show how it can be explicitly computed in certain cases. Specifically we shall show that in the scalar case it is equal to minx L(x, 0). Our approach involves the consideration of the infinite-horizon Bellman equation, which is an equation for a function p(. ) and a scalar/z which play roles similar to the cost potential and minimal average cost per unit time in stochastic control problems. We introduce the notion of good solutions for the Bellman equation which will be used to prove the existence and to compute optimal trajectories. The existence of a good solution to the infinite-horizon Bellman equation is proved by considering afinite-horizon problem with the same cost as the infinite-horizon one and applying known results for finite-horizon control problems. In the scalar case we compute explicit expressions for the minimal cost growth rate and for the differential inclusion which governs the behavior of optimal trajectories. We also apply our results to problems in R n where the integrand is in a separated form L(x, v) = l(x)+ g(v). In both cases the minimal cost growth rate/z is equal to minx L(x, 0). Moreover, we remark that for a wide class of problems it follows that whenever the above-mentioned function p(. ) is continuously differentiable then the minimal cost growth rate is expressed by minx L(x, 0). These facts suggest the conjecture that the relation /z = min L(x, O) x

holds in quite general situations. The paper is organized as follows. In Section 2 we describe the framework and the assumptions. In Section 3 we introduce the notion of good solutions for the infinite-horizon Bellman equation and discuss some properties of this equation. In Section 4 we prove the existence of good solutions by considering a related finite-horizon problem with an optimal cost equal to that of an infinitehorizon problem closely related to the original one. In Section 5 we use the good solution to define a certain differential inclusion, and the relation between its solutions and optimal trajectories is discussed. Section 6 is devoted to the scalar case and we compute explicitly various optimal quantities. In Section 7 we apply our results to study the case where L(x, v)= g(v)+ l(x) is in a separated form,

x,v~ R".

Optimal Trajectories of Infinite-Horizon Deterministic Control Systems

2.

13

The Framework

Let (x, v) -->L(x, v) be a continuous function defined on R" × R" with values in (-oo, +oo]. We assume that there is a c o m p a c t set K c R", the closure of an open and convex set in R", such that for every v

L(x, v) < oo

if and only if

x ~ K.

We denote by I'] the Euclidean n o r m in R n and we assume, t h r o u g h o u t the paper, the following:

Assumption A. (i) The function (x, v)-->L(x, v) is continuous, and for every fixed x ~ K the function v -->L(x, v) is convex. (ii) L satisfies the coercivity condition

L(x, v)/lvl-->oo

as

Ivl-,~

for every x c K. (iii) There is a constant c > 0 such that

IL( x, v) - L(y, v)l- clx -yl(1 + Ivl) for every x, y c K and every v ~ R n. We call a function L which has the properties in A s s u m p t i o n A an integrand. Definition 2.1. A function z(. ), z: [0, co)--> R n is called a trajectory of L if it is absolutely continuous (a.c.) and if L(z(t), ~(t)) < oo for almost every t in [0, oo), namely z(t)~ K for every t - 0 . The p r o b l e m that we consider here is the minimization o f S~" L(z(t), ~(t)) dt as T--> co. With every trajectory z(. ) of L we associate the cost flow c(- ) defined by

c(t) = I / L(z(s), ~(s)) ds. As an optimality criterion we use the overtaking optimality notion. This concept was introduced and studied in the e c o n o m i c literature by Gale [4], K o o p m a n [5], and v o n Weizs[icker [10], and in the control literature by, e.g., Brock and Haurie [1]. Definition 2.2. The trajectory z*(- ) is called an overtaking optimal trajectory of the integrand L if the cost flow c*(. ) corresponding to it has the property: given a trajectory z ( . ) with z ( 0 ) = z*(0) and an s > 0, there is a time t o > 0 such that c*(t) < c(t) + e for every t > to, where c(. ) is the cost flow corresponding to z(. ).

14

A. Leizarowitz We shall also consider the following weaker notion of overtaking optimality:

Definition 2.3. A trajectory z*(. ) is called a weak overtaking optimal trajectory of the integrand L if the cost flow c*(.) corresponding to it has the property: given a trajectory z ( . ) with z(0)= z*(0) and an e > 0 , there is an increasing sequence of times {ti}~=l, ti ~ O0 as i-* ~ , such that c*(t~) < c(t~) + e for every i--- 1, where c(. ) is the cost flow corresponding to z(. ).

The problem which we consider is the existence and characterization of overtaking optimal trajectories for a given integrand. Certain infinite-horizon control problems can be considered in the above framework by associating with them a suitable integrand. For details see, e.g., Brock and Haurie [1].

3.

The Infinite-Horizon Bellman Equation

The following is a heuristic discussion which is intended to motivate the consideration of equation (3.2) below. . . . . T For the finite-horizon problem of minimizing So L(x, ~) dt the value function (x, t ) ~ ~p(x, t) satisfies the Bellman equation

{

O~+min[L(x, v ) + v . V~(x, t)] =0, Ot

(3.1)

gifT, x) = 0

(see, e.g., Theorem 4.1, p. 83, of Fleming and Rishel [3]). The function (Xo, to) ~O(Xo, to) expresses the minimal value of S,r L(x, 2) dt where x(. ) is subject to X(to) = Xo. In the infinite-horizon case we expect the cost integral to grow at some minimal rate T-~txT, but still expect the expressions [ S T L ( x , ~ ) d t - t x T ] to remain bounded as T varies in [0, oo), for the better trajectories x(.). Thus replacing L(x, v) in (3.1) by [L(x, v) - / z ] would yield an equation for the excess cost, namely the cost left after subtracting the linear part/zT from the cost integral Sro L(x, 2) dt. Moreover, since the problem is defined on an infinite time interval, ~p is time independent and the term O~/Ot in (3.1) should disappear, and we are led to consideration of the equation min[L(x, v) + v- Vp(x)] =/z,

x ~ K,

v ~ R n.

(3.2)

This is the Bellman equation for our infinite-horizon problem. It is an equation both for the function p ( . ) and for the scalar /z. This completes the heuristic discussion and we now return to a rigorous treatment of the problem. We consider a Lipschitz continuous function p ( . ) in K and denote by Dp(xo, vo) the directional derivative of p(. ) at the point Xo in the direction Vo, namely

Dp(xo, Vo)= lira h~O+

p( xo + hvo) - p( xo) h

Optimal Trajectories of Infinite-HorizonDeterministic Control Systems

15

For almost every Xo in K the directional derivative is defined for all Vo, since Vp(xo) is defined for almost every x0 in K (since p(. ) is Lipschitz continuous). For a given K c R" a pair (p, tz) can be given the control interpretation described above if it is a good solution of (3.2), according to the following: Definition 3.1. Let x-~p(x) be Lipschitz continuous in K. The pair (p, tz) is a good solution of (3.2) if:

(i) Equality holds in (3.2) for almost every x in K. (ii) For every x o ~ K there is an a.c. trajectory x ( . ) such that x(0)=Xo, x ( t ) c K for all t - 0 and

L(x( t), Yc(t) ) + Dp(x( t), ~( t) ) = I~ for almost every t in [0, co). We define the set-valued function z ~ G(z) by

G(z) = { v c R": L(z, v)+ Dp(z, v)=tz}

(3.3)

whenever Dp(z, v) is defined. For a prescribed initial value ZoC K we consider the differential inclusion

~(t)~ G(z(t))

for almost every

t>0

(3.4)

with the initial condition z(0) = z0. An a.c. solution z(. ) of (3.4) which satisfies z(t) ~ K for all t->0 is called a viable solution of (3.4). Using this terminology condition (ii) in Definition 3.1 can be phrased as: for every ZoE K there is a viable solution z(. ) of (3.4) satisfying z(0) = zo. If G(z) is a singleton, as in the case where v ~ L(x, v) is strictly convex and p(. ) is continuously differentiable (thus Dp(z, v) = Vp(z) • v in (3.3)), then (3.4) is an ordinary differential equation. The requirement in (ii) of Definition 3.1 is then that all the solutions of this equation which start in K at t = 0 will stay in K for all times t > 0. Assume that (p, ~) is a good solution of (3.2) and for a Zo~ K let z(. ) be a viable solution of (3.4) satisfying z ( 0 ) = Zo. The function t ~ p(z(t)) is a.c. being a composition of a Lipschitz continuous p ( . ) and an a.c. z(. ), and its derivative is a.e. equal to Dp(z(t), 2(t)). Thus the following holds a.e. in [0, 0o):

L(z(t), ~(t))=tx - D p ( z ( t ) , ~(t)) which implies that

Io T L(z(t), e(t)) dt = t z T + p ( z o ) - p ( z ( T ) ) .

(3.5)

Since p ( - ) is bounded on K it follows from (3.5) that lim 1

T~oo T

L(z(t), i ( t ) ) dt =tx.

(3.6)

16

A. Leizarowitz

On the other hand, let x(. ) be any trajectory of L (recall Definition 2.1), thus x(. ) is a.c. and x(t) ~ K for all t >- 0. We show in Proposition 4.5 that for almost every t > 0 the following holds:

L(x( t), :~( t) ) > tx - Dp(x( t), Yc(t) ) implying that lim [ r L ( x ( t ) , 2 ( t ) ) dt>-i.~. r~oinf IT Jo

(3.7)

(We do not present Proposition 4.5 here since its proof is closely connected with the definition of the good solution p ( . ) in Section 4.) We thus conclude from (3.6) and (3.7) the following:

Theorem 3.2. If ( Pi, [-gi), i = 1, 2, are good solutions of (3.2) then/xl = tz2, namely there is uniqueness in the scalar constant part of the good solution. This unique value tx is the minimal-cost growth, or the minimal long-run time average cost. Example 3.3. Let K = [ - 1 , 1 ] c R 1 and L(x, v ) = 1 ( v - f (x)) 2 where f is a continuous scalar function defined on [-1, 1]. The Bellman equation is min[l(v - f ( x ) ) 2 + vp'(x)] = ~ which is equivalent to - l ( p ' ( x ) ) 2 + p ' ( x ) f ( x ) =/~

or

(3.8)

p'(x) = f ( x ) + [ f 2 ( x ) - 2 / ~ ] 1/2.

For every x the minimum in (3.8) is attained at v = f ( x ) - p ' ( x ) , thus we are looking for trajectories z(. ) which satisfy ~(t) = f ( z ) - p ' ( z ) and Iz(t)]- 1 for all t --- 0. Since such trajectories must exist for every choice of initial condition Zo in [-1, 1] we must have 2/x -< min f2(x). Ix1_<1

(3.9)

Assume that the minimum of f 2 ( . ) is attained at a unique point -1 < z0< 1. Then, we claim, an equality holds in (3.9) and a good solution is given by /z=½ rain f2(x), --l<_x~l

p'(x)

[f(x)-x/f(x)2-21x, = lf(x)+x/f(x)2-2tz-,

--

- l <--x<-zo, Zo
For every Xo in [-1, 1] the trajectory x(. ) which satisfies ~(t) = ~/f(x) 2 -2/z • sgn(z0 - Xo),

x(0) = Xo,

is such that x ( t ) e [ - 1 , 1] for all t>-0. This shows that the pair (p,/~) is indeed a good solution, that ~ is the minimal-cost growth rate, and the above trajectory x ( . ) is such that liml f r r-,oo T Jo L(x(t), g(t)) dt = tx. In fact this trajectory is even overtaking optimal, as will follow from Theorem 3.3, and x ( t ) ~ Zo as t ~ o o for every initial condition xo.

Optimal Trajectories of Infinite-HorizonDeterministicControl Systems 4.

17

Existence of Good Solutions

In this section we prove that the definition of good solutions is not vacuous and there indeed exist good solutions for the infinite-horizon Bellman equation (3.2). The method of proof is by defining a finite-horizon problem with the same minimal cost as that of an infinite-horizon problem which is closely related to the original one, and applying known results for finite-horizon control problems. Theorem 4.1. Let L ( . , • ) be an integrand with a constraint set K c R n. Then the Bellman equation (3.2) has a good solution ( p ( . ) , t.t ). To prove Theorem 4.1 we shall need the following results. Proposition 4.2.

Under Assumption A there exist constants M and ~ such that

fo r [L(z, ~) - Ix] dt >- ~

for all

M

T> 0

and all trajectories z(. ) of L, (4.1)

and there is a trajectory x ( . ) of L so that oT[L(x, Y c ) - ~ ] d t <-M

forall

T>0.

(4.2)

Proof We first prove that (4.1) and (4.2) hold for every integer T > 0 and then the assertion will follow. To this end we define the function m: K x K ~ R 1

re(x, y) = i n f

(L

L(z, i) dt: z(O) =x, z(1) = y

}

,

(4.3)

where the infinum is over all the trajectories z(. ) which satisfy z(0) = x, z(1) = T, and z(t) e K for 0 -< t_< 1. The fact that K is the closure of an open and convex set implies that re(x, y ) < m for every x, y e K, since

o~L(z(t),~(t))dt
for

z(t)=x+t(y-x),

by the continuity of L ( . , . ) . We claim that the conditions in Assumption A guarantee that L ( . , . ) is bounded below on K × R". Indeed, it follows easily from (i) and (ii) of Assumption A that

L(x, v)/Ivl~oo

as

Ivl~,

uniformly for

xeK.

This, together with the continuity of L ( . , • ) implies that L ( . , • ) is bounded below on K x R". It thus follows that m(x, y) > -oo for every x, y e K. The conditions in Assumption A guarantee that the infinum in (4.3) is attained by some trajectory (see Theorem 4.1, p. 68, of Fleming and Rishel [3]). Moreover, m ( . , • ) is continuous on K x K (see Proposition 4.3 below). oe C Now consider, for every sequence {xi}~=o K, the cost expressions N--1

CN(~) = Y. m(xi, x~+~), i=0

(4.4)

18

A. Leizarowitz

where we denote 2={x~}7°=0, and we consider (4.4) as N ~ o o . A study of such infinite-horizon discrete-time control systems is displayed in Leizarowitz [8], and it follows from Theorem 3.1 of [8] that there exist constants/.t and Mo> 0 such that N--1

m(xi, xi+l)- tzN >---Mo i=0

for all

N >- 1 and every sequence

{x~}7°=oc K,

and there exists a sequence {x*}7°=oc K such that IN-I

~, m(x*,x*+l)

-/xN

<-Mo

forall

(4.5)

N->I.

i=0

Clearly, this means that (4.1) and (4.2) hold if we consider only integers T > 0. Since L ( . , • ) is bounded below on K x R" it follows that there is a constant a such that

o~ L(x(t), Yc(t)) dt> a

(4.6)

for every 0 < 6 -< 1 and every trajectory x(. ). It follows from (4.5) and (4.6) that (4.1) and (4.2) hold for every T > 0 with

M=Mo+l~r+l~l. As a trajectory x ( . ) in (4.2) we take a trajectory such that

x(k)=x*

for all

k->0

and in the interval [k, k + 1], x(. ) satisfies

f k+a L(x( t), Yc(t) ) dt = m(X*k , Xk*+l). k

This concludes the proof of the proposition.

[]

Once we have established the validity of (4.1) and (4.2) we can go on and define the function p: K ~ R' F

p(y)=inf(liminf f I

T~Jo

[L(x(t),~(t))-t~]dt:x(.)isa

trajectory for L and x(0)= y ) .

(4.7)

It follows from Proposition 4.2 that p(. ) is well defined. In what follows we need the following result from [6].

Optimal Trajectories of Infinite-HorizonDeterministic Control Systems Proposition 4.3.

Proof

19

The function m (., • ) is Lipschitz continuous on K × K.

See Theorem 5.6.3 of [6].

Proposition 4.4.

The function p(. ) is Lipschitz continuous on K.

Proof Let m: K x K ~ R 1 be as in (4.3). Then there is, by Proposition 4.3, a constant c > 0 such that Ira(x1, Y l ) - m(x2, Y2)[<- c[]xl--X21 + [Yl--Y2[]

(4.8)

for all x~ , x2 , y~ , Y2 c K. Now let x c K and let x(. ) be a trajectory of L such that x(0) = x and lim inf T~oo

[L(x(t),2(t))-ix]
For x ' e K we define a trajectory z(. ) which satisfies z(O)= x', z ( 1 ) = x(1)

o L(Z(t), i ( t ) ) = m(x', x(1)) and z ( t ) = x(t) for all t-> 1. It then follows from (4.8) that

p(x') <- p ( x ) + clx - x'l + ~. This being true for every e > 0 and every x, x' ~ K implies that

]p(x)-p(x')]-<

c l x - x']

for all x, x ' c K, proving the Lipschitz continuity of p(. ) in K.

[]

The following result will be needed in the proof of Theorem 4.1. It was also used to establish Theorem 3.2. Proposition 4.5.

Let x(. ) be any trajectory of L in K. Then the following holds:

L(x(t),:~(t))+Dp(x(t),Yc(t))-ix>-O

foralmostevery

t>-O.

(4.9)

Proof Let T > 0 be fixed and consider the following finite-horizon minimization problem on the finite time interval [to, T], 0 -< to< T: min~ I T [L(x(t), 2 ( 0 ) - I x ] d t + p ( x ( T ) ) : X ( t o ) = y } , x(.~ l.l,o

(4.10)

where p(- ) is the function which is defined in (4.7). It follows from the definition of p(. ) that the minimal value in (4.10) is p(y), no matter what the values of to and T are.

20

A. Leizarowitz

Let x ( . ) be any trajectory of L in K. In order to prove (4.9) it is clearly enough to prove

L(x(t),2(t))+Dp(x(t),2(t))-ix>_O The function t~p(x(t)) is differentiable

for almost every

t~[0~l].

(4.11)

a.e. in [0, 1] as a composition of the Lipschitz continuous function p(. ) and the a.c. trajectory x(. ). At every point such that both x ( . ) and p(x(.)) are ditterentiable we have (d/dt)p(x(t))= Dp(x(t), Yc(t)). Thus the directional derivative Dp(x(t), 2(t)) exists for almost every t in [0, 1]. Now if (4.11) is false then for some a > 0 the set C = {t~ [0, 1]:

L(x(t), Sc(t))+Dp(x(t), So(t))-Ix <--a}

(4.12)

has positive Lebesgue measure. Then C contains a Lebesgue point 0 < to < 1 of the function t~ L(x(t), it(t))+ Dp(x(t), ~(t)). We consider the expressions to+~$

j"

[L(x(t), ~(t)) - Ix] dt +p(x(to+ 8)).

(4.13)

tO

From the way we chose to it follows that lira+ ~1 fj t °'°+z [L(x(t),x(t))+Dp(x(t),2(t))-Ix]

dt<--a ,

and this implies that for sufficiently small 6 the expression in (4.13) is less than But this is a contradiction since by the discussion at the beginning of the p r o o f the minimal possible value for the expression in (4.13) is p(X(to)). This proves (4.11) and concludes the proof of the proposition. []

p(x(to)) -½aS.

Proof of Theorem 4.1. We again consider the minimization problem (4.10), for a fixed T > 0 and 0 -< to< T. We denote the value function of this problem by W(to, y). It follows from standard results about the value function (see Theorem 4.1, p. 81, of Fleming and Rishel [3]) that at all points where the value function is differentiable it satisfies ---OW~-min[L(y, v)+OW, v-/x] 0to ~ Oy

=0

(here we used the fact that there exist optimal solutions to the problem (4.10), as implied by Assumption A). But as discussed at the beginning of the proof of Proposition 4.5 we have W(to, y)=p(y) for all 0 - t o < T, thus we obtain the equality min[L(y, v) + V p ( v ) • v - IX] = 0 whenever p(. ) is ditterentiable. By Proposition 4.4 p(. ) is Lipschitz continuous hence, by Rademacher's theorem (see p. 216 of Federer [2]) it is differentiable a.e. in K. It thus follows that (3.2) holds a.e. in K which proves the validity of (i) in Definition 3.1.

Optimal Trajectories of Infinite-HorizonDeterministicControl Systems

21

To complete the proof we have to construct a viable solution x ( . ) of (3.4) for every initial value Xo~ K. Clearly, it is enough to construct a solution x ( . ) of (3.4) which satisfies x(0)=Xo and x ( t ) ~ K for all 0-
Io[L(z(t),~(t))-/~]

t+p(z(1)),

z(0) = Xo,

z(t)cK

for

0_
The existence of such an x(. ) follows from Assumption A. The function t-~

p(x(t)) is differentiable a.e. in [0, 1] and at every point such that both x ( - ) and p(x(.)) are differentiable (d/dt)p(x(t))= Dp(x(t), Yc(t)). Thus the directional derivative Dp(x(t), Yc(t)) exists for almost every t in [0, 1]. We claim that L(x(t),Yc(t))+Dp(x(t),~(t))-/~<-O

a.e. in [0, 1].

(4.15)

Let D be the set D -- {t ~ [0, 1]: L(x(t), ~(t)) + Dp(x(t), ~(t)) -/x > 0} and we have to prove that D has Lebesgue measure zero. Otherwise there would be a f l > 0 so that E = {t ~ [0, 1]: L(x(t), Yc(t)) -t- Dp(x(t), Yc(t)) - i~ >_fl} is of positive Lebesgue measure, hence E contains a Lebesgue point 0 < ~"< 1 of the function t -~ L(x(t), ~(t)) + Dp(x(t), ~(t)). From the way we chose z it follows that lim 1

[L(x(t),2(t))+Dp(x(t),2(t))-tx]dt>-~

and therefore there is a sufficiently small ~ > 0 for which the following holds:

]+~ [L(x(t), ~(t)) -/~] dt+p(x(r+ ~)) >-p(x(z))+½~.

(4.16)

But since x(. ) minimizes (4.14) it follows that it must also minimize the expression

f

-+8 [L(z(t), ~(t))-/~] dt+p(z(z+ ~)),

z(z)--x(z),

with the minimal value being p(z(:')). This, however, contradicts (4.16), which concludes the proof of (4.15). It follows from (4.9) and (4.15) that x(- ) satisfies (3.4) a.e. in [0,1], and since x(0)--Xo and x ( t ) ~ K for all 0 - t - < l , (ii) of Definition 3.1 holds, which completes the proof of the theorem. []

5.

A Related Differential Inclusion and Optimal Trajectories

It is the content of Proposition 4.5 that every trajectory of L satisfies (4.9) on [0, ~). Our claim is that trajectories for which equality in (4.9) holds for almost

• ,~ ~ i ~ ~

~.

22

A. Leizarowitz

every t > 0 are of special importance from the optimality point of view. We recall the definition of the set-valued function z ~ G(z) in (3.3) and consider the differential inclusion 2(t) ~ G ( x ( t ) ) x(0) = Xo.

for almost every t > O, (5.1)

For every initial value there exists, by Theorem 4.1, a trajectory x ( . ) which satisfies (5.1). Let x ( . ) be a trajectory of L and assume that

fo

° [ L ( x ( t ) , ~c(t)) + Dp(x(t), ~(t)) -/a,] dt < oo.

(5.2)

Let [ % bj] be a sequence of time intervals, bj - aj = 1 for some fixed positive L Assume that aj-~ oo as j-~ oo and let xj(. ) be defined on [0, I] by

xj( t) = x( aj + t). Proposition 5.1. Let x ( . ) be a trajectory of L and let [at, bj] and x~(. ) be as above. Suppose further that (5.2) holds. Then there is a function y: [0, l]~ K such that ~(t)~ G(y(t)) for almost every t c [0, l] and there is an increasing sequence of natural numbers {jk}k°°=l such that lim max k~oo

O~t<--I

[xj~(t)-y(t)l=O.

(5.3)

Proof The validity of Assumption A guarantees the existence of optimal trajectories on finite intervals. Therefore there is an increasing sequence of integers {jk}k~=l and a function y ( . ) for which (5.3) holds and

fo

L(y(t),f:(t)) dt-< lim inf k ~oo

L(xjk(t), Ygk(t)) dt.

(5.4)

The nonnegativity of the integrand in (5.2) implies that

o[L(x~k,~9~)+Dp(x~,2~k)-lz]dt-O

as

k.oo

and then it follows from (5.4) that

Io

' [ L(y, 35)+ Dp(y(t), j,(t)) - Iz] dt = O.

Since the integrand in the last integral is nonnegative we conclude that y ( . ) satisfies the differential inclusion (5.1) a.e. in [0, l], concluding the proof of the proposition. [] Let us consider dynamical properties of the relation (5.1). For a solution x ( . ) of (5.1) we denote, as usual, by w ( x ( . ) ) the set of all points z~ K such that x(tj) ~ z for some sequence of times t~~ oo.

Optimal Trajectories of Infinite-HorizonDeterministicControl Systems

23

Suppose that there is a set S c K such that w ( x ( . ) ) = S for every viable solution x( . ) of (5.1). Then there is a weak overtaking optimal trajectory for the infinite-horizon minimization problem for L in K, for every initial value Xo ~ K. It is given by any viable solution of the differentiable inclusion (5.1).

Theorem 5.2.

Proof Let x ( . ) be a trajectory for L in K, x ( 0 ) = Xo. We have by Proposition 4.5 the relation fo T [L(x, ic) - tx] dt >-p(xo) - p ( x ( t ) ) .

(5.5)

If limSUpT_.ooJr[L(x, 2 ) , t z ] d t < o O then we can use Proposition 5.1 and a diagonal argument to construct a viable solution y(- ) of (5.1) defined on [0, oo) such that for every interval [0, l] there is a sequence of time intervals/j = [aj, bj] with aj j~o) oo and

~axlx(aj+t)-y(t)[~O

as j ~ o o .

(5.6)

It follows from our assumptions that for every z ~ S and every e > 0 there is some to >-0 so that [y(to)- z] < e. This, together with (5.6), implies that for every z ~ S there is a sequence of times ~'k k-,~ O0 SO that

X(rg)~Z

as

k~oo.

(5.7)

Since S is an w-limit set it is a compact subset of K and assume that p ( - ) attains its minimal value on S at z0 c S, namely

p(z)>-p(zo)

zcS.

for every

(5.8)

Let x(- ) be any trajectory of L, x(0) = Xo, and let x*(. ) be a viable solution of (5.1), x * ( 0 ) = Xo. If lim

r~oo

[L(x(t), 2 ( t ) ) - ~ ] dt =oo,

then it follows from

oT [ L(x*( t ), ~*(t)) - / z ] dt = p(xo) - p ( x * ( T) ) that

;o

L(x(t), ~:(t)) d t -

fo •

L(x*(t), ~*(t)) d t ~ .

as

T~co.

(5.9)

T

If, on the other hand, hm m f T ~ ~o [L(x, Yc) - Ix] dt< oo, then it follows from Proposition 4.5 that lim SUpT~SOT [L(x, ~ ) - t z ] dt
x(~'k)~zo

as

k~oo.

(5.10)

24

A. Leizarowitz

We thus conclude from (5.5) that ork [L(x, ~ ) - I x ] d t > - p ( x o ) - p ( x ~ k )

(5.11)

while x*(. ) being a solution of (5.1) satisfies the following (recall (3.3)):

fo

"~ [L(x*, ~ * ) - I x ] dt = p(Xo)--p(x*(~'k)).

Since X*(Zk) converges to S as k ~ given e > 0

(5.12)

it follows from (5.8) and (5.10) that for a

p(x*(~'k)) >--p(X(Zk)) -- e

if k is large enough. In view of (5.11) and (5.12) this implies that

fo

~k L ( x * , Yc*) dt <

;o

L(x, ~) dt + e

for all sufficiently large k. This inequality, combined with the discussion which precedes (5.9), concludes the proof of the weak overtaking optimality of

x*(.).

[]

In order to conclude that a solution of (5.1) is overtaking optimal we impose stronger assumption on the asymptotic dynamics of (5.1). Theorem 5.3.

Suppose that there is a point s ~ K so that

(5.13)

lim x( t ) = s l-~oO

f o r every viable solution x ( . ) o f (5.1). Moreover, the limit in (5.13) has a uniform rate in the sense that f o r every e > 0 there is a to > 0 so that Ix(t) - s I< e for all t > to and all the viable solutions o f (5.1). Then there is an overtaking optimal trajectory f o r every initial value Xo. Such a trajectory is given by a viable solution o f (5.1) with the initial value Xo. Proof Let x ( . ) , x(0) = Xo, be a trajectory for L. Let y ( . ) be a viable solution of (5.1) satisfying y ( 0 ) = Xo. Comparing the corresponding cost flows c(. ) and c*(.) of x ( . ) and y ( . ) , respectively, in light of the overtaking criterion it is enough to consider the case

lim sup

[ L( x, .~) - p~] dt < oe.

T~eo

It then follows from Proposition 5.1 and the uniform rate of convergence of solutions of (5.1) to s that x(. ) also tends to s as t -,oo. We have by (4.9)

fo

T'[ L(x, Yc) -- tx ] at >_p( xo) - p ( x ( r ) )

(5.14)

Optimal Trajectories of Infinite-HorizonDeterministicControl Systems

25

while y(. ) satisfies (5.15)

or [ L(y, Y') - I~ ] dt = p(xo) - p ( y ( T) ).

Using the convergence of x(T) and y(T) to s, the continuity of p(-), (5.14), and (5.15) we conclude that for every e > 0 the relation

fo

L(y, ) ) dt <

io

L( x, ~ ) dt + e

holds for all large T, proving the overtaking optimality of y(. ).

[]

Remark. A sufficient condition which guarantees that the uniform rate limit (5.13) exists in the case that L ( . , .) is jointly convex in (x, v) is established in Leizarowitz [9]. Remark. If L ( x , . ) is strictly convex in v for every fixed x, and p ( . ) is continuously differentiable then the differential inclusion in (5.1) is in fact a differential equation. If it is sufficiently regular, then it has a unique viable solution through every initial value in K. Asymptotic dynamic properties of this equation are then related to optimality properties of the control problem as expressed in Theorems 5.2 and 5.3. 6.

The Scalar Case

In this section we consider the scalar case n = 1. Let L ( . , . ) be defined on [a, b] x R ~ where [a, b] c R 1 is a finite interval in which x ( . ) is constrained to take values. In this case we can establish simple and explicit expressions for/z and p(-). Specifically /.~ -- min L(x, O)

(6.1)

a~x~b

while p(. ) is determined by the condition that (-p'(x)) is equal to a slope of a tangent line to the graph of L(x, • ) which goes through the point (0,/z). Once explicit expressions for/z and if(x) are known, the set-valued function x ~ G ( x ) can be explicitly computed and used to determine the optimal trajectories. We are looking for a good solution of the Bellman equation min[L(x, v) + p ' ( x ) v ] =/x.

(6.2)

v

A solution (p,/.~) of (6.2) is a good solution if the following holds: (i) p(. ) is continuously differentiable in [a, b]. (ii) Denote by g ( x ) the set of points v ~ R 1 for which the minimum in (6.2) is attained. Then there is a 8 > 0 such that a---x-
and

vcg(x)

implies

v>0,

b-~-
and

vcg(x)

implies

v<0.

This condition guarantees the viability of solutions of ~ ~ g(x).

26

A. Leizarowitz

It follows from (6.2) that L ( x , v ) + p ' ( x ) v > - t x for every v, in particular <- L(x, 0). Hence ~ must satisfy tz -< a_
(6.3)

We claim that a strict inequality cannot hold in (6.3) if we wish p ' ( . ) to be continuous. To see this we observe that the statement in (6.2) is equivalent to saying that ( - p ' ( x ) ) is the slope of a tangent to the graph of v ~ L(x, v) which goes through the point (0,/z). If strict inequality holds in (6.3), then there are two such tangent lines for each x ~ [a, hi, one has a slope l+(x) and the other a slope l_(x) with l+(x)> L(x). In order to have a continuous function x ~ p ' ( x ) we must choose the tangent lines in such a way that either all of them have the slope l÷(x) or all of them have the slope l_(x) for all x ~ [a, b]. But then either g(x) c [a, oo) for all x e [a, b] or g(x) c ( - ~ , - a ] for all x ~ [a, b], for some a > 0. Clearly, there are no viable solutions for ~ e g(x(t)) in [a, b] in either case. The above discussion does not prove (6.1) since generally p(- ) is not required to be continuously differentiable, and it should only be Lipschitz continuous. However, we now show that there is a good solution for (6.2) with/z as in (6.1). In what follows we assume that the minimum in (6.1) is attained at a unique point a < c < b. For every x • [a, b], x # c, there are two tangent lines for v--> L(x, v) that go through the point (0, tz). We again denote their slopes by l+(x) and l_(x). We define the set-valued function 1 on [a, b] as follows:

l+(x)

if a<_x
I = ~ t h e set of slopes of tangent lines to L(c,. ) l(x)

|

atv=0

ifx=c,

/

kL(x)

if c
It is easy to see that l ( . ) is continuous in [a, c) and in (c, b]. Let g(x) be the points v ~ R ~ where the following minimum is attained: min[L(x, v) - l(x)v].

(6.4)

12

It follows from the uniform divergence to infinity of L(x, v)/Ivl as all the sets g(x) are uniformly bounded for x ~ [a, hi.

that

Proposition 6.1. Assume that the minimum in

(6.1) is attained at a unique point a < c < b and let x-> l(x) and x-> g(x) be defined as above. Then the set-valued function x-> g( x ) is upper semicontinuous in [ a, b ].

Proof Since the sets g(x) are uniformly bounded, the assertion will follow once we show that g(. ) has a closed graph. Since x ~ l(x) is continuous at every x # c, the graph is closed at every such point by the continuity of L ( . , • ) and the fact that the minimum in (6.4) has a constant value ~. We prove that the graph is closed at x = c . Let x,-:----> c, vj~g(xj), vjj-7-L-~ v and assume, to get a J 3~oo contradiction, that v ~ g(c). Since 0 ~ g(c) we must have v # 0, and we can assume, without loss of generality, that v > 0. It follows from the convexity of L(c, • ) and

Optimal Trajectories of Infinite-Horizon Deterministic Control Systems

27

the fact/z = L(c, 0) that

L ( c, 2 ) < l [ / z + L(c, v)]

(6.5)

since equality in (6.5) would imply that v ~ g(c). We also have for every j -> 1

L ( Xj, ~) ~_~[.I ..~_Ij . ~Vj = ~ttx-~ lr -- L(xj, vj)] with the last equality following from vj c g(xj), and where lj is the slope of the relevant tangent line to L(xj, • ). Letting j ~ ~ in the inequality L(xj, vj/2) >½[tz + L(xj, vj)] and using the continuity of L leads into a contradiction to (6.5), and completes the proof. [] Let/~ be as in (6.1) and we define a continuous function p(. ) on [a, b] by requiring that p'(x) = - l ( x ) p ( a ) =0.

for x ~ c, (6.6)

Theorem 6.2. Assume that the minimum in (6.1) is attained at a unique point a < c < b. Then (p, tz) which are defined in (6.1) and (6.6) provide a good solution, tz is the minimal long-run average-cost growth rate. Any solution of Yc(t)~ g(x( t) ), x(O)= Xo, is an overtaking optimal trajectory. Such a solution exists for every XoC [a, b].

Proof In order to show that (p,/~) is a good solution it is enough to demonstrate the existence of viable solutions to ~(t)~ g(x(t)), x(O)= Xo, for every Xo~ [a, hi. It follows from Proposition 6.1 and from standard results about differential inclusions that for every XoE(a, b) there exists a solution of ~ ( t ) ~ g ( x ( t ) ) , x(0) = Xo, in some time interval [0, ~]. The fact that vtg(a)

implies

v>0

v~g(b)

implies

v<0

and

then guarantees that there is in fact a viable solution in [a, b] for every initial value XoC [a, b]. The overtaking optimality of the solutions of ~ ( t ) c g(x(t)) will follow from Theorem 5.3 once we have proved that x ( t ) ~ c as t ~ in a uniform rate for all the solutions. But this follows from the fact that for every 6 > 0 there is an r/> 0 such that

x>_e+6

and

v~g(x)

implies

v--r/

and also for every 6 > 0 there is a v > 0 such that x-
and

vcg(x)

implies

v->v.

[]

28

A. Leizarowitz

Remark. The geometric interpretation of equation (3.2) which motivated the proof of Theorem 6.2 can be applied to more general cases. Let L ( . , .) be an integrand defined on R" × R " and we want to minimize ~or L(x(t), Yc(t))dt as T . o o for trajectories x(. ) which are bounded functions from [0, oo) into R". If L(x, v) grows to infinity sufficiently fast as Ixl Jr Ivl-, oo then it follows that all the relevant trajectories are uniformly bounded and contained in some ball, if the initial value is restricted to a bounded set. We can then define a function x ~ p(x) as in (4.7) and it will follow that p ( x ) ~ o o as [x[~oo. If the function p ( . ) is continuously differentiable and not merely Lipschitz continuous, then it follows that the minimal-cost growth rate is expressed by # = min L(x, O)

(6.7)

x~R n

which is a direct generalization of the scalar case result. The reason is that p(. ) has a local minimum Xo (since p(x) ~ oo as Ixl ~ ~ ) at which Vp(xo) = 0. However, ( - V p ( x ) ) is a slope of a tangent hyperplane to the function v ~ L(x, v) that goes through the point (/z, 0). The inequality ~z <_ min L(x, 0)

(6.8)

xE R n

must hold, and if strict inequality holds in (6.8) then the slopes of the above tangent hyperplanes are bounded away from zero, so that the equation Vp(x0) = 0 cannot hold in any point Xo. This shows that (6.7) holds in this situation, and also shows the validity of (6.7) if we consider the integrand L ( . , .) along with a constraint set K, provided that K is large enough. This discussion, together with the results of the present and next section, suggests the conjecture that the equality (6.7) holds in quite general situations for integrands in R ".

7.

Control Systems in R"

We consider the optimization problem in R ~ and demonstrate how explicit optimal quantities can be computed for a wide class of such systems. We begin by considering the following example. Example 7.1. We consider the minimization of~ T [½[~(t)[2+ l(x(t))] dt as T ~ where l ( . ) is a continuous function defined on K c R". In this case L(x, v) = l(x) +1Iv r and the Bellman equation (3.2) is

l(x) + min[½]v]2+ v. Vp(x)] : /z or equivalently

½i (°P) 2= t(x)-,,.

(7.1)

i=l \OXi/

It follows from (7.1) that -< min l(x). xEK

(7.2)

Optimal Trajectories of Infinite-HorizonDeterministicControl Systems

29

We define the set-valued function G(x) = {v e R": l(x) +½[v12+ Dp(x, v) =/~}.

(7.3)

If (p,/~) is a good solution, then there are viable trajectories x(. ) which satisfy 2(t)eG(x(t)),

x(t)eK

for

t->0.

(7.4)

If strict inequality holds in (7.2) then - m i n l(x) = - e < 0 xcK

and (7.3) and (7.4) imply that for a viable solution x(. ) the following holds Dp(x(t), 2 ( 0 ) <- ix - l(x(t)) <- - e for almost every t > 0, which contradicts the boundedness of p ( . ) on K since d -d~P(X(t)) = Dp(x(t), Yc(t))

a.e. in [0, ec).

Therefore we must have

l(x)

= min xcK

and p(. ) is a solution of (7.1) with this value of/z. The viability of solutions of 2 ( 0 e G ( x ( t ) ) will be achieved if p(. ) satisfies the boundary condition Vp(x) • nx > 0

for all

x • OK,

where OK is the boundary of K and nx is a unit outward normal vector to K at xeOK. The result concerning Example 7.1 generalizes to the following situation. Theorem 7.2.

Let the integrand L ( . , • ) have the form

L(x, v)= l ( x ) + g ( v ) , where l(. ) is continuous on K c R", g(. ) is strictly convex on R n, and g ( v ) / l v [~ as ] v ] ~ . Then the minimal-cost growth rate is /z --- g(0) + m i n l(x) (= min L(x, 0)). xeK

(7.5)

xcK

Let H: R" ~ R 1 be defined by H(~7) = m i n [ g ( v ) + v . ~7], 1)cR n

then the differential inclusion (3.4) has the form Yc(t) = V H ( V p ( x ) )

for almost every

x • K,

(7.6)

and if p(. ) is continuously differentiable in K then (3.4) reduces to the differential equation (7.6).

30

A. Leizarowitz

Proof The Bellman equation is min[g(v) + v. Vp(x)] =/x - l(x)

(7.7)

19

and since the left-hand side does not exceed g(0) we have /~ -< g(0) + rain l(x).

(7.8)

x~K

Let (p, tz) be a good solution of (7.7) and let x(. ) be a trajectory such that

l(x(t))+g(Yc(t))+Dp(x(t),2(t))=lz

for almost every

t>0.

(7.9)

(The existence of such a trajectory is guarantee d by the fact that (p,/x) is a good solution.) Integrating both sides of (7.9) over [0, T] and using the convexity of g(. ) we get

tz>-l forl(x(t))dt+g[l (x(T)-x(O))]+T[P(x(T))-p(x(O))] from which it follows that tx - g(O) + minx~ K l(x), by letting T - co. This inequality and (7.8) imply (7.5). It remains to prove (7.6). This, however, follows from the fact that 7 H ( ~ ) is equal to the value Vo which minimizes the expression [ g ( v ) + r l - v ] , thus 7H(Vp(x)) is the only point in the singleton set G(x) at every point where p(. ) is ditterentiable. [] Example 7.3.

Let the function h: Rn-~ R" be such that

v ~ g(v) = v. h(v) and

g(v)/Ivl-,~

is strictly convex as JvJ~oo.

(7.10)

We assume that h(. ) is continuously differentiable and consider the minimization of T

oh fo Ix(t) • ~x(-X)X(t)+x(t) " h(2(t))] dt as T-~oo. The constraint set K is a ball centered at the origin in R". Then our integrand is

L(x,v)=x"

(-x) x + v ' h ( v ) ,

xcK,

and the Bellman equation is x"

(-x)

x + m i n [ v , h(v)+v. Vp(x)]=tx.

(7.11)

In view of (7.10), if we choose

p(x) = - x " h(-x),

(7.12)

Optimal Trajectories of Infinite-Horizon Deterministic Control Systems

31

then it is easy to see that the minimum in (7.11) is attained at v = - x . To check that the differential equation (7.11) is indeed satisfied by p ( . ) in (7.12) we compute (recall (7.10))

g(-x)+ x" V g ( - x ) = g ( - x ) + x" h ( - x ) - x " (~x (-X))X =-x" (~x (-X))X ,

(7.13)

where we used the fact that the minimum in (7.11) is attained at v = - x . It follows from (7.13) that /x = 0 and thus p ( x ) = g ( - x ) and tx = 0 form a good solution. Since p(- ) is continuously differentiable, the differential inclusion (3.4) reduces to the differential equation

2(t) = -x(t) and all the solutions with Xo~ K satisfy x(t)~ K for all t->0, and converge, in a uniform rate to zero as t-~ co. Hence these solutions are the overtaking optimal trajectories for the optimization problem. Example 7.4.

We take in Example 7.3

h ( x ) = ixl m 2x

for an integer m---2, x ~ R ' . We then have

g(v) = v" h(v) = [vlm. We compute

Ohi/Oxj where

Oh_.~_k=l ~ x2) (m/2)l~ij'~-"~- 1 Oxj

1x 2)

" 2xixj.

Therefore

X" (~x(--X))X-~(k~=lX2)rn/2"q-(m--2)(~lX2)m/2 =(m-1

x 1

The minimization problem is thus to minimize o ~ - [ ( m - a ) l x ( t ) l m + l i c ( t ) ] m]

at,

T~oo.

Using a suitable change of variable t ~ cet we can consider the minimization of

Io

T[,

lx(t)lm+l

(t)l

]

dr,

T~oo,

32

A. Leizarowitz

for an arbitrary positive h. The result of the previous example shows that tz = 0 and the overtaking optimal trajectories are given by

x.:xoex,[ References 1. Brock, W. A., and Haurie, A. (1976). On existence of overtaking optimal trajectories over an infinite time horizon. Mathematics of Operations Research, 1:337-346. 2. Federer, H. (1969). Geometric Measure Theory. Springer-Verlag, Berlin. 3. Fleming, W. H., and Rishel, R. W. (1975). Deterministic and Stochastic Optimal Control. 4. Gale, D. (1967). On optimal development in a multi-sector economy. Review of Economic Studies, 34:1-19. 5. Koopman, T. C. (1965). On the concept of optimal economic growth. In The Economic Approach to Development Planning. Pontificiae Academiae Scientiarum Scripia Varia, Vol. 28, pp. 225-287. North-Holland, Amsterdam. 6. Leizarowitz, A. (1984). Control problems on infinite horizon. Ph.D. Thesis, The Weizmann Institute of Sciences, Rehovot, Israel. 7. Leizarowitz, A. (1985). Existence of overtaking optimal trajectories for problems with convex integrands. Mathematics of Operations Research, 3:450-461. 8. Leizarowitz, A. (1985). Infinite horizon autonomous systems with unbounded cost. Applied Mathematics and Optimization, 13:19-43. 9. Leizarowitz, A. (1985). Convergence of viable solutions of differential inclusions with convex compact graphs. SIAM Journal of Control and Optimization, 23:514-522. 10. von Weizs~icker, C. C. (1985). Existence of optimal programs of accumulation for an infinite time horizon. Review of Economic Studies, 32:85-164.

Accepted 11 September 1987