Math Camp Day 4

Dynamic Optimization
short version

SAKAMOTO, Eiji1

September 30, 2024

1 I’m grateful to all the past lecturers for sharing their slides. All errors are my own.
1 / 61
Before start

Introduction

Dynamic Optimization in Discrete Time

Classical Approach
Introduction to DP
(Relatively) Formal Introduction to DP
Contraction Mapping Theorem
Solution Methods

1 / 61
Before the class

Introduction (myself)
1st year student of Doctoral degree in UTGSE
research topics: macroeconomics (Political Economics, Financial Crisis,
Econometrics, and so on...).
I was a TA for Core Econometrics II and Core Macro 1.
If you have a question, please speak up, or send email to me.
my address: [Link](at)[Link]
If you want to talk with me in person, please come to my lab after
sending me an email.
715, 7F, International Academic Research Building

2 / 61
Message

Welcome to the University of Tokyo!

Core courses and research may be verrrrry tough.
I’m with you.
If you want to talk with me in person, please come to my lab after
sending me an email.
715, 7F, International Academic Research Building
my address: [Link](at)[Link]
Info. for those who enter UTGSE
Real comment on M1 life at UTGSE
Honestly, how were your two years at UTGSE?
Survive! Hellish first Spring semester at UTGSE

3 / 61
Before start

Introduction

Dynamic Optimization in Discrete Time

Classical Approach
Introduction to DP
(Relatively) Formal Introduction to DP
Contraction Mapping Theorem
Solution Methods

3 / 61
Introduction

So far, we have learned static optimization.

Today, we discuss dynamic optimization.
”dynamic” means that problems include time
e.g.) allocate consumption between today and tomorrow.

4 / 61
Motivating Example 1

Consider the following utility maximization problem:

You have a cake of size w0 and eat it for two days. (t = 0, 1)
Let xt be the amount of cake you eat at date t.
Assume the utility function is written as
U (x0 , x1 ) := log x0 + β log x1
the flow utility of eating cake at date t is given by a logarithmic
function: u(xt ) := log xt
β ∈ (0, 1) represents the discount factor.
(Today is more important than tomorrow.)

5 / 61
Motivating Example 1
This problem is written as

max U (x0 , x1 ) = log x0 + β log x1 (= u(x0 ) + βu(x1 ))

{x0 ,x1 }

s.t. x0 + x1 = w0 , xt ≥ 0 (t = 0, 1)

Q. What is the optimal relation between x0 and x1 ?

6 / 61
Motivating Example 1
This problem is written as

max U (x0 , x1 ) = log x0 + β log x1 (= u(x0 ) + βu(x1 ))

{x0 ,x1 }

s.t. x0 + x1 = w0 , xt ≥ 0 (t = 0, 1)

Q. What is the optimal relation between x0 and x1 ?

It is given by deriving the first-order condition.
Substitute x1 = w − x0 in U (x0 , x1 ) and take a derivative w.r.t. x0 :
1 1
−β = 0 (or u′ (x0 ) − βu′ (w0 − x0 ) = 0)
x0 w0 − x0
1 1
∴ =β (or u′ (x0 ) = βu′ (x1 )) (∗)
x0 x1
The optimal allocation, (x0 , x1 ), should satisfy (∗).
This equation tells us a good intuition of dynamic optimization.

6 / 61
Motivating Example 1
What does 1/x (or u′ (x)) in (∗) mean economically?
Consider a linear approximation2 of log x (or u(x)) around x = X.
1
log x ≈ log X + (x − X)
X
(or u(x) ≈ u(X) + u′ (X)(x − X))

Let x = X + 1.
1
log (X + 1) − log X ≈
X
(or u(X + 1) − u(X) ≈ u′ (X))

Hence, 1/x (or u′ (x)) means incremental utility change!

→ so called Marginal Utility

2 Recall Taylor expansion learned in the Day 1! This is so called 1st order Taylor

expansion around X.
7 / 61
Motivating Example 1
Suppose you try to increase the amount of cake slightly at date 0, then the
equation (∗) says
marginal utility gain today 1/x0 (= u′ (x0 ))
=
discounted marginal utility cost tomorrow β × 1/x1 (= βu′ (x1 ))

Therefore, at the optimum, the benefit and cost of a marginal change in the
amount of cakes are balanced.

8 / 61
Lesson from this example

