JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS: Vol. 86, No. 3, pp. 529-552, SEPTEMBER 1995

An Infinite-Horizon Multistage Dynamic Optimization Problem H. R.

BABAD 2

Communicated by L. D. Berkovitz

Abstract. Multiprocess problems are dynamic optimization problems in which there is a collection of control systems coupled through constraints in the endpoints of the constituent trajectories and through the cost function. Optimality conditions for such problems posed over a finite interval have already been derived. However, multiprocess problems arise, for example in the mathematical economics literature, in which one of the component processes operates over an infinite horizon. We give a proof of the relevant necessary conditions in the form of a maximum principle under mild and verifiable hypotheses and apply the theory to a two-stage problem in which an explicit dependence on the intermediate time (taken as a choice variable) is incorporated in the integrands of the cost functional.

Key Words. Dynamic optimization, maximum principle, multiprocesses, infinite-horizon problems.

1. Introduction Dynamic optimization problems arise, especially in the economic and biological sciences, which are defined over an infinite-time horizon. In the deterministic, continuous-time case, the performance index is described by an improper integral which may not necessarily converge. The requirement that this integral be convergent is therefore quite restrictive, as in for example, the discussion on the maximum principle for the infinite horizon by Pontryagin and his associates (Ref. 1). It is still possible to obtain necessary conditions for optimality over the infinite horizon in the form o f a maximum ~This research was carried out while the author was a Graduate Student at the Department of Electrical Engineering, Imperial College of Science, Technology, and Medicine, London, England. The author is gratefulto ProfessorR. B. Vinter for his adviceand helpfuldiscussions. :Research Associate, Department of Zoology, Universityof Oxford, Oxford, England. 529 0022-3239[95/0900-0529507.50/0 9 1995 Plenum Publishing Corporation

530

JOTA: VOL, 86, NO. 3, SEPTEMBER 1995

principle, without such restrictions, as in the Halkin classic paper in this field (Ref. 2). However, the following points must be noted. Firstly, the notion of optimality for the infinite horizon must be carefully defined. This is because, although the definition of optimality is unambiguous over a finite horizon, several nonequivalent definitions of optimality are available over the infinite horizon; see, e.g., Carlson and Haurie (Ref. 3) and Stern (Ref. 4) where the logical implications among the different definitions are also discussed. Since, in proving the necessary conditions, Halkin uses the weakest of the various definitions in the literature, we may conclude that the single-stage infinite-horizon maximum principle which he derives is valid for any of the other definitions of optimality which may be employed. Secondly, the finite-horizon transversality condition does not, in general, carry over to the infinite-horizon case by standard techniques, so where studies of the infinite-horizon transversality property have been made, they only provide results in special cases; see, for example, Refs. 5-11. We now consider whether general necessary conditions, in the spirit of the Halkin classic work, can be derived for multistage, infinite-horizon optimal control problems via the use of multiprocess theory as the latter appears to be ideally suited to applications of this kind. An optimal multiprocess problem is a dynamic optimization problem involving a collection of control systems coupled through constraints in the endpoints of the state trajectories and through the cost function. The development of a maximum principle for multiprocesses (see Refs. 12 and 13) extends the notion of the classical Pontryagin maximum principle and permits the solution of a wide range of nonstandard problems. Our first objective in this paper is to develop a maximum principle for multistage problems over the infinite-time horizon. We consider the simplest example of a multistage problem, namely a two-stage optimal control problem, in which one of the component processes operates over an infinite-time horizon,

fl J=

~o0 L,(t, x(t), u(t)) dt+

t0

L2(t, x(t), u(t)) dt.

(1)

I

Here, tl is the switching or intermediate time. We show that an optimal solution for the given infinite-horizon problem is still optimal when the data of that problem are restricted to a fixed-time interval subject to a terminal condition on the state. By reformulating the problem in terms of multiprocesses, we can use this property to prove general necessary conditions for optimality over the infinite horizon. This is achieved by applying the finite-horizon multiprocess maximum principle over strictly

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

531

increasing time intervals in order to construct a function which will be a suitable candidate for the costate function. Since the proof method can be generalized to problems with more than two stages, we have in effect a maximum principle for general multistage problems operating over an infinite-time interval. Our second objective is to show that this theory can be applied to twostage optimal control problems of the form

J=

f; o

Ll(t, x(t), u(t), tl) art+

ft

L2(t, x(t), u(t), tl) art,

(2)

1

where, in addition to the intermediate time tl being a choice variable, there is an explicit dependence in the integrands of the cost functions on this intermediate time; see Ref. 14. Standard optimality conditions of control theory, which accommodate changes in the dynamics only at fixed times, cannot be applied directly to such problems. Examples of such two-stage problems have been treated in the mathematical economics literature (see, e.g., Refs. 15-18), but with the assumption that the intermediate time is fixed and exogenous, i.e., it is taken as a given variable in the decision making process. The difficulties associated with an endogenous switch point (i.e., it is a choice variable in the decision making process) can sometimes be overcome by the following techniques where, to begin with, we solve a family of problems involving fixed times and then minimize over the times to determine the optimum values (two-phase optimization), or alternatively we reduce the free times to fixed times by transformation of the time variable. Thus, we see that in general two-phase optimization consists of freezing certain choice parameters, thereby reducing the problem to one which can be solved by application of the classical maximum principle and then minimizing a value function (the minimum cost as a function of the frozen parameter values) to determine the optimum parameter values. However, the drawbacks to these techniques are that two-phase optimization requires tractable formulas describing the value function relative to the intermediate times (which cannot be done for complicated problems) and that time transformation techniques are typically applicable only when certain regularity conditions are imposed on the data. This rules out significant applications. Optimal multiprocess theory overcomes these drawbacks in that firstly no explicit reference is made to value functions, and thus implementation of optimization procedures will not depend on availability of such formulae, and in that secondly it treats dynamic optimization problems where the data are merely measurable in the time variable. This is an important feature of the theory.

532

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

Although Tomiyama and Rossana establish necessary conditions for the two-stage problem described by (2), they do so under severe and somewhat restrictive hypotheses, namely, the assumptions that the data and the cost functions are continuously differentiable in the x, t, tl variables and also under a smoothness assumption on a certain value function introduced to decouple the stages. This latter condition is difficult to verify in general. On the other hand, by viewing trajectory segments between intermediate times as component trajectories, we arrive at an optimal multiprocess problem for which the new theory supplies optimality conditions under mild, verifiable hypotheses expressed in terms of the data themselves. Presence of the intermediate time tl in the cost is simply dealt with by state augmentation techniques. Here, then, we see immediately the advantages of applying multiprocess theory instead of classical methods of analysis.

2. Preliminaries

The notation used follows that of Clarke (Ref. 19). We begin with the following definition of generalized gradient. Definition 2.1. Let N be an open subset of Rk, let x be a point in N, and let f: N ~ be a locally Lipschitz continuous function. Then, the generalized gradient af(x) o f f at x is the set

Of(x)=c~

Vf(xi)lxi---} x, Vf(xi)exists for i= 1,2 . . . .

