Dynamics Programming

Lecture 7
Introduction to Dynamic Programming
Econ 602 Spring 2020
Ibn Haldun University
April 27, 2020
Econ 602 Spring 2020 (Ibn Haldun University) Lecture 7 April 27, 2020 1 / 34
Neoclassical Growth Model in Discrete Time Setup of the Model
Model Ingredients
Time is discrete and indexed by t=0,1,2...

In each period there are three goods being traded labor services nt ,
capital services kt and a final good yt .
The final good can either be invested it or consumed ct .
The economy can be described with the following ingredients.
Technology: yt = F (kt , nt )
-Output can be consumed or invested:yt = it + ct
-Investment augments the capital stock which depreciates at a
constant rate δ over time. : kt t + 1 = (1 − δ)kt + it
-HH’s own the capital stock and make the investment decision.
Model Ingredients
Preferences:
-There is a large no. of identical and infinitely lived households.
-We examine the problem of a single representative HH.
-Time separable utility function represents the preferences of each
household.
U ({ct }t∞=0 ) = ∑t∞=0 βt U (ct )
Information No risk, perfect foresight of HHs and firms
Endowment At period 0, the HH is born with some endowment k̄o
of initial capital stock. They are also endowed with one unit of time
that can be devoted to leisure or work.
Social Planner Problem in Sequential Formulation
Consider the problem of a social planner that wants to maximize the

utility of the representative agent subject to the technological
constraints of the economy.
The problem of the planner is
∞
w (ko ) = max ∞ ∑ βt U (ct )
{ct ,kt ,nt }t =0 t =0
(1)
s.t.
F (kt , nt ) = ct + kt +1 − (1 − δ)kt (2)
ct ≥ 0, kt ≥ 0, 0 ≤ nt ≤ 1∀t (3)
ko ≤ k̄o (4)
where β ∈ (0, 1)
Assumptions on preferences and technology

The above utility function satisfies the assumptions we mentioned in
the pure exchange economy case.
Assumptions about the production technology: F is continuously
differentiable, homogenous of degree 1, strictly increasing and strictly
concave.
Further more F(0,n)=F(k,0)=0 for all k, n > 0
F satisfies Inada conditions i.e. limk →0 Fk (k, 1) = ∞,
limk →∞ Fk (k, 1) = 0
From these two assumptions, we can come up with two consequences
-nt = 1 ∀t since HH do not value leisure in their utility
-k0 = k̄0 since the production function is strictly increasing in capital.
To simplify the notation define
f (k ) = F (k, 1) + (1 − δ)k ∀k
The function f gives the total amount of consumption goods available
for consumption or investment
Rewriting Social Planner Problem in Sequential

Formulation
Assuming full depreciation (δ = 1) and substituting

ct = f (kt ) − kt +1 and using the implications of the assumptions we
can rewrite the social planner’s problem as
w (k̄o ) = max{kt +1 ,}t∞=0 ∑t∞=0 βt U (f (kt ) − kt +1 ) (5)

s.t.
0 ≤ kt +1 ≤ f (kt )∀t
ko = k̄o given
The only choice is the planner faces is the choice between letting the
consumer eat today vs. invest in the capital today and eat tomorrow.
How do we solve this infinite-dimensional optimization problem?
Neoclassical Growth Model in Discrete Time Solution of the Model
Solving the Social Planner Problem
There are two possible approaches to solving this problem

-Traditional Euler Equation Approach and Transversality Conditions
-Recursive Methods (Dynamic Programming)
In the first approach, you optimize over an infinite sequence of capital
stocks {kt +1 }t∞=0
Only works in simple examples and under certain conditions.
Recursive methods work for a wide class of models and you optimize
over a finite dimensional choice variable.
The Finite Horizon Case
Let us begin with the finite horizon case where the representative
consumer lives for T < ∞ periods after which he dies for sure.
w T (k̄o ) = max{k T
t +1 } t =0
∑T t
t =0 β U (f (kt ) − kt +1 ) (6)
s.t.
0 ≤ kt +1 ≤ f (kt )∀t (7)
ko = k̄o > 0given (8)
Obviously kT +1 = 0 ,and given the Inada conditions on the utility

