Appendix IV APPENDIX IV OPTIMAL CONTROL THEORY This appendix provides a concise review of optimal control theory.Many economic problems require the use of optimal control theory.For example, optimization over time such as maximizations of utility over an individual's life time and of profit and social welfare of a country over time and optimization over space such as the ones analyzed in this book fit in its framework. Although these problems may be solved by the conventional techniques such as Lagrange's method and nonlinear programming if we formulate the problems in discrete form by dividing time (or distance)into a finite number of intervals,continuous time (or space)models are usually more convenient and yield results which are more transparent.Optimization over continuous time,however,introduces some technical difficulties.In the continuous time model,the number of choice variables is no longer finite:since decisions may be taken at each instant of time,there is a continuously infinite number of choice variables.The rigorous treatment of optimization in an infinite-dimensional space requires the use of very advanced mathematics. Fortunately,once proven,the major results are quite simple,and analogous to those in the optimization in a finite-dimensional space. There are three approaches in the optimal control theory:calculus of variations, the maximum principle and dynamic programming.Calculus of variations is the oldest among the three and treats only the interior solution.In applications,as it turned out, choice variables are often bounded,and may jump from one bound to the other in the interval considered.The maximum principle was developed to include such cases. Roughly speaking,calculus of variations and the maximum principle are derived by using some appropriate forms of differentiation in an infinite-dimensional space. Dynamic programming however,exploits the recursive nature of the problem.Many problems including those treated by calculus of variations and the maximum principle have the property that the optimal policy from any arbitrary time on depends only on the state of the system at that time and does not depend on the paths that the choice variables have taken up to that time.In such cases the maximum value of the objective function beyond time t can be considered as a function of the state of the system at time t.This function is called the value function.The value function yields the value which the best possible performance from t to the end of the interval achieves. The dynamic programming approach solves the optimization problem by first obtaining the value function.Although the maximum principle and dynamic programming yield the same results,where they can both be applied,dynamic programming is less general than the approach based on the maximum principle,since it requires differentiability of the value function. We first try to facilitate an intuitive understanding of control theory in section 1. In order to do so,a very simple control problem is formulated and the necessary conditions for the optimum are derived heuristically.Following the dynamic programming approach,Pontryagin's maximum principle is derived from the partial 189
Appendix IV 189 APPENDIX IV OPTIMAL CONTROL THEORY This appendix provides a concise review of optimal control theory. Many economic problems require the use of optimal control theory. For example, optimization over time such as maximizations of utility over an individual's life time and of profit and social welfare of a country over time and optimization over space such as the ones analyzed in this book fit in its framework. Although these problems may be solved by the conventional techniques such as Lagrange's method and nonlinear programming if we formulate the problems in discrete form by dividing time (or distance) into a finite number of intervals, continuous time (or space) models are usually more convenient and yield results which are more transparent. Optimization over continuous time, however, introduces some technical difficulties. In the continuous time model, the number of choice variables is no longer finite: since decisions may be taken at each instant of time, there is a continuously infinite number of choice variables. The rigorous treatment of optimization in an infinite-dimensional space requires the use of very advanced mathematics. Fortunately, once proven, the major results are quite simple, and analogous to those in the optimization in a finite-dimensional space. There are three approaches in the optimal control theory: calculus of variations, the maximum principle and dynamic programming. Calculus of variations is the oldest among the three and treats only the interior solution. In applications, as it turned out, choice variables are often bounded, and may jump from one bound to the other in the interval considered. The maximum principle was developed to include such cases. Roughly speaking, calculus of variations and the maximum principle are derived by using some appropriate forms of differentiation in an infinite-dimensional space. Dynamic programming however, exploits the recursive nature of the problem. Many problems including those treated by calculus of variations and the maximum principle have the property that the optimal policy from any arbitrary time on depends only on the state of the system at that time and does not depend on the paths that the choice variables have taken up to that time. In such cases the maximum value of the objective function beyond time t can be considered as a function of the state of the system at time t. This function is called the value function. The value function yields the value which the best possible performance from t to the end of the interval achieves. The dynamic programming approach solves the optimization problem by first obtaining the value function. Although the maximum principle and dynamic programming yield the same results, where they can both be applied, dynamic programming is less general than the approach based on the maximum principle, since it requires differentiability of the value function. We first try to facilitate an intuitive understanding of control theory in section 1. In order to do so, a very simple control problem is formulated and the necessary conditions for the optimum are derived heuristically. Following the dynamic programming approach, Pontryagin's maximum principle is derived from the partial
differential equation of dynamic programming. As mentioned above, this approach is not the most general one, but it facilitates economic interpretation of the necessary conditions. In section 2 the results in section I are applied to an example taken from Chapter VIl. Section 3 considers a more general form of the control problem(due to Bolza and Hestenes) and Hestenes' theorem, giving the necessary conditions for the optimum, is stated without proof. This theorem is general enough to include most problems that appear in this book. Finally, in section 4, Hestenes' theorem is used to solve the control problems in Chapter I 1. A Simple Control Problem Consider a dynamic process which starts at inital time to and ends at terminal time t,. Both to and 4, are taken as given in this section. For simplicity, the state of the system is described by only one variable, x(, called the state variable In most economic problems the state variable is usually a stock, such as the amounts of capital equipments and inventories available at time t. In Chapters IV and V of our book the volume of traffic at a radius is a state variable The state of the system is influenced by the choice of control variables, u(0, u2(0),.,u,(0), which are summarized as the control vector, l()=(1(t),u2(D)2…,ly(t) (11) The control vector must lie inside a given subset of a Euclidean r-dimensional space, U: to≤t≤1 (12) where U is assumed to be closed and unchanging. Note that control variables are chosen at each point of time. The rate of investment in capital equipment is one of the control variables in most models of capital accumulation; the rate of inventory investment is a variable in inventory adjustment models; and the population per unit distance is a control variable for the models in this book. An entire path of the control vector,u(O),to sIst, is a vector-valued function u(t) from the interval into the r-dimensional space and is simply called a control. A control is admissible if it satisfies the constraint(1.2)and some other regularity conditions which will be specified in section 3 The state variable moves according to the differential equation dx di=x()=/(x()u(0),0) (13) where f, is assumed to be continuously differentiable. Notice that the function fr is not the same as fo. In this section the initial state, x('o), is given, 190
Appendix IV 190 differential equation of dynamic programming. As mentioned above, this approach is not the most general one, but it facilitates economic interpretation of the necessary conditions. In section 2 the results in section 1 are applied to an example taken from Chapter VII. Section 3 considers a more general form of the control problem (due to Bolza and Hestenes) and Hestenes' theorem, giving the necessary conditions for the optimum, is stated without proof. This theorem is general enough to include most problems that appear in this book. Finally, in section 4, Hestenes' theorem is used to solve the control problems in Chapter I. 1. A Simple Control Problem Consider a dynamic process which starts at inital time 0 t and ends at terminal time 1 t . Both 0 t and 1 t are taken as given in this section. For simplicity, the state of the system is described by only one variable, x(t) , called the state variable. In most economic problems the state variable is usually a stock, such as the amounts of capital equipments and inventories available at time t. In Chapters IV and V of our book the volume of traffic at a radius is a state variable. The state of the system is influenced by the choice of control variables, ( ), ( ), , ( ), 1 2 u t u t u t K r which are summarized as the control vector, ( ) ( ( ), ( ), , ( )). 1 2 u t u t u t u t = K r (1.1) The control vector must lie inside a given subset of a Euclidean r-dimensional space, U: ( ) , , 0 1 u t ÎU t £ t £ t (1.2) where U is assumed to be closed and unchanging. Note that control variables are chosen at each point of time. The rate of investment in capital equipment is one of the control variables in most models of capital accumulation; the rate of inventory investment is a variable in inventory adjustment models; and the population per unit distance is a control variable for the models in this book. An entire path of the control vector, u(t) , , 0 1 t £ t £ t is a vector-valued function u(t) from the interval [ ] 0 1 t ,t into the r-dimensional space and is simply called a control. A control is admissible if it satisfies the constraint (1.2) and some other regularity conditions which will be specified in section 3. The state variable moves according to the differential equation ( ) ( ( ), ( ), ), 1 x t f x t u t t dt dx = & = (1.3) where 1 f is assumed to be continuously differentiable. Notice that the function 1 f , is not the same as 0 f . In this section the initial state, ( ) 0 x t , is given, ( ) , 0 0 x t = x (1.4)
where x is some constant, but the terminal state, x(t,), is unrestricted. For example, the capital stock at initial time is fixed the rate of change of the capital stock equals the rate of investment minus depreciation; and the capital stock at terminal time is not restricted The problem to be solved is that of maximizing the objective functional J=6(x(n),u(t),)d+S0(x(1)1) with to the control vecto nstraints(1. 2), (1.3),and(1. 4), where fo and So, the functions which make up the objective functional are continuously differentiable. A functional is defined as a function of a function or functions. that apping from a space of functions to a space of numbers. In the investment decision problem for a firm, for example, fo(x(O), u(t),ndt is the amount of profit earned in the time interval t, t+dt and So(x(tu), 41) is the scrap value of the amount of capital x(t,)at terminal time t, fIxIt, tt)m).E Fiqure la, A Trajectory of the Stata variable objective Functional fixt),u(4h, t) t+A time Figure 1b. -he Dbjective Functional
Appendix IV 191 where 0 x is some constant, but the terminal state, ( )1 x t , is unrestricted. For example, the capital stock at initial time is fixed; the rate of change of the capital stock equals the rate of investment minus depreciation; and the capital stock at terminal time is not restricted. The problem to be solved is that of maximizing the objective functional ò = + 1 0 ( ( ), ( ), ) ( ( ), ) 0 0 1 1 t t J f x t u t t dt S x t t (1.5) with respect to the control vector, u(t) , , 0 1 t £ t £ t subject to the constraints (1.2), (1.3), and (1.4), where 0 f and S0 , the functions which make up the objective functional are continuously differentiable. A functional is defined as a function of a function or functions, that is, a mapping from a space of functions to a space of numbers. In the investment decision problem for a firm, for example, f (x(t),u(t),t)dt 0 is the amount of profit earned in the time interval [t,t + dt] and ( ( ), ) 0 1 1 S x t t is the scrap value of the amount of capital ( )1 x t at terminal time 1 t
The problem is illustrated in Figure 1. In Fig. la, a possible trajectory of the state variable with the initial value x is depicted. If the trajectory of the control vector is specified for the entire time horizon [o, t,I, the trajectory of the state variable is completely characterized. The value of the state variable at time t and the choice of the control vector then jointly determine fo(x(o),u(o),t) In Fig. lb we graph the part of the value of the objective functional which has been realized at any time t for the particular trajectory of the control vector fo therefore, appears as the slope in Fig 1b, while the value of the objective functional the sum of the integral from fo to t,, of fo, and So, the scrap value at terminal time Our problem is to obtain the trajectory of the control vector that maximizes the The major difficulty of this problem lies in the fact that an entire time path of the control vector must be chosen. This amounts to a continuously infinite number of control variables. In other words, what must be found is not just the optimal numbers but the optimal functions. The basic idea of control theory is to transform the problem hal uing the entire optimal path of control variables into the problem of find ing the optimal values of control variables at each instant of time. In this way the problem of choosing an infinite number of variables is decomposed into an infinite number of mor elementary problems each of which involves determining a finite number of variables The objective functional can be broken into three pieces for any time t-a past, a t and a futu f0(x(),u(n),)dn ∫f6(x0):()d f0(x(0),u(),)dr+S0(x(1),1) The decisions taken at any time have two effects. They directly affect the present erm fo(x(t), u(t), !)dt by changing fo. They also change x, and hence the future path of x(o), through i=f(x(o), u(t),t). The new path of x(o) changes the future part of the functional For example, if a firm increases investment at time t, the rate at which profits are earned at that time falls because the firm must pay for the investment. The investment however, increases the amount of capital available in the future and therefore profits earned in the future. The firm must make investment decisions weighing these two effects. In general, the choice of the control variables at any instant of time must take into account both the instantaneous effect on the current earnings foAt and the indirect effect on the future earnings [ fodr'+So through a change in the state 192
Appendix IV 192 The problem is illustrated in Figure 1. In Fig.la, a possible trajectory of the state variable with the initial value 0 x is depicted. If the trajectory of the control vector is specified for the entire time horizon [ ] 0 1 t ,t , the trajectory of the state variable is completely characterized. The value of the state variable at time t and the choice of the control vector then jointly determine ( ( ), ( ), ) 0 f x t u t t . In Fig.1b we graph the part of the value of the objective functional which has been realized at any time t for the particular trajectory of the control vector 0 f , therefore, appears as the slope in Fig.1b, while the value of the objective functional is the sum of the integral from 0 t to 1 t , of 0 f , and S0 , the scrap value at terminal time. Our problem is to obtain the trajectory of the control vector that maximizes the objective functional. The major difficulty of this problem lies in the fact that an entire time path of the control vector must be chosen. This amounts to a continuously infinite number of control variables. In other words, what must be found is not just the optimal numbers but the optimal functions. The basic idea of control theory is to transform the problem of choosing the entire optimal path of control variables into the problem of finding the optimal values of control variables at each instant of time. In this way the problem of choosing an infinite number of variables is decomposed into an infinite number of more elementary problems each of which involves determining a finite number of variables. The objective functional can be broken into three pieces for any time t - a past, a present and a future - : ò ò ò +D +D + ¢ ¢ ¢ ¢+ + ¢ ¢ ¢ ¢ = ¢ ¢ ¢ ¢ 1 0 ( ( ) , ( ) , ) ( ( ), ). ( ( ) , ( ) , ) ( ( ) , ( ) , ) 0 0 1 1 0 0 t t t t t t t t f x t u t t dt S x t t f x t u t t dt J f x t u t t dt The decisions taken at any time have two effects. They directly affect the present term, ò +D ¢ ¢ ¢ ¢ t t t f (x(t) ,u(t) ,t )dt 0 , by changing 0 f . They also change x& , and hence the future path of x(t) , through ( ( ), ( ), ) 1 x& = f x t u t t . The new path of x(t) changes the future part of the functional. For example, if a firm increases investment at time t, the rate at which profits are earned at that time falls because the firm must pay for the investment. The investment, however, increases the amount of capital available in the future and therefore profits earned in the future. The firm must make investment decisions weighing these two effects. In general, the choice of the control variables at any instant of time must take into account both the instantaneous effect on the current earnings f Dt 0 and the indirect effect on the future earnings ò +D ¢+ 1 0 0 t t t f dt S through a change in the state
variable. The transformation of the problem is accomplished if a simple way to represent these two effects is found This leads us to the concept of the value function, which might be used by a planner who wanted to recalculate the optimal policy at time t after the dynamic process began. Consider the problem of maximizing f(x(),u(t),)'+S0(x(1),41) when the state variable at time t is x; x(o=x. The maximized value is then a function ofx and t (1.7) which is called the value function. The optimal value of the objective functional for the original problem(1. 2)-(1.5)is J*(x=(D),1)=J*(x),0) (1.8) The usefulness of the value function must be obvious by now: it facilitates the characterization of the indirect effect through a cha the state variable by summarizing the maximum possible value of the objective functional from time t on as a function of the state variable at time t(and n) The next step in the derivation of the necessary conditions for the optimum involves the celebrated Principle of Optimality due to Bellman. The principle exploits the fact that the value of the state variable at time t captures all the necessary information for the decision making from time t on: the paths of the control vector and the state variable up to time t do not make any difference as long as the state variable at time t is the same. This implies that if a planner recalculates the optimal policy at time I given the optimal value of the state variable at that time, the new optimal policy coincides with the original optimal policy. Thus if u*(0),to stsII, is the optimal control for the ariginal problem and x*(O),to stsI, the corresponding trajectory of the state variable. the value function satisfies J*=[6(x*().n*(1),1)d+Sox*(1),) (1.9) Applying the principle of optimality again, we can rewrite(1.9)as J*(x+(0=g1(x*(0)+(O,)d+、6(xm)nnd S0(x*(1)41) (1.10) f(x*(),u*(1),1)d’+J*(x*(t+M),t+△D) for any t and t+ A such that to≤t≤t+At≤l1. This construction allows us to
Appendix IV 193 variable. The transformation of the problem is accomplished if a simple way to represent these two effects is found. This leads us to the concept of the value function, which might be used by a planner who wanted to recalculate the optimal policy at time t after the dynamic process began. Consider the problem of maximizing ò ¢ ¢ ¢ ¢ + 1 ( ( ), ( ), ) ( ( ), ) 0 0 1 1 t t f x t u t t dt S x t t (1.6) when the state variable at time t is x ; x(t) = x . The maximized value is then a function of x and t: J * (x,t), (1.7) which is called the value function. The optimal value of the objective functional for the original problem (1.2)-(1.5) is *( *( ), ) *( , ). 0 0 J x t t = J x t (1.8) The usefulness of the value function must be obvious by now: it facilitates the characterization of the indirect effect through a change in the state variable by summarizing the maximum possible value of the objective functional from time t on as a function of the state variable at time t (and t). The next step in the derivation of the necessary conditions for the optimum involves the celebrated Principle of Optimality due to Bellman. The principle exploits the fact that the value of the state variable at time t captures all the necessary information for the decision making from time t on: the paths of the control vector and the state variable up to time t do not make any difference as long as the state variable at time t is the same. This implies that if a planner recalculates the optimal policy at time t given the optimal value of the state variable at that time, the new optimal policy coincides with the original optimal policy. Thus if *( ), , 0 1 u t t £ t £ t is the optimal control for the original problem and *( ), , 0 1 x t t £ t £ t the corresponding trajectory of the state variable, the value function satisfies * ( *( ), *( ), ) ( * ( ), ). 1 ò 0 + 0 1 1 = ¢ ¢ ¢ ¢ t t J f x t u t t dt S x t t (1.9) Applying the principle of optimality again, we can rewrite (1.9) as ( *( ), *( ), ) *( *( ), ), ( *( ), ) *( *( ), ) ( *( ), *( ), ) ( *( ), *( ), ) 0 0 1 1 0 0 1 f x t u t t dt J x t t t t S x t t J x t t f x t u t t dt f x t u t t dt t t t t t t t t t = ¢ ¢ ¢ ¢+ + D + D + = ¢ ¢ ¢ ¢+ ¢ ¢ ¢ ¢ ò ò ò +D +D +D (1.10) for any t and t + Dt such that 0 1 t £ t £ t +Dt £t . This construction allows us to
concentrate on the decisions in the short interval from t to t+ A by summarizing the outcome in the remaining period in the value func tion, J *(*(t+Ar),+An) By the definition of the value function, any admissible control cannot do better than the value function if the initial state is the same. Consider the following special type of control, u(!),tst'sty: the control is arbitrary between time t and time t+A and optimal in the remaining period given the state reached at time t+At. Then the corresponding value of the objective functional satisfies 1+A J*(x*()1)2,6(x('),(),t)d+J*(x(t+△),t+△) (1.11) where x(o,), tst'st, is the state variable corresponding to the control u(t) with the initial state x(=x*(o Combining(1.10)and(1. 11)yields t+△t *(x*(),0)=0(x*(1),*(t),1)d+J*(x*(t+△,t+△1) ≥f0(x(,u(t),tdr+J*(x(+△,t+△) for any u()∈U,t≤!≤t+△ This shows that the optimal control in the interval [, /+Ad] maximizes the sum of the objective functional in the interval and the maximum possible value of the functional in od [+Ar, 1. If both sides of the inequality are differentiabl Taylor's expansion around t yields I The details of Taylors expansion here are as follows. Taylor's theorem states that if F(is F()=F(a)+(1-a)F(a)+o(t-a) satisfies F0(1)=f6(D) =f0(x+(D),a(1),D)t+J*(x*(n),D) +[(a*(x*(1)D)/ox)*0)+aJ*(x·(m),D)/O4+o(M)
Appendix IV 194 concentrate on the decisions in the short interval from t to t + Dt by summarizing the outcome in the remaining period in the value func tion, J * (x * (t + Dt),t + Dt) . By the definition of the value function, any admissible control cannot do better than the value function if the initial state is the same. Consider the following special type of control, 1 u(t¢), t £ t¢ £ t : the control is arbitrary between time t and time t + Dt and optimal in the remaining period given the state reached at time t + Dt . Then the corresponding value of the objective functional satisfies * ( * ( ), ) ( ( ), ( ), ) * ( ( ), ) 0 J x t t f x t u t t dt J x t t t t t t t > ¢ ¢ ¢ ¢ + + D + D ò + D (1.11) where x(t¢) , 1 t £ t¢ £ t , is the state variable corresponding to the control u(t¢) with the initial state x(t) = x * (t) . Combining (1.10) and (1.11) yields ( ( ), ( ), ) ( ( ), ) ( ( ), ) ( ( ), ( ), ) ( ( ), ) 0 0 f x t u t t dt J x t t t t J x t t f x t u t t dt J x t t t t t t t t t t ³ ¢ ¢ ¢ ¢ + * + D + D * * = * ¢ * ¢ ¢ ¢ + * * + D + D ò ò + D + D for any u(t¢)ÎU ,t £ t¢£ t + Dt . (1.12) This shows that the optimal control in the interval [t,t + Dt] maximizes the sum of the objective functional in the interval and the maximum possible value of the functional in the rest of the period [ ]1 t + Dt,t . If both sides of the inequality are differentiable, Taylor's expansion around t yields1 1 The details of Taylor's expansion here are as follows. Taylor's theorem states that if F (t) is differentiable at t = a , then F(t) = F (a) + (t - a)F(a) + o(t - a) , where 0 ( ) lim 0 = - - - ® t a o t a t a ．Noting that ò +D + D º ¢ ¢ t t t F (t t) f (t )dt 0 0 satisfies ( ) ( ), 0 0 F t = f t ¢ we obtain [( *( *( ), ) ) *( ) *( *( ), ) ] ( ), ( * ( ), *( ), ) *( *( ), ) ( * ( ), * ( '), ') ' * ( *( ), ) 0 0 J x t t x x t J x t t t t o t f x t u t t t J x t t f x t u t t dt J x t t t t t t t + ¶ ¶ +¶ ¶ D + D = D + ¢ + + D + D ò +D & and
-(OJ*(x*(1),)/)△t =f0(x*(D),u*(,D)△+(aJ*(x*(t),D)/ox)f1(x*(D),Lu*(D),D)△t+ ≥f0(x*(D),(0,0)At+(aJ*(x*(D,1)ax)f(x*(D,u(D),D)M+… for any u()∈U, where. represents higher order terms which become negligible as At tends to zero since they approach zero faster than At. Note that we used x(o=x*(o x(t)=f1(x(D),u(1),D)andx*(t)=f1(x*(1),ut*(,1) Inequality(1. 13) has a natural economic interpretation. For example, if a firm is contemplating the optimal capital accumulation policy, fo(x*(O),u(O),t)4,is approximately the amount of profits earned in the period L, t+Az a*(x*(0, 1)/ax is the marginal value of capital, or the contribution of an additional unit of capital at time t; and fI(x*(0),u(0), t)At=x()At is approximately the amount of capital accumulated in period t, t+Ar]. Thus (a*/ax)Ar rep of capital accumulated during the period. (1. 13), therefore, shows that the optimal control vector maximizes the sum of the current profits and the value of increased Dividing(1. 13)by At and taking limits as At approaches zero, we obtain a*(x*(0),0)/at =f0(x*+(D),u*(D,0)+(aJ*(x*(D),1)/Ox)f1(x*(),u*(m),1) ≥后(x*(1),u(D),D)+(aJ*(x*(m),1)/ax)f(x*(D),u(D,D) (1)∈U Thus the optimal control vector u*(1 maximizes f(x*(1),u,1)+(aJ*(x*()1)/ax)f1(x*(m),u,D) (1.15) at each instant of time, and we have finally transformed the problem of finding the optimal path to that of finding optimal numbers at each point in time. From the above discussion, it must be clear that(1. 15)summarizes both the instantaneous effect and the indirect effect through a change in the state variable (1. 14) can be rewritten as fo(x(r,u(r),rdr+J*(x(+△),t+△) =f0(x(),a(D),1)△t+J*(x()n) +[(aJ*(x(),n)/ax)(t)+aJ*(x(n),1)/oM+o(△) fo(x*(),(D),D)M+J*(x*(D),D) (aJ*(x*(),)/ax)x(n)+a/*(x*(m),)/an]M+o△) where we used x(n)=x*(O). Substituting these two equations into(1. 12)yields(1. 13) 195
Appendix IV 195 ( *( ), ( ), ) ( *( *( ), )/ ) ( *( ), ( ), ) , ( *( ), *( ), ) ( *( *( ), )/ ) ( *( ), *( ), ) ( *( *( ), )/ ) 0 1 0 1 K K ³ D + ¶ ¶ D + = D + ¶ ¶ D + - ¶ ¶ D f x t u t t t J x t t x f x t u t t t f x t u t t t J x t t x f x t u t t t J x t t t t for any u(t) Î U , (1.13) where ... represents higher order terms which become negligible as Dt tends to zero, since they approach zero faster than Dt . Note that we used x(t) = x * (t) , ( ) ( ( ), ( ), ) 1 x& t = f x t u t t and *( ) ( *( ), *( ), ). 1 x& t = f x t u t t Inequality (1.13) has a natural economic interpretation. For example, if a firm is contemplating the optimal capital accumulation policy, f (x*(t),u(t),t)Dt 0 , is approximately the amount of profits earned in the period [t,t + Dt] . ¶J * (x * (t),t) / ¶x is the marginal value of capital, or the contribution of an additional unit of capital at time t; and f (x*(t),u(t),t)Dt = x(t)Dt 1 & is approximately the amount of capital accumulated in period [t,t + Dt]. Thus ¶J ¶x f Dt 1 ( */ ) represents the value of capital accumulated during the period. (1.13), therefore, shows that the optimal control vector maximizes the sum of the current profits and the value of increased capital. Dividing (1.13) by At and taking limits as At approaches zero, we obtain ( *( ), ( ), ) ( *( *( ), )/ ) ( *( ), ( ), ) ( *( ), *( ), ) ( *( *( ), )/ ) ( *( ), *( ), ) *( *( ), )/ 0 1 0 1 f x t u t t J x t t x f x t u t t f x t u t t J x t t x f x t u t t J x t t t ³ + ¶ ¶ = + ¶ ¶ - ¶ ¶ for any u(t)ÎU . (1.14) Thus the optimal control vector u * (t) maximizes ( *( ), , ) ( *( *( ), )/ ) ( *( ), , ) 0 1 f x t u t + ¶J x t t ¶x f x t u t (1.15) at each instant of time, and we have finally transformed the problem of finding the optimal path to that of finding optimal numbers at each point in time. From the above discussion, it must be clear that (1.15) summarizes both the instantaneous effect and the indirect effect through a change in the state variable. (1.14) can be rewritten as [( *( *( ), ) ) ( ) *( * ( ), ) ] ( ), ( * ( ), ( ), ) *( * ( ), ) [( *( ( ), ) ) ( ) * ( ( ), ) ] ( ) ( ( ), ( ), ) *( ( ), ) ( ( '), ( '), ') ' * ( ( ), ) 0 0 0 J x t t x x t J x t t t t o t f x t u t t t J x t t J x t t x x t J x t t t t o t f x t u t t t J x t t f x t u t t dt J x t t t t t t t + ¶ ¶ + ¶ ¶ D + D = D + + ¶ ¶ + ¶ ¶ D + D = D + + + D + D ò +D & & where we used x(t) = x *(t) . Substituting these two equations into (1.12) yields (1.13)
a+/ar=maxecb(x+().)+(aJ+(ax)f(x+(,)] (1.14) This equation holds for any x, not just x*(O, and can be considered a partial differential equation of J*(x, 1). It is called the partial differential equation of dynamic programming or Bellman's equation In the dynamic programming approach, the right side of (1. 14)is maximized with respect to u, yielding the partial differential equation. The partial differential equation is then solved with the boundary conditions. At the initial time to, x(to=x, while at the terminal time t, the value function satisfies J*(x(1),1)=S0(x(1),1) (1.16) for any x( 1). This equation is the terminal boundary condition associated with Bellman's equation. Since(1. 16) holds for any x(tu), we have aJ*(x(1)1)/ax=aS0(x(41)h1)/ax, which is called the transversality condition at time t One of the disadvantages of the dynamic programming approach is that the partial ifferential equation is usually hard to solve. Pontryagin's maximum principle, which can be immediately derived from the partial differential equation of dynamic programming, is often more useful for economic applications. Furthermore, the method of dynamic programming employs the Taylor expansion in(1. 13), which requires that the value function be differentiable. There are many problems for which the value function is not differentiable everywhere. The maximum principle, however can be proven using a different and more general method. In this section we derive the maximum principle from Bellman's equation, and in Section 3 we state a more general version of the maximum principle without proof. o derive Pontryagin's maximum principle, we define the adjoint, or costate, o auxillary, variable, p(1)=0*(x*(t),1)/0x, and rewrite(1. 15 )as the Hamiltonian H[x(),(t)t,p()]=f0(x()u(),1)+p(t)(x(,(D0) (1. 14)now reads: if u*() is the optimal control and x*(O) the associated path of the state variable, then there exists a p(t) such that for any t H[x*(O),u*(),4, p(o]=max(au H[x*(O),u, t, P(o] (120) Since p(t) equals a*/ax, the adjoint variable p(t)is the marginal value of the state variable (if, for eample, x(o is capital, p(t is the marginal value of 196
Appendix IV 196 { } * / max [ ( * ( ), , ) ( * / ) ( *( ), , )]. 0 1 J t f x t u t J x f x t u t u U - ¶ ¶ = + ¶ ¶ e (1.14') This equation holds for any x, not just x * (t) , and can be considered a partial differential equation of J * (x,t) . It is called the partial differential equation of dynamic programming or Bellman's equation. In the dynamic programming approach, the right side of (1.14') is maximized with respect to u, yielding the partial differential equation. The partial differential equation is then solved with the boundary conditions. At the initial time , ( ) , 0 0 0 t x t = x while at the terminal time 1 t , the value function satisfies *( ( ), ) ( ( ), ) 1 1 0 1 1 J x t t = S x t t (1.16) for any ( ) 1 x t . This equation is the terminal boundary condition associated with Bellman's equation. Since (1.16) holds for any ( ) 1 x t , we have *( ( ), ) / ( ( ), )/ , 1 1 0 1 1 ¶J x t t ¶x = ¶S x t t ¶x (1.17) which is called the transversality condition at time 1 t . One of the disadvantages of the dynamic programming approach is that the partial differential equation is usually hard to solve. Pontryagin's maximum principle, which can be immediately derived from the partial differential equation of dynamic programming, is often more useful for economic applications. Furthermore, the method of dynamic programming employs the Taylor expansion in (1.13), which requires that the value function be differentiable. There are many problems for which the value function is not differentiable everywhere. The maximum principle, however, can be proven using a different and more general method. In this section we derive the maximum principle from Bellman's equation, and in Section 3 we state a more general version of the maximum principle without proof. To derive Pontryagin's maximum principle, we define the adjoint, or costate, or auxiliary, variable, p(t) = ¶J * (x * (t),t)/ ¶ x, (1.18) and rewrite (1.15) as the Hamiltonian, [ ( ), ( ), , ( )] ( ( ), ( ), ) ( ) ( ( ), ( ), ). 0 1 H x t u t t p t = f x t u t t + p t f x t u t t (1.19) (1.14') now reads: if u * (t) is the optimal control and x * (t) the associated path of the state variable, then there exists a p(t) such that for any t [ ] { } H x *(t),u * (t),t, p(t) max H [x * (t),u,t, p(t)]. = ueU (1.20) Since p(t) equals ¶J * / ¶x , the adjoint variable p(t) is the marginal value of the state variable (if, for example, x(t) is capital, p(t) is the marginal value of
apital) and has the interpretation of the shadow price of x(o) (1. 14)also contains information about the adjoint variable. We can rewrite (1. 14)as the Hamilton-Jacobi equation -a*/at=h(x', u*, I, a/*/ax) (1.21) If the value function is twice differentiable, the derivative of (1.2 1)with respect to x can aJ*/axat= aH /ax+(OH /ap)a*/ax (122) Differentiating(1. 18 )with respect to however, yields P=(a*ax2)x*+a*/atax (1.23) If we further assume twice continuous differentiability, the second order mixed partial derivatives are equal whatever the order of differentiation: aJ*/axat=0J*/atOx Since from(1. 19)and(1.3)we have x*=(a/p)H(x*,u*,1,p), (124) ve can substitute(1.22)and(1.24)into(1.23)to get p=(O/ax)H(x*,u*,1,p) (125) Equation(1. 25) is often called the adjoint equation and the pair,(1.24)and(1.25),is called the canonical equations of the maximum principle The transversality condition(1. 17) gives the value of the adjoint variable at time h1 P(1)=aS0(x*(1)1)ax (1.26) Finally, the time derivative of the Hamiltonian along the optimal path dh ahahaH aH dt ax at From(1. 24)and(1.25), the sum of the first two terms on the rhs is zero. The third term vanishes because either aH /au=0 for an interior solution or i=o for boundary solution Thus we have H aH (127) except when the control vector has a jump The maximum principle approach solves the ordinary differential equations(1. 24
Appendix IV 197 capital) and has the interpretation of the shadow price of x(t) . (1.14') also contains information about the adjoint variable. We can rewrite (1.14') as the Hamilton-Jacobi equation: - ¶J * / ¶t = H ( x*,u*,t,¶J * / ¶x). (1.21) If the value function is twice differentiable, the derivative of (1.21) with respect to x can be taken: */ / ( / ) */ . 2 2 2 - ¶ J ¶x¶t = ¶H ¶x + ¶H ¶p ¶ J ¶x (1.22) Differentiating (1.18) with respect to t, however, yields ( */ ) * * / . 2 2 2 p& = ¶ J ¶x x& +¶ J ¶t¶x (1.23) If we further assume twice continuous differentiability, the second order mixed partial derivatives are equal whatever the order of differentiation: */ */ . 2 2 ¶ J ¶x¶t = ¶ J ¶t¶x Since from (1.19) and (1.3) we have x&* = (¶ / ¶p)H ( x*,u*,t, p), (1.24) we can substitute (1.22) and (1.24) into (1.23) to get - p& = (¶ /¶x)H (x*,u*,t, p). (1.25) Equation (1.25) is often called the adjoint equation and the pair, (1.24) and (1.25), is called the canonical equations of the maximum principle. The transversality condition (1.17) gives the value of the adjoint variable at time 1 t : ( ) ( *( ), ) / . 1 0 1 1 p t = ¶S x t t ¶x (1.26) Finally, the time derivative of the Hamiltonian along the optimal path is * * . t H u u H p p H x x H dt dH ¶ ¶ + ¶ ¶ + ¶ ¶ + ¶ ¶ = & & & From (1.24) and (1.25), the sum of the first two terms on the RHS is zero. The third term vanishes because either ¶H / ¶u = 0 for an interior solution or u& = 0 for a boundary solution. Thus we have t H dt dH ¶ ¶ = (1.27) except when the control vector has a jump. The maximum principle approach solves the ordinary differential equations (1.24)
and(1.25)with the boundary conditions x( o)=x and (1.26). Since boundary conditions are given at two points, i.e., at initial time t, and terminal time 4, this problem is called a two-point boundary value problem. The pair of ordi differential equations are usually easier to solve than the partial differential equation dynamic programming 2. An Example: Optimal Growth of Cities Consider the problem which was formulated in section 3 of Chapter VIl maximize CU(cO, P()-uldt subject to the differential equation k(1)=f(k(1),P(m))-Mk(1)-c(1) and the initial condition, k(0)=k where control variables are the per capita consumption of resources, c(o, and the population of a city, P(O; the state variable is the capital stock, k(o); 2 is the growth rate of the whole population; and u* is the utility level at the optimal steady The fact that the terminal time is infinite causes some complications. We first solve the finite-horizon problem of maximizing ∫"p(a.P()-n+S(k(4)4) (24) subject to the same constraints The Hamiltonian for this problem is H(k(t),c(t),P(D)2t,q())=U(c(),P(t)-ut*+q(DLf(k(,P(1)-Mk(0)-c(切),(25) where q(t is the adjoint variable associated with the differential equation(2.2) Discussions in the previous section show that q( can be interpreted as the marginal value of capital. According to(1.20), the Hamiltonian must be maximized with respect to the control variables, c() and P(r. Assuming an interior solution, we obtain U2(c(1),P(1)=g( Up(C(o), P()=q(ofp(k(O, P()), 198
Appendix IV 198 and (1.25) with the boundary conditions 0 0 x(t ) = x and (1.26). Since boundary conditions are given at two points, i.e., at initial time 0 t and terminal time 1 t , this problem is called a two-point boundary value problem. The pair of ordinary differential equations are usually easier to solve than the partial differential equation of dynamic programming. 2. An Example: Optimal Growth of Cities Consider the problem which was formulated in section 3 of Chapter VII: maximize [ ] ò ¥ - 0 U (c(t), P(t)) u * dt (2.1) subject to the differential equation, k (t) = f (k(t),P(t)) - lk (t) - c(t), & (2.2) and the initial condition, (0) , 0 k = k (2.3) where control variables are the per capita consumption of resources, c(t) , and the population of a city, P(t) ; the state variable is the capital stock, k (t) ; λ is the growth rate of the whole population; and u* is the utility level at the optimal steady state. The fact that the terminal time is infinite causes some complications. We first solve the finite-horizon problem of maximizing [ ( ( ), ( ) *] ( ( ), ) 0 1 1 0 1 U c t P t u dt S k t t t - + ò (2.4) subject to the same constraints. The Hamiltonian for this problem is H (k (t),c(t),P(t),t, q(t)) = U (c(t),P(t)) - u *+q(t)[ f (k (t), P(t) - lk (t) - c(t)] , (2.5) where q(t) is the adjoint variable associated with the differential equation (2.2). Discussions in the previous section show that q(t) can be interpreted as the marginal value of capital. According to (1.20), the Hamiltonian must be maximized with respect to the control variables, c(t) and P(t) . Assuming an interior solution, we obtain U (c(t), P(t) q(t), c = (2.5) U (c(t), P(t) q(t) f (k (t), P(t)), p = P (2.6)