Jl"

(3)

Definition 2.2. Let C be a nonempty subset of X. Then, its distance function [i.e., dc(" ) : X ~ ] is defined by

dc(x) = inf{ IIx- ell: c~ C}. function de is nonsmooth; however,

The Lipschitz constant 1 on X; i.e.,

Idc(x) -dc(y)l < IIx-Yll,

(4) it is Lipschitz continuous with

for all x, y~X.

Definition 2.3. Let C c R~ be a closed subset of ~k, and let x be a point in C. Then, the normal cone to C at x, written Nr (x), is

Nc(x)=cl{ U>_ ~2Odc(x)}.

(5)

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

533

We require analysis of generalized gradients and normal cones in order to obtain necessary conditions for the solution of multiprocess problems. The following formulas for the normal cones of certain sets which arise in optimization will be useful in our study of two-stage problems. For simplicity, we limit our attention to the convex case, though the formulas do have analogues for general closed sets.

Proposition 2.1. (i)

For closed, convex sets C 1 c ~k and C2 ~ ~l, and points a~ C1 and b~C2,

Nc~ • c2(a, b) = Nc,(a) • Nc2(b). (ii)

(6)

For any closed, convex subset C c R ~ x ~ and a point (a, b)~C,

N(~.... y~l(~,y)~C}((a, a, b))c {(p, q, r)[(p+q, r)~Nc((a, b))}.

(7)

Similar arguments to those employed in obtaining the above results give

N{(x,x,y,y)l(x,y)EC}((a, a, b, b))c {(p, q, r, s)l(p+q, r+s)~Nc((a, b))}.

(8)

3. Multiprocess Theory The notation of this section follows that of Clarke and Vinter (Ref. 12). 3.1. Multiproeesses.

Consider positive integers k and n,., m~, i =

1 , . . . , k , subsets U ~ of • x R m,, i = l , . . . , k , subsets X ~ of ~ x R n,, i= 1 , . . . , k, and functions ~bi : • x ~ nix ff~rai---~~ hi. Since frequent reference is made to points in product spaces, and to products of product spaces, we denote a point ((al, bl . . . . ), (a2, b2 . . . . ) . . . . . (ok, bk . . . . )) by {a~, b,.. . . . }. Definition 3.1. A multiprocess is a k-tuple {rg, rl,e y~(" ), wi(" )}, each element of which comprises left and right endpoints rg, r~ of a closed interval, an absolutely continuous function yi(" ): [r~, r~ ] ~ R n', and a measurable function wi(. ): [rg, r ~ ] ~ m' such that

)i(t) = q~i(t, yi(t), wi(t)), W i(t) ~ U~, yi(t) 6X~,

a.e. t~[r~, r~], a.e. te[rg, r~ ],

Vte[rg, r~].

Here, X~ denotes {x: (t, x)~Xi}, etc. The individual elements are component processes, the yi (")'S component trajectories, the wt (-)'s component control functions, and the intervals

534

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

[r~, r]] component time intervals. The processes or state trajectories are admissible if the y;(-)'s also satisfy given endpoint constraints. 3.2. Optimal Multiprocess Problem. Let Li:Rx[~n'• 1 , . . . , k, and f: E ~ R be given functions in which E = I-I(R x R x ~nix Rni),

i=

i

and let A c { { r ~ , r ~ , Y0, i yli } ~EI z'~~ to, e i = 1 , . . . , k} be a given closed constraint set. The optimal multiprocess problem is: Minimize the performance index t~r

f({r~, r],9 yt(r~), wi(r~)}) + ~

__J~Li(t, y,(t), wi(t)) dt,

over multiprocesses {r~, r], y~(-), w,(. )} which satisfy i

, yi(r0),

yi('l'l )} cA.

3.3. Essential Values. For free-time dynamic optimization problems, we can expect the optimality conditions to incorporate conditions on the boundary values of functions constructed from the costate variables. When the data are merely measurable in the time variable, the elementary definition of boundary value (namely, evaluation at a point) cannot be adopted, basically because it is not robust under the limiting arguments employed in the derivation of optimality conditions. Instead, we must interpret the boundary values as essential values. Similarly, when the data are discontinuous in the time variable, the standard condition on the maximized Hamiltonian function is replaced by an inclusion involving the essential values of this function. Let I c R be an open interval, t a point in/, and g: I---~1~k an essentially bounded measurable function. The set of essential values of g at t, denoted esss_~tg(s), is defined as follows. Definition 3.2. For 7ER k, ?'Eesss~tg(s) if and only if, for any E>O, the following set has positive Lebesgue measure: {s:

t-E
[y-g(s)]
If a point lies in co esss~t g(s), we say that it is a convex essential value of g at t. If the function g has finite left and right limits at t [written g(t-) and g(t+)], then ess g(s) = {g(t-), g(t+)}. g-el

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

535

It is clearly the case that, if g is continuous at t, then ess g(s) = {g(t)} ; S---~ t

i.e., the essential value is merely the value of the function. 3.4. Maximum Principle for Multiproeesses. We now state the multiprocess maximum principle for the finite-horizon case; see Ref. 12. To formulate the hypotheses, it is convenient to introduce the augmented velocity functions qSi= [~bi, Li], i = 1 , . . . , k. (HI)

(H2) (H3)

For each x~ ~"', qSi(', x,. ) is s x ~ measurable for i= 1 , . . . , k, where La denotes the class of Lebesgue subsets in R, and denotes the class of Borel subsets in R"~'. U;, i= 1. . . . . k, are Borel measurable sets. There exists a constant K such that, for i = 1. . . . . k,

Ic~i(t,y, w)l < K , whenever (t,y, w ) ~ R x X ~ x U~. (H4)

Ic~i(t, y, w)-~i(t, y', w)[ < K l y - y ' I , whenever (t,y, w), (t,y',w)~R•

U~.

(H5) f is locally Lipschitz continuous. Define the Hamiltonian functions Hi, i= 1. . . . . k, as

Hi(t, x, u, p, •) =p" r t, X, u) - ~,Li( t, x, u). Theorem 3.1. Multiprocess Maximum Principle.

Let

x,(. ), u;(. )} be an optimal multiprocess. Suppose that graph {xi(" )} c interior {X i } and that Hypotheses (H1) to (H5) are satisfied. Then, there exist a real number ~ equal to 0 or 1, real numbers hio,h], i=1 . . . . . k, and absolutely continuous functions Pi : [r~, r~ ] ~ ~ "' , t"= 1 , . . . , k, such that Z + ~ Ipi(r])l > 0 i

and, for i = 1. . . . . k,

-pi(t)eOxHi(t, xi(t), ui(t),pi(t), A,),

a.e. te[r~, r] ],

(9)

a.e. t~[r~, r] ],

(10)

Hi(t, xi( t), ui( t), pi( t), ~.) = m a x Hi(t, xi(t), w, pi(t), A), we u~

536

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

h~o~coesslsupHi(t, x/(ro), w, pi(zo), 3,)}, t--*r~[we U~ i

i

t

9

}

(11)

h~sco ess9 sup H~(t, xi(r~), w,p;(rx), i 3,) ,

(12)

{_ffo, hi,i p,-(to), i -pi(r] )} ~N^ + 3` Of.

(13)

The normal cone NA and the generalized gradient Of are evaluated at the i xt(r] )}. point {r~, rl,i xi(r0), Note that all the ingredients of the traditional maximum principle, namely, costate functions Pi ("), costate differential equations, and maximization of the Hamiltonians, which separate out into statements about individual component processes, are present in the multiprocess maximum principle. The fact that the component processes in the optimal multiprocess problem are coupled through the endpoint constraint and the cost function gives rise to a corresponding coupling of the component costate functions through their endpoints via the multiprocess transversality condition { - h ~ , h,, ~ p;(r0), -pi(~ )} ~NA + Z 0f.

The formulation of the optimization problem incorporates the constraints

yl(t)eX~ mainly for the purpose of hypothesis refinement. A consequence of the theorem is that the assertions remain valid if { r~, r], xi ('), ui ( ' ) } is merely a local solution to the given problem in the sense that it is minimizing with respect to all multiprocesses {r~, r~, y;(. ), wi(" )} that satisfy graph {y,. } c graph {xi } + EB, where B is the open unit ball. 4. Statement of the Problem

We consider the following performance index defined over the infinite horizon:

I=

Ll(t, x(t), u(t)) dt+ o

L2(t, x(t), u(t)) dt,

(14)

I

where L,-: N x R" • Nm--~N, i= 1, 2, are given functions. We wish to minimize (14) subject to the state equations

2(t)_~f~(t,~ x(t), u(t)), - t A ( t , x(t), u(t)),

a.e. te[to, td, a.e. t~[tl, oo),

(15)

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995 I

I

Vt~[to, h],

x(t)e l.Xxi',

Vt~[tl, ~).

537 (16)

We also wish the minimization to be subject to the control constraints

u(t)e5 U),

a.e. a.e.

U 2,

t~[to, tl], te[h, ~),

(17)

and boundary conditions

X(to) ~ Co, (tl, x(h)) ~ G .

(18)

Here, the f.: •• R"• R"-~R n, i = 1 , 2 , are given functions; U i c R x R ", X i c R x R ", CocR", C I = R x R" are given sets [X~ denotes {x: (t, x)eX"}, similarly for U~]; the state x(. ) is absolutely continuous on [to, ~ ) ; and the control u(. ) is measurable on [to, ~ ) . The intermediate time tl is a choice variable, constrained to satisfy to < tl < oo. Conditions on f~ and L~ will be stated in Theorem 5.1 in the next section. Any triplet (x, u, tl) satisfying (14) to (18) is termed admissible. If in addition it is minimizing, it is termed optimal. Notice that this can be set up as an infinite-horizon multiprocess problem (cf. Section 3.2) with component dynamical equations

21=7q,

~2=A,

in which the x;s are segments of the state trajectory, etc., cost function

f

~i Lt( t, xi(t), ui( t) ) dt,

and endpoint constraint (%.1, %.I, ,t.2, rl, 2 Xl(VO), 1 xl(rl), 1 x2(ro), 2 x2(r2)) ~A,

on the multiprocesses { ~ , ~-~,x;(. ), ug(. )};= 1,2 considered. Here, the set A is i

i

A = {{r~, r,, xi(ro), xi(r])} : v~ = to, rl = r2o= tl, r~= 0% x,(r~)eC0, x,(rl) = x2(r2), x2(r~) free}.

(19)

As previously mentioned, there is no unique way to define optimality when we are dealing with problems having infinite horizon. Issues are involved here of whether we require a control to give rise to convergence of the improper integral in the cost function and, if not, what is meant by the term "optimal." It is natural to adopt as definition of optimal control as weak a notion of optimality as is compatible with the maximum principle

538

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

that we have in mind, for then this maximum principle will also serve as a necessary condition for other, stronger notions of optimality which may be employed. We work with a weak concept of optimality introduced by Halkin (Ref. 2), which does not require convergence of the improper integral in the cost function.

Definition 4.1. We say an admissible triplet (x*(-), u*(-), t]~) is weakly optimal if, for every admissible triplet (x, u, 4), every T e J (J= [q, oe)), and every 9 > 0, there exists a r e J with r > T for which

f;

Ll(t, x(t), u(t)) dt+

0

f;

L2(t, x(t), u(t)) dt

1

L~(t, x*(t), u*(t)) dt+

L2(t, x*(t), u*(t)) d t - e.

(20)

>-" to

5. Infinite-Horizon Multiprocess Maximum PrincipLe This section provides a statement of the necessary conditions on optimal triplets for the infinite-horizon problem. Define the Hamiltonian function Hi, i = 1, 2, for each stage by

H,.( t, x, u, p, /1.)=p" f .( t, x, u ) - ~,Li( t, x, u), and define the augmented velocity function ~ by ~(J~,Li), where j~: Rx R"x R " ~ R "+1, i= 1, 2.

Theorem 5.1. Let (x*(.), u*(. ), t*) be the optimal triplet for the infinite-horizon problem of Section 4. Assume that: (HI)

(H2) (H3)

For each x e R n , f ( ' , x , ") is & a x ~ measurable for i=1,2, where 2~ denotes the Lebesgue subsets in R and ~ denotes the Borel subsets in R m. U;, i= 1, 2, are Borel measurable sets. There exists a constant K such that, for i = 1, 2, IX(t, x, u)[
(H4)

[j~(t, x, u ) - f ( t , y ,

~xx~x u~.

u)[ < g l x - y l ,

whenever (t, x, u), (t,y, u)e

Let graph{xi (')} c interior{X i}, for i = 1, 2. Then, there exist real numbers Z equal 0 or 1, h0, h,, and a function p(. ): [0, oo)~R n, which is locally

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

539

absolutely continuous on [0, t*), [t*, ~ ) such that ~,+ IIp(.)liL~>0, and such that: (i)

(ii)

-p(t)et~xHl(t, x*(t), u*(t),p(t), ;r -p(t)edxH2(t, x*(t), u*(t),p(t), ~),

te[to, t*], a.e. te[t*, ~ ) ; a.e.

(21a) (21b)

Hi(t, x*(t), u*(t),p(t), ~.) =max Hi(t, x*(t), w,p(t), A.),

a.e.

te[to, t*],

(22a)

n2(t, x*(t), u*(t), p(t), ~.) =max H2(t, x*(t), w,p(t), A),

a.e.

te[t*

(22b)

weU]

oo);

w~ f 2

(iii)

ho~coesstsupH~(t,x*(t*),w, limp(t),~.)}, t~tl I. wEUt

t-'*tl [.w~Ut

(iv)

p(to)~Nco, (ho-h,,

The normal cone (t*, x*(t* )).

\

Nco

(23a)

t~rtl

\

t;tl

-lim p(t)

+ lim p(t)leNc ~.

is evaluated at

x*(to)

and

Nc,

(24) is evaluated at

Equations (21) are the costate equations and Eqs. (22) give the condition for the maximization of the Hamiltonian. The essential values, required for the evaluation of the normal cones, are given by (23), and the transversality conditions are given by (24).

6. Proof of Theorem 5.1

We obtain the maximum principle over the infinite horizon by combining two lemmas which we shall state and prove, but first we introduce some notation. Given Te[tl, ~) and ~eR n, we denote by Pr, e the finite-horizon fixed endpoint problem obtained by restricting the interval of integration in the infinite-horizon problem to [0, T] and by introducing the terminal condition

540

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

x(T) = ~, namely: Minimize the performance index Ll(t, x(t), u(t)) dt+ 0

Lz(t, x(t), u(t)) dt, 1

subject to

to
fc(t) -

ffl(t, x(t), u(t)), ~IrE(t, x(t), u(t)),

x(O) E Co,

a.e. te[to, h], a.e. tE[tl, 00),

(tl, x(h))~C1,

x(T) = ~.

Optimality for the finite-horizon problem Pr.r is defined in the obvious way. Given an admissible triplet (x, u, t~) for the infinite-horizon problem and also T~[fi, oo), we denote by (x, u, t~)r a triplet in which the first two arguments are the restrictions of the original state trajectory and control functions to [0, T]. The first stage is to prove the following lemma. Lemma 6.1. If (x*('), u*(. ), t*) is weakly optimal for the infinitehorizon problem, then given any T>ff, (x*('), u*(" ), t*)r is optimal for Pr, x*(T) .

Proof. Assume that the assertion is false. Then, there exist T > t*, E>0, and a triplet (~, ~, f o r for Pr, x*(r), with to< tl < T, such that

fl~l

Ll(t, ~(t), a(t)) dt+

0

<

~T

L2(t, ~(t), a(t)) dt

I

Ll(t, x*(t), u*(t)) dt

L2(t, x*(t), u*(t)) dt - e.

(25)

Define an admissible triplet (x, u, tl) for the infinite-horizon problem according to tl = tl and x(t)

5~(t), [x*(t),

u(t)=Sa(t),, [u*(t),

a.e. t~[to, T], a.e. t~[T, m), a.e. t~[to, T], a.e. t~[T, oo).

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

541

Then, for all r > T,

f

Ll(t, x(t), u(t)) aft+

o

=

f/

Lz(t, x(t), u(t)) dt

I

ft'

Ll(t, ~(t), a(t)) dt+

o

+

<

L2(t, ~(t), ~(t)) dt I

L2(t, x*(t), u*(t)) dt

I,o;

Ll(t, x*(t), u*(O) dt +

I,"

L2(t, x*(t), u*(t)) d t - e,

1

by Inequality (25). This contradicts the weak optimality of u*(. ), t* ). The lemma is proved.

(x*(-),

[]

The above result is clearly a variation on the Bellman optimality principle (Ref. 20). In effect, we have shown that, if (x*, u*, t*) is an optimal solution for the infinite-horizon problem, then (x*, u*, t*) is also optimal for any finite restriction of the problem. The second stage is to prove the following lemma. Lemma 6.2. Let (x*(-), u*(. ), t*) be an admissible triplet. If for any T> t*, (x*(-), u*(. ), t*)r is optimal for Pr, x*(r), then the conclusions of the infinite-horizon multiprocess maximum principle (Theorem 5. l) hold. ProoL

Step 1. Necessary Conditions for a Sequence of Finite-Horizon Problems. Let T 1, T 2, . . . be a strictly increasing sequence of real numbers in It*, oo) such that T J ~ as j ~ o o . For eachje{1, 2 . . . . }, we have that (x*(.), u*(. ), t*)rJ is optimal for the associated finite-horizon fixed endpoint problem PrJ.x*~rJ). Step la. Necessary Conditions for the Finite-Horizon Problems. We now apply the necessary conditions of optimality to each of the above finitehorizon problems PrJ, x*(rJ). From the finite-horizon maximum principle for multiprocesses (see Section 3.4), we know that, for each j, there exist real numbers )~Jequal to 0 or 1, h~, h{, and p/: [to, T j ] ~ R", absolutely continuous on [to, tl*) and [t*, T j], such that

s + [p/(to)[ + Ip/(t* )[ > 0

542

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

and such that:

(i) (ii)

-lY(t)ecg~Hl(t, x*( t), u*(t), pJ (t), ,~J), a.e. te[to, t*], -pJ(t) EO~H2(t, x*(t), u*(t), pJ (t), ;d), a.e. t6[t*, TJ]; Hi(t, x*(t), u*(t),pJ(t), M) =max H~(t, x*(t), w, pJ(t), ,V), a.e. te[to, t* ],

(26a) (26b)

(27a)

wE U~

H2( t, x*(t), u*( t), pJ ( t), s =max H2(t, x*(t), w, pJ(t), U),

a.e.

tE[t* TJ];

(27b)

w E U t2

t~tl LweUt

tTtl

t-*tl L w ~ U t

(iv)

PJ(t~176

t~tl

hj~

t+,,

The normal cone Nco is evaluated at x*(t0), and

/

(29)

Ncl is evaluated at

(t*, x*(t* )). Conditions (26) to (28) follow directly from the multiprocess maximum principle. Notice that, by asserting that the pJ's are absolutely continuous on the closed interval [t ~', TJ], we have effectively taken the right-continuous version of the concatenation of the component costate functions obtained from the multiprocess maximum principle. Step lb. Computation of Normal Cones. From this point in the proof, we employ the notation r(t-), r(t +) to denote left and right limits of the function r(. ) defined on an interval containing the point t. We may write the multiprocess transversality condition as

{ (hJo,pJ ( to), -pJ ( t*-) ), (-h~ ,pJ(t*+),-pJ(TJ))} eNy, ((t~, x*(to), x*(t*)), (t~, x*(t~ ), x*(TJ))), where /~= {((t, y, z), (t', y', z'))~ R2(1+"+"):

y~Co, t = t', z=y', z'=x*(TJ)}.

In view of Proposition 2.1 (i), we have pJ (to) ~ Nco

(30)

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

543

and

(hio, -pJ(t*-), -hA, pJ(t* + )) eND(t*, x*(t* ), t*, x*(t* )), where

D:={(t, y, t', y'): (t, y)=(t', y'), (t, y)eG }. By Proposition 2.1 (ii),

(hJo, -pJ (t*-), -hA, pJ (t* +)) e{(a, y, a', y'): ((a + a ' ) , ( y +

y'))eNc~(t*,

x*(t*))}.

It follows that

(hio-h~, -pJ(t*-) +p/(t*+))eNc~(t *, x*(t*)).

(31)

(30) and (31) are the required transversality conditions satisfied along the sequence of finite-horizon problems that we consider. Step 2. Conclusion: Infinite-Horizon Necessary Conditions. It remains to derive the necessary conditions of optimality for the infinitehorizon problem by passage to the limit. We merely sketch the proof. Full details are provided in Ref. 21. Note that the condition

AJ--~IpJ (to)l + Lp/(t*)l

>0

can be normalized to

I~Jl + Ip/(t0)t + IpJ(t*)l = 1, by scaling the multipliers. Step 2a. Asymptotic Normalization. For each j, we have ~,J= 0 or 1. By extracting a subsequence, we can arrange that the {~,/} converge to a limit. We call this limit ~,. Clearly ~,= 0 or 1. By further extraction of subsequences, we can also arrange that pJ(to)---,p and that p/(t* +)--*/~, for points p and/~ satisfying ~ + l P l +1/~1 = 1. Step 2b. Construction of Costate Function q (.). We now consider the costate functions and construct a costate which satisfies the necessary conditions over the infinite horizon. Proofs of the Gronwall lemma and Ascoli theorem may be found in standard texts e.g., Refs. 22 and 23, respectively.

544

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

(a) We can show via the Gronwall lemma that, for each k, the sequence of functions p J(. ), j=k, k + 1. . . . . is uniformly bounded on [to, t*) and the fixed subinterval [tl*, Tk]. We may also deduce from the differential equations for the p J(. )'s that they are uniformly Lipschitz continuous on [to, t*) and [t*, Tk]. (b) Repeated application of the Ascoli theorem over fixed subintervals [tl*, T k ] results in a nested family of subsequences o f p I (t), namely, (p l,n(. ))nOO=l D (p2,n(,))net)= 1 ZD" ""

with the following properties: (bl) (b2)

for fixed k, terms in the sequence (p/"(-))~=1 are selected from (P J(" ))~k, where pJ(.) is the original sequence; for each k, pk'"(t)~qk(t) uniformly as n ~ over [t*, Tk], where qk(t) is Lipschitz continuous.

Furthermore, since the sequences are nested, qk(. ) and q J(. ) coincide on [t*, T k] for j > k . We can similarly show that, since the p J( - ) , j = 1, 2 . . . . . are uniformly bounded and uniformly Lipschitz continuous over [to, t* ), a subsequence can be chosen which converges to some Lipschitz continuous function q~ (c) Now define the function q('): [to, t * ) u [t*, oo)~R" as follows:

q(t)=~q~ ~qk(t),

t~[to, t*), t~[t*, ~),

where k is such that Tk> t. Evidently, the definition of q(- ) on [to, o~) is independent of k. Take any t>t*; then, t lies in some interval [t~', Tk], where k is the minimum value such that Tk> t; and, as we have just shown, qk(t) = lim

n--~ oo

pk'"(t),

over [t*, Tk].

We know by construction of the subsequences that eachpk"(t), n = 1, 2 , . . . , satisfies the necessary conditions (26) to (29) over It*, Tk]. We need to show that q~ and qk satisfy the necessary conditions. (cl)

Consider

--pk'n(t) =pk'n(t) " fx (t, x(t), u(t))- XLx(t, x(t), u(t)), for some fx ("),/Zx (.). Using the absolute continuity and uniform convergence of each p~", we can apply the Lebesgue convergence theorem (see, e.g., Ref. 23) to show that, for each k, qk(. ) satisfies condition (26), similarly for qO(. ). Therefore, by construction of q(. ), it satisfies the costate equation over [to, ~).

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995 (c2)

545

We have, for eachp~'n(t), n = 1, 2, . . . , and a given we U 2, that

H(t, x*(t), u*(t), pk"(t), ~) >_H(t, x*(t), w, pk"(t), ;~),

a.e.

te[t*, Tk].

Since the inequality holds along the sequence, it holds for the limiting value of p k., by the continuity of H. Therefore,

n (t, x*(t), u*(t), qk (t), A) > H(t, x*(t), w, q* (t), Z). Since this holds for any we U 2, it holds as a maximum over all we U 2, i.e.,

n(t, x*(t), u*(t), q*(t), Z)=max H(t, x*(t), w, q* (t), Z). we U 2

This is true for each k and similarly for qO; therefore, q(. ) satisfies the maximization of the Hamiltonian condition (27) over [to, c~). (c3) We have that, for any fixed k, (28) holds when pk,~(. ) replaces pJ for n = 1, 2 , . . . . Passing to the limit [this is justified by the upper semicontinuity of the convex essential value (Ref. 24, Lemma 1.2)], we see that (28) remains valid when q replaces p:. (c4) We know that, for j = l , 2 , . . . , p J ( ' ) satisfies pJ(to)e Nco(x*(to)). In view of the upper semicontinuity of the normal cone to a convex set, passage to the limit is valid; thus, q(to)eNr Similarly, we can deduce that

(ho- hi i -q(t* -) + q(t* +)) eNc,. (c5)

It is evident too that

q(to)=ff and q(t *+) =/3; see Step 2a. So,

;t+ IPl +1~1 =1. Thus, we have constructed a costate q ( . ) that satisfies the necessary conditions over the infinite horizon. [] The theory can obviously be extended to cover any performance index of the form

L,(t, x,(t), u,(t)) dt+ i

i- I

L~+l(t, x~+l(t), u~+l(t)) dt, In

where transversality conditions for the intermediate times t~ . . . . . tn can be obtained by defining constraint sets C~ . . . . . Cn § ~ in a similar fashion to the Cl of the theorem.

546

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

7. Application of the Infinite-Horizon Theory In this section, we consider an example of the application of the infinitehorizon multiprocess maximum principle, namely, a two-stage optimal control problem where the switch point is a choice variable and appears as an argument in the integrands of the performance index. Previously, necessary conditions for problems of this type have been obtained by Tomiyama and Rossana (Ref. 14) over the finite horizon. Using a multiprocess formulation, we show that general necessary conditions can be obtained over the infinite horizon under relaxed hypotheses. The problem considered by Tomiyama and Rossana (Ref. 14) is to find a triplet (x*, u*, t*) that maximizes the performance index

J=

~ttl Ll(t, x(t), u(t), tl) dt+ ~l ~ Lz(t, o 1

x(/), u(t), tl)

dt,

subject to the state equations

:~(t) = I fl( t' x( t), u( t), tl), (A(t, x(t), u(t), tl),

a.e. a.e.

te[to, tl], te[tl, cr

the boundary condition

X(to)~Xo, and the control constraint

u(t)~

~U1c-~ m, U2~R '~,

a.e. a.e.

t~[to, tl], t~[tl, oo).

In the original formulation, the functionsfi, Li, i= 1, 2, are at least continuously differentiable in x, t, tl and continuous in u, X0 is a nonempty dosed subset of ~", and Ui, i= 1, 2, are closed subsets of R'~. A triplet which achieves the maximum of the performance index over triplets satisfying the constraints of this problem is said to be optimal. Note that tl is a choice variable to be chosen optimally and that the asterisk denotes optimal quantities. It is assumed that an optimal control triplet (x*, u*, t* ) exists, where to < t* < ~ . We remove the explicit t~ dependence by state augmentation. Define L ~ mZ$ `