One’s decision about today’s action affects her utility tomorrow, and
thus,
decision maker faces a trade-off b/w today’s & future payoff.
Many economic problems have this dynamic nature:
Households decide how much to consume today and how much to save
for the future.
If a worker accepts a job offer and start working today, she loses
chances to get a better job in the future.
But there are many economic situations which we cannot describe only
with two-period model.
Therefore, it is important to study the ways to solve general dynamic
optimization problems!

9 / 61
Today’s Contents

Today’s focus is Infinite-horizon & deterministic cases.

Here is a Big Picture of dynamic optimization

10 / 61
Today’s Contents

Today’s goal:
1. Understand how to solve Dynamic Optimization in discrete time.
2. Especially, study a new approach: Dynamic Programming (DP)
Why DP?
1. Easy to solve (in some sense)
2. Because DP is everywhere!
▶ Micro: Repeated Games, Decision Theory
▶ Macro: Growth, Asset Pricing, DSGE model
▶ Metrics: Structural Estimation

11 / 61
Useful References

1. Acemoglu, D. (2009) “Introduction to Modern Economic Growth,”

Princeton University Press.
Chapter: 6, 16 for DP, Chapter: 7 for continuous time case
2. [SLP] Stokey, N. L., Lucas, R. E., & Prescott, E. (1989) “Recursive
Methods in Economic Dynamics,” Harvard University Press.
Chapter: 4, 9 for DP
3. [LS] Ljungqvist, L., & Sargent, T. J. (2018) “Recursive Macroeconomic
Theory,” 4th edition, MIT Press.
Chapter: 3, Appendix A for DP
4. [QE] QuantEcon also introduces Dynamic Programming using
Python and Julia

12 / 61
Before start

Introduction

Dynamic Optimization in Discrete Time

Classical Approach
Introduction to DP
(Relatively) Formal Introduction to DP
Contraction Mapping Theorem
Solution Methods

12 / 61
Dynamic Optimization in Discrete Time

Consider the following standard utility maximization problem:

∞
X
max β t u(ct )
{ct }t=0 ,{kt+1 }∞
∞
t=0
t=0
s.t. kt+1 = f (kt ) − ct , ct ≥ 0, kt+1 ≥ 0 (t = 0, 1, · · · )
k0 > 0; given
kt , ct : capital stock and consumption at period t
u, f : u′ > 0, u′′ < 0, f ′ > 0, f ′′ < 0 w/ some conditions
β ∈ (0, 1) : discount factor
This problem is called ”sequential problem”, since you choose infinite
sequences {ct }∞ ∞
t=0 , {kt+1 }t=0 .

13 / 61
How to Solve the Problem?

As I said, there are two methods to solve this type of problem:

Classical approach (Lagrangian method)
Dynamic Programming approach

14 / 61
Before start

Introduction

Dynamic Optimization in Discrete Time

Classical Approach
Introduction to DP
(Relatively) Formal Introduction to DP
Contraction Mapping Theorem
Solution Methods

14 / 61
Classical Approach
1. Set up the Lagrangian L:
∞
X
L := β t {u(ct ) + λt [f (kt ) − kt+1 − ct ]}
t=0

2. Take derivatives w.r.t. ct , kt+1 , and set them zero.

∂L
= β t [u′ (ct ) − λt ] = 0
∂ct
∂L
= β t [−λt + βλt+1 f ′ (kt+1 )] = 0
∂kt+1

3. Eliminate the Lagrangian multiplier λt from the equations.

u′ (ct ) = βu′ (ct+1 )f ′ (kt+1 )

This equation is called ”Euler equation (EE)”.

15 / 61
Euler Equation

Intuition:
The Euler equation describes the optimal relation between any two
periods (remember the cake example!).
LHS u′ (ct ) : marginal utility loss of increasing saving today
RHS βu′ (ct+1 ) : discounted marginal utility gain
× f ′ (kt+1 ) : marginal income gain tomorrow due to saving

That is, the benefit and cost of a marginal change in consumption and
saving are balanced at the optimum !

16 / 61
Transversality Condition

In the finite time horizon case;

We want to derive 2T + 2 unknowns {ct }Tt=0 , {kt+1 }Tt=0 .
using 2T + 2 equations
T Euler equations (t = 0, · · · , T − 1).
T + 1 resource constraints (t = 0, · · · , T ).
1 terminal condition kT +1 = 0.
(it’s optimal to use up all the resources by the terminal period.)
On the other hand, in the infinite time horizon case, we cannot define the
terminal condition since there is no terminal period.
An analog of ”terminal condition” = transversality condition (TVC).