function, the constraints on kt +1 will never be binding.
Forming the Lagrangian yields
L = U (f (ko ) − k1 ) + ...βt U (f (kt ) − kt +1 ) + βt +1 U (f (kt +1 ) − kt +2 )

.... + βT U (f (kT ) − kT +1 )
Hence we can find the FOCs as

∂L
= − βt U 0 (f (kt ) − kt +1 ) + βt +1 U (f (kt +1 ) − kt +2 )f 0 (kt +1 ) (9)
∂kt +1
U 0 (f (kt ) − kt +1 ) = βU 0 (f (kt +1 ) − kt +2 ) f 0 (kt +1 ) (10)
| {z } | {z } | {z }
Utility cost of saving 1 Discounted add. utility from one Add. production with 1
more unit of capital more unit of consumption more unit of capital in t+1
This first order condition is called Euler condition.

This equation is a second order difference equation, a system of T
equations and T unknowns.
Starting from the terminal condition kT +1 = 0 we can solve for the
optimal {kt +1 }T
t =0 uniquely.

Let U (c ) = ln (c ) and f (k ) = k α . Then Equation 10 becomes
1 βαktα+−11
=
kt − kt +1
α ktα+1 − kt +2
ktα+1 − kt +2 = βαktα+−11 (ktα − kt +1 ) (11)
with ko = 0andkT +1 = 0
To solve this nonlinear difference equation let’s define a variable
zt = kkt +α 1
t
The variable zt is the fraction of output saved as capital for tomorrow.
Dividing both sides of Equation 11 by ktα+1 , we get
βα(ktα − kt +1 )
1 − zt +1 =
kt +1
αβ
zt +1 = 1 + βα − (12)
zt
Recursively solving this backwards by plugging zT = 0 yields
1 − (αβ)T −t
zt = αβ
1 − (αβ)T −t +1
1 − (αβ)T −t α
kt +1 = αβ k
1 − (αβ)T −t +1 t
1 − (αβ)
ct = kα
1 − (αβ)T −t +1 t
Note that the optimal policies are a function of the time horizon the
social planner faces.
The Infinite Horizon Case

To prepare for the discussion of the infinite case let’s analyze the first
order difference equation in Equation 12 graphically.
Figure: Dynamics of saving rate
On the y axis, we draw zt +1 against zt on the x axis.

Since kt +1 ≥ 0 zt ≥ 0∀t.
As zt approaches 0 from above, zt +1 approaches −∞.
As zt approaches +∞, zt +1 approaches 1 + αβ from below
asymptotically.
The graph intersects the x-axis at z o =
αβ
1+αβ
The difference equation has two steady states where zt +1 = zt = z
z = 1 or z = αβ
Start with zT = 0 on the y axis go to the curve to determine zT −1
mirror it against the 45-degree line to obtain zT −1 on the x-axis.
Repeating this, one obtains the entire sequence {zt }T
t =0 hence the
whole {kt +1 }T
t =0 sequence.
Going with t backwards to zero, the zt ’s approach αβ.
Now let’s turn to the infinite horizon case and try to solve it with
Euler equation approach.
Our problem is to solve
w T (k̄o ) = max{kt +1 }t∞=0 ∑t∞=0 βt U (f (kt ) − kt +1 ) (13)

s.t.
0 ≤ kt +1 ≤ f (kt )∀t (14)
ko = k̄o > 0given (15)
U 0 (f (kt ) − kt +1 ) = βU 0 (f (kt +1 ) − kt +2 )f 0 (kt +1 )

This is again a second order difference equation, but now we only
have an initial condition for ko , but no terminal condition.
The terminal condition is replaced by the transversality condition

stated as
lim βt U 0 (f (kt ) − kt +1 )f 0 (kt ) kt = 0

t →∞ | {z } |{z}
value in discounted Total
utility terms of one capital
more unit of capital stock
The transversality condition states that the value of the capital stock
measured in terms of the discounted utility goes to zero as time goes
to infinity.
It does not mean that the value of the capital stock converges to
zero, but rather the shadow value of the capital stock has to converge
to zero.
Theorem
Let U, β, and f satisfy the assumptions we mentioned previously. Then
allocations {kt +1 }t∞=0 that satisfy the Euler equations and the
transversality condition (TVC) solves the social planner’s problem for a
given ko .
This theorem states that under certain assumptions the Euler