JOTA:

VOL. 86, NO. 3, SEPTEMBER 1995

547

An equivalent formulation is as follows: Minimize the performance index

f

/~l(t, x,(t), u,(t), x3(t)) dt+

0

/:2(t, x2(t), u2(t), x4(t)) dt,

(32)

1

subject to ~,(t) = fl(t, x~(t), ul(t), x3(t)),

a.e. te[to, td,

(33a)

~2(t) =f2(t, x2(t), u2(t), x4(t)),

a.e. t~[4, oo),

(33b)

~3(t) =0,

x3(4) = 4,

te[to, 4],

(33c)

~4(t)=0,

x4(4)=4,

te[4, ~ ) ;

(33d)

ul(t)~U~,

a.e. tS[to, 4],

u2(t)~U 2, a.e. t~[tl, oo), xl(to)~Co,

x~(t)eX~,

all t~[to, tl],

x2(t)~X 2, all t~[4, oo);

(tl, Xl(tl))~C1.

(34a) (34b) (35)

The minimization is conducted over multiprocesses {(to, 4, x,(" ), x3(" ), Ul(" )), (t~, t2, x2(" ), x4(" ), u2(" ))} subject to the constraint set A, defined by A = {(to, 4, xl(to), xl(tl), x3(to), x3(tl)), (t[, t2, x2(t ~), x2(t2), x4(t~ ), x4(t2)) : tl = t~, t2 = ~ ,

xl(to) ~ Co, x1(4)= x2(t[ ), x3(to) free, x3(4)

=

tl = x4(t~ ), x4(t2) free}.

(36)

Here,/:i : R x R n x R m x ~ R andJ~ : R x R n x E~n x ~ R n, i= 1, 2, are given functions and UecRxRm, x i c R x R ~ , i = 1 , 2 , are given sets; C o c R ~, C, c R x R n are given dosed endpoint constraint sets; the intermediate time t~ is a choice variable, constrained to satisfy to < t~ < ~ , where to is fixed. Note that the state is continuous at the switchpoint, i.e., Xl(4)=x2(4). It is important to realize, however, that by reformulating the two-stage problem as a multiprocess problem, we can relax the smoothness conditions imposed on the functions to ones of Lipschitz continuity. The following theorem provides necessary conditions of optimality over the infinite horizon for this particular problem. Define the Hamiltonian function H for each stage by

Hi(t, x, u, p, tl)=Pi "f,'(t, x, u, t~) +pi+ 2 "J~+2(t, x, u, 4) +~,Li(t,x,u, 4), i=1,2,

548

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

where p(t) is the costate. Note that this reduces to Hi = pi . f ' + ,~Li,

i = 1, 2,

since f3 =)q = 0. Define the augmented velocity function j~ = (fi,/~i), i= 1, 2, where ~ : I~x W ' x I~"' x I~..-*R "+1.

Theorem 7.1. Let ((x*, u*, x*), (x*, u*, x~')) solve the reformulated problem. Assume that: (HI)

For each (x, t l ) e ~ n x R,fi(", x, ", ti)

(H2) (H3)

is Aa x ~ measurable for i = 1, 2, where ~ denotes the Lebesgue subsets in • and ~ denotes the Borel subsets in ~m. U i, i-- 1, 2, are Borel measurable sets. There exists a constant K such that, for i= l, 2,

If~(t, x, u, tl)l
Ifi(t,x,u,t,)-fi(t,y,u,h)l
Let graph{x; (.) } c interior{X / }, for i = 1, 2. Then, there exist real numbers ). equal 0 or 1, h~,h2, and absolutely continuous functions pff-): [/0, t*]-+ R n, P2(" ): [t*, 00)..., [~n, P3(" ): [to, t~' ] ~ R n, P4(" ): it*, 00)--+R n, such that 3,+ Ipffto)l + IpE(t~' )1 + [pffto)l + Ip4(t* )[ > 0 and such that: (i)

-bl(t) ~0~, Hi(t, x* (t), u* (t),pl(t), x* (t)),

a.e. t~[to, t*],

(37a)

-h(t) ~2HE( t, x* ( t), u* ( t), p2(t), x* (t)),

a.e. t~[t~, ~ ) ,

(37b)

-/~3(t) ~C~3Hl(t, x~ (t), u~ (t), pfft), x~' (t)),

a.e. t~[to, t*],

(37c)

a.e. te[t*, 0o);

(37d)

-/h(t) e Ox,Hfft, x* (t), u* (t), p2(t), x* (t)),

J O T A : V O L . 86, N O . 3, S E P T E M B E R

(ii)

549

1995

Hi(t, x*(t), u*(t),pl(t),x~(t)) Hi(t, x*(t), w, pl(t), x*(t)),

a.e.

t~[to, t~],

(38a)

a.e.

te[t~, ~ ) ;

(38b)

}

(39a)

h2~coesslsup2H2(t,x~(t~),w, p2(t*),xZ(t*))};

