Biosight: Quantitative Methods for Policy Analysis : Dynamic Models

Published on: **Mar 3, 2016**

Published in:
Education

- 1. Day 3: Dynamic Models Day 3 NotesHowitt and Msangi 1
- 2. Understand Bellman’s Principle of Optimality and the basic Dynamic programming problem Have your cake and eat it too – an example Solve the DP using Chebychev Polynomial approximation Apply concepts to Senegal livestock model Evaluate changes in the DP optimal solution Day 3 NotesHowitt and Msangi 2
- 3. Introduction to Dynamic Programming ◦ Solving a simple problem with analytical methods Value Function Iteration ◦ Illustrate with “cake-eating” problem Function Approximation ◦ Chebychev nodes ◦ Chebychev polynomials Collocation example ◦ Solving for polynomial terms with simple example DP Senegal Livestock Model ◦ (S)DP Solution Day 3 NotesHowitt and Msangi 3
- 4. Fundamental Dynamic Program ◦ State variable: x ◦ Control variable: c ◦ Discount factor: β Day 3 NotesHowitt and Msangi 4 1 ( , ) ( , ) t t t t t Max f x c subject to x g x c+ =
- 5. Bellman’s “principle of optimality” ◦ Dynamic problem and equation of motion: ◦ Infinite horizon: ◦ Where, β is the discount factor V(.) is the value function, defined as maximum utility for a T-period problem, given initial starting stocks and conditions Day 3 NotesHowitt and Msangi 5 ( ) ( ) ( ){ }1 1( ) max , , t t t t t t t t c V x f c x V x x g x cβ + += + = ( ){ } ( ){ }( ) max max c c V x c V x x x c c V x cα α β β+ + = + = − = + −
- 6. Assumptions ◦ Value functions that are continuous in the controls and state variables. ◦ Value functions that are concave in the controls and state variables. ◦ A decision-maker who optimizes the sum of expected discounted value. Day 3 NotesHowitt and Msangi 6
- 7. Day 3 NotesHowitt and Msangi 7 The Marie-Antoinette problem “Let them eat cake…”
- 8. The cake eating example: CakeEatingDP_Analytical_Day3.gms Using the generic DP previously used, we can derive two key conditions that hold at the optimal solution: 1. “Euler” equation: 2. ‘Benveniste-Scheinkman’ condition: Day 3 NotesHowitt and Msangi 8 ( ) ( ) ( ){ }1 1( ) max , , t t t t t t t t c V x f c x V x x g x cβ + += + = ( ) ( ) ( )( )0 , , ,c t t c t t c t tf c x g x c V g x cβ= + ⋅ ⋅ ( ) ( ) ( )( )( ) , , ,x t x t t x t t x t tV x f c x g x c V g x cβ= + ⋅ ⋅
- 9. Closed-form example of the cake-eating problem, written as: Conversely to show that it is an infinite-horizon problem: Next, calculate marginal rate of substitution between the current and future period: Day 3 NotesHowitt and Msangi 9 ( ) ( ){ }1 1( ) max t t t t t t t c V x u c V x x x cβ + +=+ =− 1 1 1 ( ) ( ) . .t t t t t t U u c s t x x cβ ∞ − + = = = −∑c ( ) ( ), 1 1 ( ) t t t t u c MRS u cβ+ + ′ = ′ c
- 10. Using a simple utility function: , the problem would become: And, after dropping the time sub-script, we obtain: Day 3 NotesHowitt and Msangi 10 ( ) ( )t tu c c α = ( ){ }1 1( ) max ( ) t t t t t t t c V x c V x x x cα β + +=+ =− ( ){ } ( ){ }( ) max max c c V x c V x x x c c V x cα α β β+ + = + = − = + −
- 11. Backward recursion example of the cake-eating problem (“no tomorrow”): We expect carry-over value is zero, so you eat all of the cake in the last period. Using this knowledge, combined with the function to used to determine carry-over value from the previous period, and using the Euler condition (first-order conditions), we define optimal consumption as: Day 3 NotesHowitt and Msangi 11 ( ){ }1 0( ) max c V x c V x cα β= + − 1 1 1 1 1 1 * 1 1 x x c α α α β β β − − − = = + +
- 12. Using the optimal consumption function and substituting back into the Bellman equation and simplifying with algebra, we obtain: By defining , the value function can be written as: Next, solve the Bellman equation problem, then take the first- order conditions (w.r.t. consumption), to acquire the Euler condition, which yields: Day 3 NotesHowitt and Msangi 12 ( )1 1 1 2 ( ) 1V x xα α α β − − =+ ⋅ ( )1 1 1 11 α α β − − + =Θ 2 1( )V x xα =Θ ⋅ ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 1 1 1 1 1 11 1 x x c x c α α α α β β β β − − − − ⋅Θ = ⋅Θ ⋅ − = = + ⋅Θ + ⋅Θ
- 13. Substituting this function back into the Bellman equation, to acquire the maximized value, we acquire: By defining , and using algebra to simplify, the value function can be written as: Day 3 NotesHowitt and Msangi 13 ( ) ( ) ( ) ( ) 1 1 1 1 * * 3 2 1 1 ( ) 1 1 x x V x c V x c x α α α α α β β β β− − = + − = + − + ⋅Θ + ⋅Θ ( )( )1 1 1 1 21 α α β − − + ⋅Θ = Θ 3 2( )V x xα =Θ ⋅
- 14. From the previous results, we see the carry-over value functions have the following ‘equation of motion’: Using this, we can simulate forward, from a starting value to reach convergence. We infer that: Which we can substitute into the equation of motion and solve for the steady-state parameter value: Day 3 NotesHowitt and Msangi 14 ( ) 1 1 1 11s s α α β − − − Θ= + ⋅Θ 1s s−Θ =Θ =Θ 1 1 1 1 α α β − − Θ= −
- 15. Substituting the parameter value into our value function, yields: From this, we can define the infinite-horizon Bellman equation as: Day 3 NotesHowitt and Msangi 15 1 1 1 ( ) 1V x x xα α α α β − − ∞ = Θ⋅ = − ⋅ ( ){ }1 1 1 ( ) max 1 c V x c x cα α αα β β − − = + ⋅ − ⋅ −
- 16. Using backward-recursion, we can obtain the closed- form solution to the infinite-horizon value function: Additionally, we can obtain the function that determines consumption as a function of the current state: Derived directly from closed-form solution of the DP problem Observed habits ◦ Consumption and stock Day 3 NotesHowitt and Msangi 16 1 1 1 ( ) 1V x xα α α β − − ∞ =− ⋅ ( ) ( ) ( ) ( )1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 x x x c x α α α α α α α β ββ β β β − − − − − − − = = = = − + ⋅Θ ++ ⋅ − −
- 17. Solution properties ◦ Solve Bellman equation in GAMS ◦ Use the derived “policy function” to calculate consumption over time Verify first-order conditions hold for: ◦ First-order condition with respect to consumption (Euler equation) ◦ Envelope condition w.r.t. state variable (Benveniste-Scheinkman condition) ◦ All implying the condition below holds over optimal path Day 3 NotesHowitt and Msangi 17 ( ){ }( ) max c V x c x c αα β= + ⋅Θ⋅ − ( ) 11 0 c x c αα α α β −− = − ⋅ ⋅Θ⋅ − ( ) ( ) ( ) ( ) 1 11 1 ( ) ( )x xV x V x x x x x α αα α β α α β β − −− −+ + = ⋅ → ⋅Θ⋅ = ⋅ ⋅Θ⋅ → = ⋅ ( ) 1 1x x αβ+ −= ⋅
- 18. Steps for value function iteration: ◦ Set a convergence tolerance of ◦ Make an initial guess, call it V, for the value function at each possible state. The Contraction Mapping Theorem guarantees convergence for any starting value. ◦ Compute the value function using V, call it TV. ◦ Compute ◦ Check if If true, solution has converged. If false, update V with TV and go to (c). Repeat until convergence. Discretizing the state-space Chebychev polynomial approximation Day 3 NotesHowitt and Msangi 18
- 19. Functional fixed point equation ◦ Domain contains an infinite number of points ◦ Use approximation and interpolation methods: Select a degree for the basis functions, n Require n conditions (equations), by selecting a series n of interpolation nodes, Require that and are equal Day 3 NotesHowitt and Msangi 19 1 ˆ( ) ( ) n j j j f x c xφ = = ∑ nx f ˆf ( ) ( ) ( ) 1 ˆ n i j j i i j f x c x f xφ = = =∑
- 20. Chebychev Nodes ◦ Nodes: ◦ Chebychev nodes are nearly optimal – in that they span the state space in the most efficient way Day 3 NotesHowitt and Msangi 20 0.5 cos , 1,2,..., 2 2 i a b b a n i x i n n π + − − + = + ∀=
- 21. Chebychev Polynomials ◦ Select our basis functions using Chebychev Polynomials Order i is defined over [-1,1], where we can map [a,b] to [-1,1] by: Polynomial has the recursive formulation: Day 3 NotesHowitt and Msangi 21 ( ) ( ) 2 1 x a z b a − = − − 1 2( ) 2 ( ) ( )j j iT z zT z T z− −= −
- 22. Evaluate a Chebychev polynomial of order i by: ◦ Evaluate the first 2 order polynomials ◦ For order i>1 we use these values and the recursive formula ◦ Evaluate the resulting polynomial Polynomial interpolation matrix has typical element: Day 3 NotesHowitt and Msangi 22 ( )( )0.5 1 cosij n i j n π φ − + − =
- 23. Figure 1. Graph of the Chebychev Polynomial Terms over its Domain -1.5 -1 -0.5 0 0.5 1 1.5 -1.5 -1 -0.5 0 0.5 1 1.5 x Phi(x) phi1 phi2 phi3 phi4 phi5 Day 3 Notes 23Howitt and Msangi
- 24. Generalize approximation methods and how they solve a function equation (specifically, the Bellman equation) Find a function that satisfies a known function g, the relationship: Approximate using a linear combination of n basis function: Day 3 NotesHowitt and Msangi 24 :[ , ]f a b ( ), ( ) 0 [ , ]g x f x for x a b= ∈ f ( ) ( ) 1 ˆ n i j j i j f x c xφ = = ∑
- 25. Replaced an infinite-decision problem with a finite-dimension specification ◦ Will not be able to exactly satisfy approximated function, so we will specify a convergence criteria ◦ Applying Chebychev nodes to the Bellman equation to approximate the value function: where is the coefficient for the ith polynomial term and is defined over the [-1,1] interval given by the mapping. Day 3 NotesHowitt and Msangi 25 ( )( ) ( )i i i V x c M xφ= ∑ ( )( )i M xφ ic
- 26. “Chubby-chev” – eating cake example: CakeEatingDP_ChebyApprox_Day3.gms General problem: rewritten as: Instead of backward recursion, we might choose to use the collocation method for a numerical solution “Value function iteration” ◦ Chebychev polynomial ◦ Bellman equation Day 3 NotesHowitt and Msangi 26 ( ) ( ) ( ){ }1 1( ) max , , t t t t t t t t c V x f c x V x x g x cβ + += + = ( ){ } ( ){ }( ) max max c c V x c V x x x c c V x cα α β β+ + = + = − = + −
- 27. Polynomial approximation: where j refers to the order of the polynomial, and coefficients are defined by to avoid notation conflicts in previous examples Values of each polynomial term are evaluated with respect to the state variable (x) A 3rd order Chebychev polynomial approximation will be written as: Day 3 NotesHowitt and Msangi 27 ( )( )( ) j j j V x a M xφ= ∑ ja ( )jφ ⋅ ( )( ) ( )( ) ( )( ) ( )( )1 1 2 2 3 3 3 ( ) j j j V x a M x a M x a M x a M xφ φ φ = = Φ = + +∑
- 28. We chose 3 points over the domain of the state variable, defined by the interval Solve the Bellman equation for current-period values of the state variable to obtain a sequence of maximized values: Where each solution yields a single scalar numerical value. Then, equate the polynomial approximation terms at the computation ‘nodes’ (which we selected, not Chebychev): Day 3 NotesHowitt and Msangi 28 ( )1 2 3, ,x x x ,low up x x ( ){ } ( ){ } ( ){ } 1 1 1 2 2 2 3 3 3 ( ) max ( ) max ( ) max c c c V x c V x c v V x c V x c v V x c V x c v α α α β β β = + − = = + − = = + − = ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) 1 1 1 2 2 1 3 3 1 1 1 1 2 2 2 2 3 3 2 2 1 1 3 2 2 3 3 3 3 3 a M x a M x a M x v a M x a M x a M x v a M x a M x a M x v φ φ φ φ φ φ φ φ φ + + = + + = + + =
- 29. Recognizing the results as a linear system, we can define as: Simplifying to: or Approximate an implicit function by choosing a proper set of basis functions ◦ Solve for the vector of polynomial coefficients by solving the inverse problem Day 3 NotesHowitt and Msangi 29 ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) ( )( ) 1 1 2 1 3 1 1 1 1 2 2 2 3 2 2 2 3 31 3 2 3 3 3 M x M x M x a v M x M x M x a v a vM x M x M x φ φ φ φ φ φ φ φ φ = 11 21 31 1 1 12 22 32 2 2 13 23 33 3 3 a v a v a v φ φ φ φ φ φ φ φ φ = =a vΦ 1− =a vΦ
- 30. Decision to pump groundwater ◦ Current marginal net revenue ◦ Future net value of groundwater ◦ Pumping costs ◦ Probability of future recharge Expressed as: subject to where dt , Ht and Rt are respectively the annual pumping, the height of groundwater and recharges to the aquifer, and Pi are the probabilities of a given level of recharge in a future year Later – look at the stochastic (SDP) version Day 3 NotesHowitt and Msangi 30 ( ) ( )1 1 1 max , t t t i t t d t i f d P f d Hβ ∞ + + + + ∑ ∑ 1t t t iH H d R+ = − +
- 31. Ferlo region livestock stocking model (Hein, 2009) ◦ Decision variable: long-term stocking density Other assumptions ◦ Livestock sold at time t, ◦ Size of livestock herd in Tropical Livestock Units (TLU), ◦ Livestock feed on fodder , which is produced on the land depending on rain and Rainfall Use Efficiency (RUE) Current profits defined as: Day 3 NotesHowitt and Msangi 31 tSL tTLU tF tr tRUE ( )0 1t t tSL SLπ α α= −
- 32. Ferlo region livestock stocking model (Hein, 2009) ◦ Decision variable: long-term stocking density Other assumptions ◦ Livestock sold at time t, ◦ Size of livestock herd in Tropical Livestock Units (TLU), ◦ Livestock feed on fodder , which is produced on the land depending on rain and Rainfall Use Efficiency (RUE) Current profits defined as: and are the intercept and slope of the livestock market demand function Day 3 NotesHowitt and Msangi 32 tSL tTLU tF tr tRUE ( )0 1t t tSL SLπ α α= − 0α 1α
- 33. RUE indicates the effectiveness to transfer rain to biomass where are scaling parameters R is the average rainfall is the long term stocking density: where H is grazed land area Stocking density represents intensiveness of grazing, but does not account for variation of spatial distribution Day 3 NotesHowitt and Msangi 33 ( ) ( )( )2 2 2 3 42 2t t t t t tRUE r r SR r Rr vα α α µ µ= + − − − + , ,vα µ tSR t t TLU SR H =
- 34. Fodder production is a product of RUE and land area: Land production limit depends on TLU feeding requirements (2,500 kg/ha): TLU changes depend on how many units are sold, plus a growth factor. Growth assumed to follow a logistical function form, with shape parameter : Day 3 NotesHowitt and Msangi 34 t tF RUE H= MAX t t F TLU Ph = λ 1 1 t t t tMAX t TLU TLU TLU SL TLU λ+ =− −
- 35. SDP Solution ◦ Solve using Chebychev polynomial approximation of value function ◦ Define 4 nodes to evaluate the value function approximation State space (TLU) is [300,600] and maps to [-1,1] interval by: Transformation back to [300,600]=[L,U] interval calculated by: ◦ Now define interpolation matrix using the recursive formula Day 3 NotesHowitt and Msangi 35 2 1 ˆ cos , for 1,..., 2 j j x j n n π − = = ( )( )ˆ 2 j j x L U U L x + − = 1, 2, , 1, 2, 1 ˆ ˆ2 3 j j j k j j k j k j x x k φ φ φ φ φ− − = = = − ∀ ≥