equations and the transversality condition are jointly sufficient for a
solution to the social planner’s problem. (Proof in Stokey, Lucas pg.
98-99)
The Euler condition is at the same time a necessary condition for the
solution.
Is the TVC a necessary condition? i.e. Does every solution to the
planer’s problem have to satisfy the TVC?

There is not a very general result for this problem, however for the log
case Ekelund and Scheinkman (1985) prove that TVC is a necessary
condition.
From now on we assert that TVC is necessary and sufficient for
optimization under the assumptions made on f, U.
Let’s take these theoretical results for granted and proceed with the
example of U (c ) = lnc and f (k ) = k α .
For these particular forms the TVC becomes
limt →∞ βt U 0 (f (kt ) − kt +1 )f 0 (kt )kt
αβt ktα
= limt →∞ ktα −kt +1
αβt
= limt →∞ 1−zt
We also repeat the FOC derived from the Euler equations
αβ
zt +1 = 1 + αβ −
zt
Unlike the finite horizon case, we cannot solve for the Euler equations
backwards as in the finite case.
However we can solve it forwards conditional on an initial value for zo .
We now show that for only a unique value of zo , we can find a
sequence that does not violate the TVC or the nonnegativity
constraint on capital or consumption.
In relation with the Figure above, we consider 3 possible cases for the
value of zo .
1 zo < αβ. From Figure we see that in finite time, zt < 0, violating the
nonnegativity constraint on capital.

2 zo > αβ. From Figure 12, we see that limt →∞ zt = 1. We will argue
that these paths all violate the TVC.
3 zo = αβ Then zt = αβ∀t > 0. This path obviously satisfies the Euler
conditions (verified in the finite horizon case).
For this path, we have that
αβt αβt
limt →∞ = limt →∞ =0
1 − zt 1 − αβ
Hence this equation satisfies the TVC. From the sufficiency of the
Euler equation, jointly with TVC we conclude that the sequence
{zt }t∞=0 , given by zt = αβ is an optimal solution for the social
planner’s problem.
Translating this into capital sequences yields as optimal policy
kt +1 = αβktα , with ko given.
Hence the optimal policy suggests to save a constant fraction of
output for all time periods.

How are the sequences described in case 2 ruled out?
All sequences {zt }t∞=0 from case 2 converge to 1.
In the TVC, both the numerator and denominator approach 0. So the
limit is unidentified.
To find the TVC for this case let’s linearly approximate zt +1 around
the steady state z = 1
This gives
αβ
zt +1 = 1 + αβ = g (zt )
zt
zt +1 ≈ g (1) + (zt − 1)g 0 (zt )|zt =1
αβ
= 1 + (zt − 1)( 2 )|zt =1
zt
= 1 + αβ(zt − 1)
1 − zt +1 ≈ αβ(1 − zt )
1 − zt +1 ≈ (αβ)t −k +1 (1 − zk )
Hence
αβt +1 αβt +1
limt →∞ ≈ limt →∞
1 − zt + 1 (αβ)t −k +1 (1 − zk )
βk
= limt →∞ =∞
(α)t −k (1 − zk )
as long as 0 < α < 1.
Hence non of the sequences contemplated in 2, can be an optimal

solution.
The solution found in 3 is indeed the unique optimal solution to the
infinite-dimensional social planner’s problem.
For this specific case, the Euler equation together with the TVC
works.
But this is very unique to the specific example at hand.
For the general case, we cannot rely on pencil and paper but we have
to resort to computational techniques.
Dynamic Programming
Recall that the social planner’s problem expressed in Equation 5 was
an infinite -dimensional optimization problem.
The idea of dynamic programming is to find a simpler maximization
problem and demonstrate that the solution to the simpler
maximization problem solves the original maximization problem.
The problem in fact can be written as
w (ko ) = max U (f (ko ) − k1 ) + βw (k1 )
{0≤k1 ≤f (ko ),ko given}
Following questions arise:

1 Under which conditions is this suggestive discussion formally correct?
There is a lot of theory behind this.
2 Is this progress? This is a much easier problem since instead of
maximizing over an infinite sequence, we maximize over just one
number k1 ?
3 How are we going to solve this problem as there is a function on both
sides?
Recursive Formulation of Social Planner’s Problem
The above formulation of the social planner’s problem with a function