(39b)

=max weU~

H2(t, x* (t), u~ (t),p2(t), x* (t)) =max

w ~ Ut2

(iii)

H2(t, x* (t), w, p2(t), x* (t)),

I

h~eco ess suE t~tl ~wcUt

H,(t, x*(t*), w,p~(t*),x*(t*)) ,

t~tl ~wEUt

(iv)

p~(to)eNco,

(40)

(hi - h2-p3(t'~ ) +p4(t*), -pl(t* ) +p2(t* )) eNc,.

(41)

The normal cone

Nco is evaluated at (x*(to)); No1 is evaluated at

(t*, x~*(t~')). Remark 7.1. Note that ((x*, ul* , x3* ), (x*, u*, x*)) is the solution to the given problem where X1~ =X*[ [t0,t7],

Ut =U*I t'0,t7]'

X* =x*i t'7,o~),

U* =u*i t'7,o~,

X*= t*i [t0,'t]'

x*=t~[ tt7.o~)"

Remark 7.2. Note that, if we maximize the performance index directly as in Ref. 14, the usual maximization condition of the Hamiltonian is replaced by the minimization condition, and the infimum of Hi replaces the supremum in the essential value inclusions. Proof of Theorem 7.1. Conditions (37) to (40) follow from a direct application of our infinite-horizon multiprocess maximum principle (Theorem 5.1) to this particular two-stage problem. We derive the conditions for a normal cone at Cl. This follows closely from Step lb in the proof of Lemma 6.2. We may write the multiprocess transversality condition as {(hi,

-Pl ( t* ), --p3( t* ), -h2 , p2( t* ), p4(tl*)) }

eNTx (t*, x* (t*), x* (t*), if, x* (t*), x* (t*)),

550

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

where

~:={(t,y,z, t',y',z'): t = t ' = z = z ' , y = y ' ,

(t,y)~Ci }.

By Proposition 2. l(ii), we obtain

(hi, -p, ( t* ), -p3( t* ), -h2, p2( t* ), p4( t* )) ~{(a, fl, 7, a', fl', 7/): (a +ct' + 7f+ 7', fl + fl')~Nc,(t*, x* (t*))}. It follows that

(hi - h2 -p3(t* ) +p4(t~' ), -pl(t* ) +p2(t* )) ~Nc~(t*, x* (t*)). Thus, we obtain the transversality condition on the set C1 at the optimal switch point as required. [] We note that this condition yields further information if we do not incorporate a constraint set C, in our problem formulation. Then, (t*, x* (t*)) e ~ x R n, and by the theory of normal cones,

h~ - h2-p3(t* ) +p,(t*l ) = 0 and -px(t*) +p2(t* ) = 0. Thus,

pl(t?) =p2(t*); hence, the costates corresponding to the state trajectories Xl(" ) and x2(') are continuous at the switch point, as expected. The condition

h2- hi = -p3(t* ) +p4(t* ) specifies the noncontinuity of the Hamiltonians at the switch point due to the explicit tl dependence of the functions and corresponds to the result obtained via the classical maximum principle; see Ref. 14. The terms hi, h2 correspond to the optimal Hamiltonian values at the optimal switch point, and p3(t* ), p4(t* ) can be obtained by solving the costate equations together with the boundary conditions for P3(" ) and p4(" ). This analysis shows that the transversality conditions derived classically for the two-stage problem can be recovered, without imposing such severe conditions on the functions involved, via the application of the multiprocess maximum principle.

8. Conclusions

We have extended necessary conditions of optimality for multistage optimal control problems to include the infinite horizon using mild and

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

551

verifiable hypotheses. This was achieved by combining both known necessary conditions for the finite-horizon case and infinite-horizon techniques, which involve obtaining the infinite-horizon costate function as a limit of costate functions for the related finite-horizon problems. The implications of these conditions, considered for a problem derived from the resource allocation literature, are that they permit the solution of multistage problems under less stringent hypotheses on the data than by classical methods.

References 1. PONTRYAGIN, L. S., BOLTYANSKII, V. G., GAMKRELIDZE, R. V., and MISHCHENKO, E. F., The Mathematical Theory of Optimal Processes, English Translation Edited by L. W. Neustadt, Wiley-Interscience, New York, New York, 1962. 2. HALKIN, n., Necessary Conditionsfor Optimal Control Problems with Infinite Horizons, Econometrica, Vol. 42, pp. 267-272, 1974. 3. CARLSON,D. A., and HAURIE,A., Infinite-Horizon Optimal Control: Theory and Applications, Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin, Germany, Vol. 270, 1987. 4. STERN~L. E., Criteria of Optimality in the Infinite-Time Optimal Control Problem, Journal of Optimization Theory and Applications, Vol. 44, pp. 497-508, 1984. 5. WEITZMAN,M. L., Duality Theoryfor Infinite-Horizon Convex Models, Management Science, Vol. 19, pp. 783-789, 1973. 6. AUBIN, J. P., and CLARKE, F. n., Shadow Prices and Duality for a Class of Optimal Control Problems, SIAM Journal on Control and Optimization, Vol. 17, pp. 567-586, 1979. 7. GRAY, J. A., and SALANT, S. W., Transversality Conditions in Infinite-Horizon Models, International Finance Discussion Paper No. 172, Board of Governors of U.S. Federal Reserve, 1981. 8. BENVENISTE, L. M., and SCHEINKMAN, J. A., Duality Theory for Dynamic Optimization Models of Economics: The Continuous-Time Case, Journal of Economic Theory, Vol. 27, pp. 1-19, 1982. 9. MICHEL, P., On the Transversality Condition in Infinite-Horizon Optimal Problems, Econometrica, Vol. 50, pp. 975-985, 1982. 10. ARAUJO, A., and SCHEINKMAN,J. A., Maximum Principle and Transversality Condition for Concaoe Infinite-Horizon Economic Models, Journal of Economic Theory, Vol. 30, pp. 1-16, 1983. 11. MICHEL, P., Some Clarifications on the Transoersality Condition, Econometrica, Vol. 58, pp. 705-723, 1990. 12. CLARKE, F. H., and MINTER, R. B., Applications of Optimal Multiprocesses, SIAM Journal on Control and Optimization, Vol. 27, pp. 1048-1071, 1989. 13. CLARKE, F. H., and MINTER, R. B., Optimal Multiprocesses, SIAM Journal on Control and Optimization, Vol, 27, pp. 1072-1091, 1989.

552

JOTA: VOL. 86, NO. 3, SEPTEMBER 1995

14. TOMIYAMA,K., and ROSSANA,R. J., Two-Stage Optimal Control Problems with an Explicit Switch-Point Dependence: Optimality Criteria and an Example of Delivery Lags and Investment, Journal of Economic Dynamics and Control, Vol. 13, pp. 319-337, 1989. 15. MACCINI, L. J., Delivery Lags and the Demand for Investment, Review of Economic Studies, Vol. 40, pp. 269-281, 1973. 16. HOEL, M., Resource Extraction When a Future Substitute Has an Uncertain Cost, Review of Economic Studies, Vol. 45, pp. 637-644, 1978. 17. DASGUPTA,P., GILBERT,R. J., and STIGLITZ,J. E., Invention and Innovation under Alternative Market Structures: The Case of Natural Resources, Review of Economic Studies, Vol. 49, pp. 567-582, 1982. 18. ROSSANA,R. J., Delivery Lags and Buffer Stocks in the Theory of Investment by the Firm, Journal of Economic Dynamics and Control, Vol. 9, pp. 153-193, 1985. 19. CLARKE,F. H., Optimization and Nonsmooth Analysis, Wiley-Interscience, New York, New York, 1983. 20. BELLMAN,R., Dynamic Programming, Princeton University Press, Princeton, New Jersey, 1957. 21. BABAD, H. R., Optimality Conditions and Sensitivity Relations in Dynamic Optimization, PhD Thesis, Imperial College of Science, Technology, and Medicine, London University, London, England, 1991. 22. FLEMING, W. H., and RISHEL, R. W., Deterministic and Stochastic Optimal Control, Springer Verlag, Berlin, Germany, 1975. 23. ROYDEN,H. L., Real Analysis, Collier-Macmillan, New York, New York, 1988. 24. LOEWEN,P. D., CLARKE,F. H., and VINTER, R. B., Differential Inclusions with Free Time, Annales de l'Institut Henri Poincar6, Vol. 5, pp. 573-593, 1988.