17 / 61
Transversality Condition

In this example, TVC is written as

lim β t u′ (ct )f ′ (kt )kt = 0

t→∞
It is an optimal condition that determines an optimal behavior as
t → ∞.
Intuition of TVC: the value of the capital stock kt (measured by
utility) goes to zero as t → ∞.
β t u′ (ct )f ′ (kt ) : discounted utility value of one more unit of capital
kt : total capital stock
This condition does not say that the capital itself converges to zero in
the limit.

18 / 61
Classical Approach

Sufficiency of EE & TVC:

Under some technical conditions, an allocation {c∗t , kt+1
∗
}∞
t=0 satisfying
both EE and TVC solves the sequential problem. That is,
{c∗t , kt+1
∗
}∞
t=0 is an optimal allocation.
Today, we want to skip the proof of this fact.
If you want to see details and proof, see [SLP] Chap.4.5

19 / 61
Exercise
Revisit the cake-eating problem, but now, consider an infinite time horizon
case: t = 0, 1, 2, · · · .
You have w0 cake at period 0.
Flow utility is given by u(x) := ln x and future utility is discounted by β.
Of course, the amount of cake is always non-negative.
Questions.
1. Formulate sequential problem.
2. Set up Lagrangian
3. Derive Euler equation
4. Solve EE with respect to xt given x0
5. Solve the budget constraint with respect to wt given x0
6. Find one x0 to satisfy TVC
7. Solve xt and wt only with t, β, and w0

20 / 61
Solution Example I
1. Formulate sequential problem.
∞
X
max β t ln(xt )
{xt }t=0 ,{wt+1 }∞
∞
t=0
t=0
s.t. wt+1 = wt − xt , xt ≥ 0, wt+1 ≥ 0 (t = 0, 1, · · · )
w0 ; given

2. Set up Lagrangian
∞
X
L := β t {ln(xt ) + λt [wt+1 − wt + xt ]}
t=0

3. Derive Euler equation

1 1
=β
xt xt+1

21 / 61
Solution Example II
4. Solve EE with respect to xt given x0

xt = β t x0

5. Solve the budget constraint with respect to wt given x0

wt+1 = wt − β t x0
1 1
∴ wt = w0 − x0 + β t x0
1−β 1−β

6. Find one x0 to satisfy TVC

1
βt
wt → 0
xt
 
t 1 1 t 1
∴β t w0 − x0 + β x0 → 0
β x0 1−β 1−β
∴ x0 = (1 − β)w0

22 / 61
Solution Example III

7. Solve xt and wt only with t, β, and w0

xt = β t (1 − β)w0
wt = β t w0

23 / 61
Before start

Introduction

Dynamic Optimization in Discrete Time

Classical Approach
Introduction to DP
(Relatively) Formal Introduction to DP
Contraction Mapping Theorem
Solution Methods

23 / 61
Introduction to Dynamic Programming

The classical approach uses infinite equations to derive an infinite

number of unknowns {ct , kt+1 }∞t=0 , which is in general hard to solve!!
Can we solve it with less energy?
→ Yes! Dynamic Programming (DP).
DP is an alternative solution method, which exploits a property of the
problem: Recursive structure.
First, I’m going to talk about properties of the recursive structure
This is a bit technical, but please wait a moment...
Then, next I showcase HOW we can solve the problem EASILY.

24 / 61
re:Sequential problem

Consider the same standard utility max problem:

∞
X
w(k0 ) := max∞ β t u (f (kt ) − kt+1 )
{kt+1 }t=0
t=0
s.t. 0 ≤ kt+1 ≤ f (kt ) (t = 0, 1, · · · ) k0 > 0; given

where, we eliminate ct using the flow budget constraints.

This problem has the recursive structure.
That is, the structure of the choice problem that a decision maker faces
is identical at any moment.

25 / 61
Recursive Structure