on the right and left hand sides of the maximization problem is called
recursive formulation.
Now we want to study this recursive formulation. Let us denote the
function of the recursive formulation of the problem as v (.)
The interpretation of v (k ): The discounted lifetime utility of the
representative agent from the current period onwards, if the social
planner is given the capital stock k at the beginning of the current
period and allocates consumption across time optimally for the
household.
This function v () solves the follwoing recursion
v (k ) = max U (f (k ) − k 0 ) + βv (k 0 ) (16)
{0≤k 0 ≤f (k )}
Note that v (.) and w (.) are very different functions.

v () is the value function for the recursive formulation of the planner’s
problem and w () is the corresponding function for the sequential
problem.
We want to establish that v=w.
The capital stock k that the social planner brings into current period
is the result of past decisions.
k completely determines what allocations are feasible from today
onwards.
Therefore it is called the ”state variable”: It completely summarizes
the state of the economy today (i.e. all future options that the social
planner has)
The variable k 0 is decided or controlled today by the social planner.
Therefore it is called the control variable.
Equation 16 is a functional equation: the so-called Bellman equation.

Its solution is a function rather than a number or a vector.
The functional equation posits that the discounted lifetime utility of
the representative agent is given by the utility that he receives today
i.e. U (f (k ) − k 0 ) plus the discounted lifetime utility from today on,
βv (k 0 ).
This formulation makes trade-off of the planner clear.
Consumption (hence utility) today versus a higher capital stock to
work with (hence higher discounted future utility) from tomorrow
onwards.
For a given k, this maximization problem is easier to solve than the
∞
problem of picking an infinite sequence of capital stocks {kt +1 }t =0
from before.

But we have to do this maximization for every possible value of k.
By solving the functional equation we mean finding:
-A value function v (.) solving Equation 16.
-An optimal policy function k 0 = g (k ) that describes the optimal k 0
from the maximization part in Equation 16 as a function of k,i.e. for
each possible value that k can take.
Now we will work with the previously defined utility and production
functions.
U (c ) = ln (c ), f (k ) = k α , δ = 1
For these specifications, the functional equation can be solved by
hand.
The functional equation becomes
v (k ) = max ln (k α − k 0 ) + βv (k 0 )
{0≤k 0 ≤k α )}
Solving the Functional Equation: Guess and Verify
In the guess and verify method (or method of undetermined

coefficients), we guess a particular functional form of a solution.
Then we verify that the solution has in fact this form.
This method works well for the example at hand but not so well for
most other examples.
Let us make the following guess
v (k ) = A + Bln (k )
where A and B are unknown coefficients that need to be determined.
The method consists of three steps.

1 Solve the maximization problem on the RHS given the guess for v i.e.
solve
v (k ) = max ln (k α − k 0 ) + β(A + Bln (k 0 ))
{0≤k 0 ≤k α )}
- The constraints on k 0 do not bind so the FOCs for k’ is sufficient for

the unique solution.
- The FOCs yield
1 βB
=
kα − k0 k0
βBk α
k0 = (17)
1 + βB
βBk α
2 Evaluate the RHS at the optimal solution k 0 = 1+ βB . This yields
RHS = ln(k α − k 0 ) + β(A + Bln(k 0 ))

kα βBk α
= ln( ) + βA + βBln( )
1 + βB 1 + βB
βB
= −ln(1 + βB ) + αln(k ) + βA + βBln( ) + αβBln(k )
1 + βB
2 For our guess to solve the functional equation LHS must equal RHS
for all possible values of k. Equating both sides yields
βB
A + Bln (k ) = −ln (1 + βB ) + αln (k ) + βA + βBln ( )
1 + βB
+ αβBln(k )
βB
(B − α(1 + βB )) = −A − ln(1 + βB ) + βA + βBln( )
1 + βB
This equation has to hold for all possible values of k. Since the RHS is a
constant, the LHS must also be a constant.
Hence we need to equate the coefficient of ln (k ) to 0 which yields
B = 1−ααβ
Therefore the constant A has to satisfy
Therefore the constant A has to satisfy

βB
0 = −A − ln (1 + βB ) + βA + βBln ( )
1 + βB
1 αβ
= −A − ln( ) + βA + ln (αβ)
1 − αβ 1 − αβ
Solving this for A yields

