Day 3: Dynamic Models
Day 3 NotesHowitt and Msangi 1
 Understand Bellman’s Principle of Optimality and
the basic Dynamic programming problem
 Have your cake and eat it too –...
 Introduction to Dynamic Programming
◦ Solving a simple problem with analytical methods
 Value Function Iteration
◦ Illu...
 Fundamental Dynamic Program
◦ State variable: x
◦ Control variable: c
◦ Discount factor: β
Day 3 NotesHowitt and Msangi ...
 Bellman’s “principle of optimality”
◦ Dynamic problem and equation of motion:
◦ Infinite horizon:
◦ Where,
 β is the di...
 Assumptions
◦ Value functions that are continuous in the
controls and state variables.
◦ Value functions that are concav...
Day 3 NotesHowitt and Msangi 7
The Marie-Antoinette problem
“Let them eat cake…”
 The cake eating example:
CakeEatingDP_Analytical_Day3.gms
 Using the generic DP previously used,
we can derive two key ...
 Closed-form example of the cake-eating problem, written
as:
 Conversely to show that it is an infinite-horizon problem:...
 Using a simple utility function: , the problem
would become:
 And, after dropping the time sub-script, we obtain:
Day 3...
 Backward recursion example of the cake-eating problem
(“no tomorrow”):
 We expect carry-over value is zero, so you eat ...
 Using the optimal consumption function and substituting back
into the Bellman equation and simplifying with algebra, we
...
 Substituting this function back into the Bellman equation,
to acquire the maximized value, we acquire:
 By defining , a...
 From the previous results, we see the carry-over value
functions have the following ‘equation of motion’:
 Using this, ...
 Substituting the parameter value into our
value function, yields:
 From this, we can define the infinite-horizon
Bellma...
 Using backward-recursion, we can obtain the closed-
form solution to the infinite-horizon value function:
 Additionally...
 Solution properties
◦ Solve Bellman equation in GAMS
◦ Use the derived “policy function” to calculate consumption over
t...
 Steps for value function iteration:
◦ Set a convergence tolerance of
◦ Make an initial guess, call it V, for the value f...
 Functional fixed point equation
◦ Domain contains an infinite number of points
◦ Use approximation and interpolation met...
 Chebychev Nodes
◦ Nodes:
◦ Chebychev nodes are nearly optimal – in that
they span the state space in the most efficient
...
 Chebychev Polynomials
◦ Select our basis functions using Chebychev
Polynomials
 Order i is defined over [-1,1], where w...
 Evaluate a Chebychev polynomial of order i
by:
◦ Evaluate the first 2 order polynomials
◦ For order i>1 we use these val...
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(...
 Generalize approximation methods and
how they solve a function equation
(specifically, the Bellman equation)
 Find a fu...
 Replaced an infinite-decision problem with a
finite-dimension specification
◦ Will not be able to exactly satisfy approx...
 “Chubby-chev” – eating cake example:
CakeEatingDP_ChebyApprox_Day3.gms
 General problem:
rewritten as:
 Instead of bac...
 Polynomial approximation:
where j refers to the order of the polynomial, and
coefficients are defined by to avoid notati...
 We chose 3 points over the domain of the state
variable, defined by the interval
 Solve the Bellman equation for curren...
 Recognizing the results as a linear system, we can
define as:
 Simplifying to:
or
 Approximate an implicit function by...
 Decision to pump groundwater
◦ Current marginal net revenue
◦ Future net value of groundwater
◦ Pumping costs
◦ Probabil...
 Ferlo region livestock stocking model (Hein,
2009)
◦ Decision variable: long-term stocking density
 Other assumptions
◦...
 Ferlo region livestock stocking model (Hein, 2009)
◦ Decision variable: long-term stocking density
 Other assumptions
◦...
 RUE indicates the effectiveness to transfer rain to
biomass
where are scaling parameters
 R is the average rainfall
 i...
 Fodder production is a product of RUE and land
area:
 Land production limit depends on TLU feeding
requirements (2,500 ...
 SDP Solution
◦ Solve using Chebychev polynomial approximation of value
function
◦ Define 4 nodes to evaluate the value f...
of 35

Biosight: Quantitative Methods for Policy Analysis : Dynamic Models

Biosight: Quantitative Methods for Policy Analysis : Dynamic Models
Published on: Mar 3, 2016
Published in: Education      
Source: www.slideshare.net


Transcripts - Biosight: Quantitative Methods for Policy Analysis : Dynamic Models

  • 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 φ φ φ φ φ− − = = = − ∀ ≥