∞
X
v (k0 ) = max β t u (f (kt ) − kt+1 )
{kt+1 }∞ ,k
t=0 0
given t=0
∞
( " #)
X
t−1
= max u (f (k0 ) − k1 ) + β max β u (f (kt ) − kt+1 )
k1 {kt+1 }∞ ,k
t=1 1
given t=1

with conditions 0 ≤ kt+1 ≤ f (kt ).

This implies
v(k0 ) = max u (f (k0 ) − k1 ) + βv(k1 )
0≤k1 ≤f (k0 ),k0 given

This expression is called recursive formulation.

It looks much easier, because you should choose only one variable k1 !
but now, we don’t know a form of function w...

26 / 61
What ’solving the recursive problem’ means
In sequential problem, the way to solve is to find infinite sequence.
Here, the problem is recursive.

v(k0 ) = max u (f (k0 ) − k1 ) + βv(k1 )

0≤k1 ≤f (k0 ),k0 given

Now sequences don’t appear!

One way to solve this recursive problem is
1 find a function v(·)
2 then, find k1 to maximize u (f (k0 ) − k1 ) + βv(k1 ) given k0
3 then, find k2 to maximize u (f (k1 ) − k2 ) + βv(k2 ) given k1
4 then, find k3 to maximize u (f (k2 ) − k3 ) + βv(k3 ) given k2
5 then, find k4 ...
6 then, ...
So, want to find
1 v(·)
2 a function to map today’s k to tomorrow’s k′ , g(·).

27 / 61
Terminology of Recursive Formulation
The equation (1) is called functional equation (FE) or, Bellman
equation:

v(k) = max u (f (k) − k ′ ) + βv(k ′ ) (1)

k′ ∈[0,f (k)]

k, state variable: variable which is predetermined.

k′ , control(choice) variable: decided by agents today.
v(·), value function: the value of life time consumption give today’s state
evaluated at today.
k′ = g(k), policy function: describes the optimal k′ as a function of k.
Exercise: Write down the recursive formulation of the cake-eating problem.

28 / 61
Terminology of Recursive Formulation
The equation (1) is called functional equation (FE) or, Bellman
equation:

v(k) = max u (f (k) − k ′ ) + βv(k ′ ) (1)

k′ ∈[0,f (k)]

k, state variable: variable which is predetermined.

k′ , control(choice) variable: decided by agents today.
v(·), value function: the value of life time consumption give today’s state
evaluated at today.
k′ = g(k), policy function: describes the optimal k′ as a function of k.
Exercise: Write down the recursive formulation of the cake-eating problem.
Answer:
v(w) = max ′
u(w − w′ ) + βv(w′ )
0≤w ≤w

28 / 61
Before start

Introduction

Dynamic Optimization in Discrete Time

Classical Approach
Introduction to DP
(Relatively) Formal Introduction to DP
Contraction Mapping Theorem
Solution Methods

28 / 61
General Form
Before formal discussions, we generalize both SP and FE:
Sequential Problem (SP)
∞
X
w(x0 ) = max∞ β t F (xt , xt+1 )
{xt+1 }t=0
t=0
s.t. xt+1 ∈ Γ(xt ) (t = 0, 1, · · · ), x0 ∈ X; given

Functional Equation (FE)

v(x) = max {F (x, y) + βv(y)}, ∀x ∈ X

y∈Γ(x)

F : period return function (e.g. flow utility function: u(f (k) − k′ ))

Γ: constraint set (e.g. feasible capital set: {k′ ∈ R|0 ≤ k′ ≤ f (k)} )
Question: What is an (economically) intuitive difference between SP and
FE?

29 / 61
Relation between SP & FE
What you derive is completely different:
in SP optimal infinite sequence {x∗t+1 }∞
t=0

in FE value function and associated policy function v, y ∗ = g(x)

Intuition of solution:
in SP you choose a time path, or schedule of the amount of cake you eat
from today to the future, given the initial condition.
in FE you choose an optimal strategy of cake-eating: for any given amount of
cake, how much you eat today and save the rest.

30 / 61
Questions about FE

Here is a list of Questions about FE

1. Equivalence between SP & FE
Under what condition, can we say
(1) w = v: maximized lifetime utility and value function.
(2) equality between optimal sequential allocation {x∗t+1 }∞t=0 and
{x̂t+1 }∞
t=0 generated by policy function g and initial value x0
(x̂1 = g(x0 ), x̂2 = g(x̂1 ), · · · ).
2. Under what condition,
(1) does a solution to FE exists?
(2) if so, is it unique?
(3) How can we find the solution?

31 / 61
Principle of Optimality

We skip a detailed discussion of Question 1.

In fact, under weak assumptions, we can show that
w = v and {x∗t+1 } = {x̂t+1 }.
Thus, it is allowed to solve FE instead of solving SP directly.
Proofs will(?) be covered in core courses, or see [SLP], Chap.4
Let’s move on to Question 2.

32 / 61
Existence & Uniqueness of solution to FE

Question.2 Under what condition,

(1) does a solution to FE exists?
(2) if so, is it unique?
(3) How can we find the solution?
Surprisingly, only one theorem answer this set of questions:
Contraction Mapping Theorem (CMT)
=Banach fixed-point theorem
Why?
Because finding a solution to FE is equivalent to finding a fix point of a
mapping (or an operator) T where

(T (v(x)) =)(T v)(x) := max {F (x, y) + βv(y)}

y∈Γ(x)

33 / 61
Before start

Introduction

Dynamic Optimization in Discrete Time

Classical Approach
Introduction to DP
(Relatively) Formal Introduction to DP
Contraction Mapping Theorem
Solution Methods

33 / 61
Contraction Mapping

operator T : map a point/element to another point/element

Def. Contraction mapping
Let (S, d) be a metric space and T : S → S be an operator.
T is a contraction mapping if, for some β ∈ (0, 1),

∀x, y ∈ S d (T x, T y) ≤ βd (x, y) .

β is called the modulus of the contraction mapping.

Intuition: T makes two points closer.
e.g.) T x = 12 x