1 αβ
A= [ ln (αβ) + ln (1 − αβ)]
1 − β 1 − αβ
The optimal policy function can be determined by plugging in the value of

B to Equation 17.
βBk α
g (k ) =
1 + Bβ
= αβk α
Hence our guess was correct: The function v ∗ (k ) = A + Bln (k ) with

A, B determined as above solves the functional equation with
associated policy function g (k ) = αβk α .
For this policy, the optimal policy of the social planner is save a
constant fraction αβ and consume a constant fraction (1 − αβ) of
output k α .
Recall our solution to the infinite horizon problem. It was the same !
So this shows that the solutions derived from Euler equation approach
and the dynamic programming approach are the same.
Also note that the policy function only defines a unique rule between
k and k 0 .
Depending on the initial value of ko , we can achieve different paths of
{kt }t∞=0 .
To sum up, we tackled the solution of social planner’s problem of the

discrete time neoclassical growth model both using the Euler equation
approach and the dynamic programming approach.
Both techniques yield the same result however the dynamic
programming approach is easier since the optimization is done over a
finite sequence.
At the same time, dynamic programming is applicable to a wider
range of models and parameterizations whereas the Euler equation
approach works for limited cases.

Dynamics Programming

Uploaded by

Copyright:

Available Formats

Dynamics Programming

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dynamics Programming

Uploaded by

Copyright:

Available Formats

Lecture 7

Introduction to Dynamic Programming

Econ 602 Spring 2020

Ibn Haldun University

April 27, 2020

Time is discrete and indexed by t=0,1,2...

Social Planner Problem in Sequential Formulation

Consider the problem of a social planner that wants to maximize the

Assumptions on preferences and technology

Rewriting Social Planner Problem in Sequential

Assuming full depreciation (δ = 1) and substituting

w (k̄o ) = max{kt +1 ,}t∞=0 ∑t∞=0 βt U (f (kt ) − kt +1 ) (5)

Solving the Social Planner Problem

There are two possible approaches to solving this problem

The Finite Horizon Case

Obviously kT +1 = 0 ,and given the Inada conditions on the utility

L = U (f (ko ) − k1 ) + ...βt U (f (kt ) − kt +1 ) + βt +1 U (f (kt +1 ) − kt +2 )

The Finite Horizon Case

Hence we can find the FOCs as

This first order condition is called Euler condition.

The Finite Horizon Case

The Finite Horizon Case

Recursively solving this backwards by plugging zT = 0 yields

The Infinite Horizon Case

Figure: Dynamics of saving rate

The Infinite Horizon Case

On the y axis, we draw zt +1 against zt on the x axis.

The Infinite Horizon Case

w T (k̄o ) = max{kt +1 }t∞=0 ∑t∞=0 βt U (f (kt ) − kt +1 ) (13)

U 0 (f (kt ) − kt +1 ) = βU 0 (f (kt +1 ) − kt +2 )f 0 (kt +1 )

The Infinite Horizon Case

The terminal condition is replaced by the transversality condition

lim βt U 0 (f (kt ) − kt +1 )f 0 (kt ) kt = 0

The Infinite Horizon Case

This theorem states that under certain assumptions the Euler

The Infinite Horizon Case

The Infinite Horizon Case

nonnegativity constraint on capital.

The Infinite Horizon Case

For this path, we have that

The Infinite Horizon Case

The Infinite Horizon Case

The Infinite Horizon Case

Hence non of the sequences contemplated in 2, can be an optimal

Following questions arise:

Recursive Formulation of Social Planner’s Problem

The above formulation of the social planner’s problem with a function

Recursive Formulation of Social Planner’s Problem

Note that v (.) and w (.) are very different functions.

Recursive Formulation of Social Planner’s Problem

Equation 16 is a functional equation: the so-called Bellman equation.

Recursive Formulation of Social Planner’s Problem

Solving the Functional Equation: Guess and Verify

In the guess and verify method (or method of undetermined

where A and B are unknown coefficients that need to be determined.

Solving the Functional Equation: Guess and Verify

The method consists of three steps.

- The constraints on k 0 do not bind so the FOCs for k’ is sufficient for

Solving the Functional Equation: Guess and Verify

RHS = ln(k α − k 0 ) + β(A + Bln(k 0 ))