34 / 61
Contraction Mapping Theorem

Thm. Contraction Mapping Theorem (CMT)

Let (S, d) be a complete metric space, and suppose that T : S → S is a
contraction mapping with modulus β. Then
(a) T has a unique fixed point x∗ ∈ S, i.e., there exists a unique x∗ ∈ S such
that T x∗ = x∗ ;
(b) for any x ∈ S and any n ∈ N, we have d(T n x, x∗ ) ≤ β n d(x, x∗ ), and thus
T n x → x∗ as n → ∞.

Intuition: If T is a contraction mapping

(a) A unique fixed point exists
(b) You can find the point by infinitely operating T on any initial elements
Let’s look at more detail!

35 / 61
Metric Space

To explain CMT, introduce some preliminary concepts:

Def. Metric space
Let S be a nonempty set and d : S × S → R.
d is a metric on S if
1 ∀x, y ∈ S d (x, y) ≥ 0; d (x, y) = 0 if and only if x = y
2 ∀x, y ∈ S d (x, y) = d (y, x)
3 ∀x, y, z ∈ S d (x, y) + d (y, z) ≥ d (x, z)
We call (S, d) a metric space.
Intuitively, d is a distance between two points.
(e.g.) S = R2 , the Euclidean norm ∥ · ∥ is one of metrics on S.

36 / 61
Convergence of Sequences
Def. Convergence of sequences
Let (S, d) be a metric space. A sequence {xn }∞
n=1 in S converges to x ∈ S if for
every ε > 0, there exists a natural number N = N (ε) such that n ≥ N (ε) implies
d(xn , x) < ε. In this case, we write limn→∞ xn = x or xn → x as n → ∞
A sequence that converges to some point is called convergent.
Def. Cauchy sequences
Let (S, d) be a metric space. A sequence {xn }∞ n=1 in S is a Cauchy sequence in
(S, d), if for every ε > 0, there exists a natural number M = M (ε) such that
n, m ≥ M (ε) imply d(xn , xm ) < ε.
Intuitively, if we choose sufficiently large n and m, the distance b/w two
points xn and xm can be arbitrary small.
A convergent is always a Cauchy, but the converse does not hold.
(e.g.) Let S = (0, 1] and d1 (x, y) = |x − y| for x, y ∈ S. Consider a
sequence {1/n}n∈N . This is a Cauchy sequence, but does not converge to
any point in S.

37 / 61
Complete Metric Spaces

Def. Completeness
A metric space (S, d) is complete if every Cauchy sequence in S is
convergent.
The significance of completeness is that when searching for the solution
to a problem, it sometimes is the case that we are able to construct a
Cauchy sequence whose limit would be a solution if it actually exists.
In a complete metric space, we can be sure that our solution does exist
as a well-defined element of the space.

38 / 61
Contraction Mapping

Define an operator T as a mapping that maps a point/element to

another point/element.
Def. Contraction mapping
Let (S, d) be a metric space and T : S → S be an operator.
T is a contraction mapping if, for some β ∈ (0, 1),

∀x, y ∈ S d (T x, T y) ≤ βd (x, y) .

β is called the modulus of the contraction mapping.

Intuitively, with the help of T , the distance between two points (x, y)
gets closer.
(e.g.) S = R, d(x, y) = ||x − y||. T : X → X such that T x = 12 x is a
contraction mapping with modulus 12 .

39 / 61
Fixed Point

Def. Fixed point

A fixed point of T is any element of S satisfying x = T x.

Fixed Point of One-Dimensional Mapping

40 / 61
Contraction Mapping Theorem

Thm. Contraction Mapping Theorem (CMT)

Let (S, d) be a complete metric space, and suppose that T : S → S is a
contraction mapping with modulus β. Then
(a) T has a unique fixed point x∗ ∈ S, i.e., there exists a unique x∗ ∈ S such
that T x∗ = x∗ ;
(b) for any x ∈ S and any n ∈ N, we have d(T n x, x∗ ) ≤ β n d(x, x∗ ), and thus
T n x → x∗ as n → ∞.

Proof: [SLP] Thm.3.2 (the property of completeness is used in the proof).

Let’s apply this theorem to the FE!

41 / 61
CMT to FE

Recall that the FE is:

v(x) = max F (x, y) + βv(y)

y∈Γ(x)

Define the Bellman operator T as

(T v)(x) = max F (x, y) + βv(y)

y∈Γ(x)

T is a mapping from the set of functions to the set of functions.

A solution to the FE is then a fixed point of the operator T , i.e., a
function v ∗ such that v ∗ = T v ∗ .

42 / 61
CMT to FE

Therefore, the contraction mapping theorem (CMT) says that,

if the Bellman operator T is a contraction mapping,
CMT(a) the FE has a unique solution v ∗ .
CMT(b) for any arbitrary guess v0 , by applying T repeatedly
(vn+1 = T vn ), a sequence {vn }∞ ∗
n=0 always converges to v .

Note. This result is very powerful; even if we choose v0 (x) = 0, we can

find a unique true value function v ∗
(this algorithm is called ”value function iteration (VFI)”).
Next Question: When is T a contraction mapping?

43 / 61
Blackwell’s Sufficient Conditions

Thm. Blackwell’s Sufficient Conditions

Let X ⊆ RL and B(x) be the space of bounded functions f : X → R with the
sup norm d∞ (f, g) := supx∈X |f (x) − g(x)|.
Let T : B(X) → B(X) be an operator satisfying
1. Monotonicity:
If f, g ∈ B(X) and f (x) ≤ g(x) for all x ∈ X, then
(T f )(x) ≤ (T g)(x) for all x ∈ X.
2. Discounting:
Let the function f + a, for f ∈ B(X) and a ≥ 0, be defined by
(f + a)(x) = f (x) + a (i.e., for all x, a is added to f (x)).
There exists some β ∈ (0, 1) s.t.
[T (f + a)](x) ≤ [T f ](x) + βa (∀f ∈ B(X), ∀a ≥ 0, ∀x ∈ X)

Then, T is a contraction with modulus β.

Thanks to this theorem, we can easily tell whether a mapping is a contraction or
not. (Proof: [SLP] them.3.3)

44 / 61
CMT to FE

Revisit the Question.2: Under what condition,

(1) does a solution to FE exists?
(2) if so, is it unique?
(3) How can we find the solution?
Now we can answer these questions as follows:
If the Bellman operator T satisfies Blackwell’s Sufficient Conditions,
T is a contraction mapping.
Then, CMT guarantees that T has a unique fixed point, and we can
easily find it by applying T repeatedly.
That is, FE has a unique solution and it is easy to find it.
As the end of this part, I give you one property of value function.

45 / 61
Property of value function
Thm. Envelope theorem (Benveniste & Scheinkman thm)
Let (X, F, β, Γ) satisfy technical conditions and let v be the unique fixed
point of T (= solution to FE) and g the associated policy function.
If x0 ∈ int(X) and g(x0 ) ∈ int(Γ(x0 )), then v is continuously differentiable
at x0 with derivatives given by

∂v(x) ∂F (x, g(x))

=
∂x x=x0 ∂x x=x0

Recall that, at the point x0 , FE is written as

v(x0 ) = F (x0 , g(x0 )) + βv(g(x0 ))

Thus, this theorem says that an indirect effect of a change in x on v(x),

through a change in the control y = g(x), can be ignored at the optimum.
Using this theorem, we can derive the Euler equation from the FE.

46 / 61
Property of value function
proof.
Consider
v(x) = max (F (x, y) + βv(y))
y

= F (x, g(x)) + βv(g(x)),

∂F (x,y) ∂v(y)
where ∂y +β ∂y = 0.
y=g(x) y=g(x)
Thus we get the following.
∂v(x) d
= {F (x, g(x)) + βv(g(x))}
∂x dx
∂F (x, g(x)) ∂F (x, y) ∂g(x) ∂v(y) ∂g(x)
= + +β
∂x ∂y y=g(x) ∂x ∂y y=g(x) ∂x
!
∂F (x, g(x)) ∂F (x, y) ∂v(y) ∂g(x)
= + +β
∂x ∂y y=g(x) ∂y y=g(x) ∂x
∂F (x, g(x))
=
∂x
47 / 61
Property of value function
Consider the following example:

v(k) = max u(f (k) − k ′ ) + βv(k ′ )

k′ ∈[0,f (k)]

From the FOC w.r.t. k ′ , g(k) satisfies

u′ (f (k) − g(k)) = βv ′ (g(k))

From the envelope theorem, we get

v ′ (k) = u′ (f (k) − g(k))f ′ (k)

Now, let k = kt , g(k) = kt+1 and f (k) − g(k) = ct , then above equations
are
u′ (ct ) = βv ′ (kt+1 )
v ′ (kt+1 ) = u′ (ct+1 )f ′ (kt+1 )

Combining them, we obtain the Euler equation:

u′ (ct ) = βu′ (ct+1 )f ′ (kt+1 )

48 / 61
Before start

Introduction

Dynamic Optimization in Discrete Time

Classical Approach
Introduction to DP
(Relatively) Formal Introduction to DP
Contraction Mapping Theorem
Solution Methods

48 / 61
How to solve FE?

So far, we have learned:

Relation between SP and FE.
optimal sequence {xt+1 }∞
t=0 v.s. value & policy function v, g
Envelope theorem and Euler equation.
Contraction mapping theorem.
guarantees existence and uniqueness of solution to FE.
Blackwell’s sufficient condition
tells us when we can apply CMT to FE.
Final Question. How to solve FE? → 3 methods.

49 / 61
How to Solve FE?

There are 3 ways to solve FE:

1. Guess & Verify.
▶ Guess the functional form of v or policy function, and verify whether
the guess is correct.
▶ This method is only used when we can find a closed-form(can solve by
hand) solution; very limited!
2. Value function iteration (VFI).
▶ Start from any initial guess of value function, and keep updating until it
converges.
▶ In practice, we often use this method.
▶ Computational method
3. Policy function iteration (not covered today).

50 / 61
Guess & Verify
Consider a cake-eating problem:

ln w′ − w + βv(w′ )


v(w) = max
′
0≤w ≤w
1. Guess the value function as v(w) = A + B ln w with some constant A, B.
2. solve the maximization in the RHS given this guess:

ln w − w′ + β(A + B ln w′ )


max
′
0≤w ≤w

FOC w.r.t. w′ implies βB

w′ = w
1 + βB

3. Substitute it into the RHS

(1 + βB) ln w + βA + βB ln βB − (1 + βB) ln(1 + βB)

and verify RHS is in the guessed form, v(w) = A + B ln w.

...compare the coefficients (solve for A and B):

A = βA + βB ln βB − (1 + βB) ln(1 + βB)

B = 1 + βB

51 / 61
Guess & Verify
Finally, we obtain the value function and the optimal policy function as
follows:

v(w) = A + B ln w
ln(1 − β) β ln β 1
= + + ln w
1−β (1 − β)2 1−β
βB
w′ = g(w) = w
1 + βB
= βw

Exercise: Derive the value function and associated policy function for the
following FE using Guess & Verify of value function:

v(k) = ′ maxα ln (k α − k ′ ) + βv(k ′ )

k ∈[0,k ]

(Hint: guess the value function as the form of A + B ln k.)

52 / 61
Solution Example

value function and associated policy function are as follows:

 
1 αβ α
v(k) = ln(αβ) + ln(1 − αβ) + ln(k)
1 − β 1 − αβ 1 − αβ
k ′ = g(k) = αβk α

53 / 61
Value Function Iteration

Consider the following FE:

v(k) = ′ maxα ln (k α − k ′ ) + βv(k ′ )

k ∈[0,k ]

Then, the procedure of value function iteration (VFI) is

1. Make an arbitrary initial guess v0 (say, v0 (k) = 0 ∀k ∈ R+ )
2. Generate a sequence of functions {vn }∞
n=1 by iterative application of
the operation below;

∀k ∈ R+ , vn+1 (k) = ′ maxα ln (k α − k ′ ) + βvn (k ′ )

k ∈[0,k ]

We know that CMT guarantees the convergence of {vn }∞

n=1 to v.

54 / 61
Value Function Iteration
Example: Suppose we start from a zero function as an initial guess
(v0 (k) = 0)
v1 (k) is given by

v1 (k) = ′ maxα ln(k α − k ′ ) + β·0

k ∈[0,k ] = v0 (k ′ )

By solving the maximization in RHS, we get k ′ = g1 (k) = 0.

Substitute it and obtain v1 (k) :

v1 (k) = ln(k α − 0) = α ln k

v2 (k) is given by

v2 (k) = ′ maxα ln(k α − k ′ ) + β·α ln k ′

k ∈[0,k ] = v1 (k ′ )

...solve the maximization and obtain v2 , and so on.

By iterating this procedure, {vn }∞
n=0 converges to v.

55 / 61
56 / 61
Review Questions

review questions to deepen your understanding of DP!

1. Explain the difference between Sequential Problem (SP) and
Functional Equation (FE). What is a solution to SP/FE?
2. Explain state variable & control variable.
3. What is a fixed point of the Bellman operator? How does it relate
to the FE?
4. Explain the procedure of Value Function Iteration (VFI).
5. What are the conditions under which the Bellman operator is a
contraction?

57 / 61
Exercise
Consider the following sequential problem:
∞
X
max β t ln(ct )
{ct }t=0 ,{kt+1 }∞
∞
t=0
t=0
s.t. kt+1 = A1−α ktα − ct , ct ≥ 0, kt+1 ≥ 0 (t = 0, 1, · · · )
k0 , A > 0; given

Qestions.
1. Set up the recursive formulation of this problem.
2. Derive the Euler equation.
3. Derive the policy function using ”Guess & Verify” of the policy
function.
*Hint for (3): Guess the functional form of the policy function and verify it
satisfies the Euler equation. A natural candidate of the guess is
c = h(k) = γA1−α kα and k′ = g(k) = δA1−α kα for some constants γ, δ > 0.

58 / 61
Solution Example
1. Set up the recursive formulation:
ln A1−α kα − k′ + βv(k′ )


v(k) = max
0≤k′ ≤A1−α kα

2. FOC w.r.t. k′ is
1
= βv ′ (k′ )
A1−α kα − k′
Evaluate k′ at g(k) and apply the envelope theorem:
αA1−α g(k)α−1
v ′ (g(k)) =
− g(g(k))
A1−α g(k)α
Note that the optimal consumption is c = h(k) = A1−α kα − g(k). Thus,
combining above equations, we obtain
1 αβA1−α g(k)α−1
=
h(k) h(g(k))
or, under the notations of SP;
α−1
1 αβA1−α kt+1
=
ct ct+1
(where, kt = k, kt+1 = g(k), ct = h(k), ct+1 = h(g(k)).)
59 / 61
Solution Example (cont’d)
3. Guess the policy functions of consumption and saving as
h(k) = γA1−α kα , g(k) = δA1−α kα for some constants γ, δ > 0.
(1) Given the guess and the resource constraint, we have δ = 1 − γ.
(2) Substitute the guess into the Euler equation:
1 αβA1−α g(k)α−1
=
γA1−α kα γA1−α g(k)α
αβ
=
γg(k)
αβ
=
γ(1 − γ)A1−α kα
(3) By comparing the coefficients, we have
γ(1 − γ)
γ=
αβ
∴ γ = 1 − αβ
Therefore, the policy functions are
c = h(k) = (1 − αβ)A1−α kα , k′ = g(k) = αβA1−α kα

60 / 61
Final Message

At most only one person can be a strictly dominant student.

So don’t be sad even if you find those who you feel are smarter than
you.
⇔ Most of you can find smarter student than you in some sense.
So don’t be arrogant even if you feel you are the best in your class.
In many cases, it’s an illusion.
And you can find many dominant researchers around the world.
Don’t be shy!
The best way to learn something is teaching it to and learning it from
your friends.
Good luck!

61 / 61