Dynamic Programming - Matthew Hoelle Home

ECON608 Macroeconomic Theory I
Fall 2014
Matthew Hoelle
Purdue University
Dynamic Programming Practice Problems
1. If T : X ! X is a contraction and X is a complete metric space, prove that there exists at
most one …xed point.
2. Prove that if is upper hemicontinuous and single-valued, then it is a continuous function.
For these results, you can use the sequential de…nition of continuity:
A function f is continuous i¤ fxn g ! x implies ff (xn )g ! f (x):
3. Prove that the constraint correspondence
is well-de…ned and continuous.
4. Prove part (i) of Berge’s Maximum Theorem, which is stated as follows:
If u(c) + V (k 0 ) is continuous and is continuous, then (ii)
for
(k) = arg maxu(c) + V (k 0 ) 8k 2 A:
is upper hemicontinuous
c;k0 2 (k)
5. Prove part (ii) of Berge’s Maximum Theorem, which is stated as follows:
If u(c) + V (k 0 ) is continuous and
T V (k) = max u(c) + V (k 0 ) 8k 2 A:
is continuous, then (ii) T V is continuous for
c;k0 2 (k)
6. Recall that CB(A) is the set of continuous, bounded, and concave functions with compact
domain A (a complete metric space). Show that T : CB(A) ! CB(A) ; where the mapping
T is de…ned as before:
max u(c) + V (k 0 )
(T V )(k) =
:
c; k 0 c + k 0 Rk + w
7. Assume that u is strictly concave, and prove that there exists a unique solution to
max u(c) + V (k 0 )
:
c; k 0 c + k 0 Rk + w
8. Write down the …rst order conditions of the Bellman equation. Use them to argue that the
value function V is di¤erentiably strictly increasing.
9. Recall that the policy function is de…ned as g : A ! A such that
g(k) = arg max u(Rk + w
k0 2A
k 0 ) + V (k 0 ):
Assume that u is strictly concave. Then g is a function. From Berge’s Theorem, g is continuous. Prove that g satis…es the following properties:
(a) g is continuously di¤erentiable (C 1 )
(b) g is strictly increasing (Dg(k) > 0 8k 2 A)
Hint: Use the Implicit Function Theorem. You may assume that V is twice continuously
di¤erentiable (C 2 ), a fact shown by Santos, Econometrica (1991).
1
Dynamic Programming Practice Problems (Solutions)
1. If T : X ! X is a contraction and X is a complete metric space, prove that there exists at
most one …xed point.
Solution:
Suppose, in order to obtain a contradiction, that there exist two …xed points,
x and x ; with x 6= x : By de…nition of a …xed point, both T (x ) = x and T (x ) = x :
By the de…nition of a contraction, for some 2 (0; 1) :
d (T (x ) ; T (x ))
d (x ; x ) :
By the de…nition of the …xed points, this implies
d (x ; x )
d (x ; x ) ;
which is only true if d (x ; x ) = 0: But this is ruled out by our initial supposition x 6= x :
This contradiction completes the argument.
2. Prove that if is upper hemicontinuous and single-valued, then it is a continuous function.
For these results, you can use the sequential de…nition of continuity:
A function f is continuous i¤ fxn g ! x implies ff (xn )g ! f (x):
Solution:
If is upper hemicontinuous, then for any sequence fkn g ! k and (cn ; kn0 ) 2
(kn ) 8n 2 N with fcn ; kn0 g ! (c; k 0 ) ; the limit point (c; k 0 ) 2 (k) : Since is single-valued,
then 8n; 9! (cn ; kn0 ) = (kn ) and 9! (c; k 0 ) = (k) : This states that (kn ) ! (k) ; which is
exactly the de…nition of continuity.
3. Prove that the constraint correspondence
Solution:
that
is well-de…ned and continuous.
Recall that the contraint correspondence
k 7!
c; k 0 2 [0; c]
A : c + k0
:A
[0; c]
A is de…ned such
Rk + w :
is well-de…ned as (k) is nonempty, since it contains the element (0; 0) for any k since R
and w 0 by assumption (R = D1 f (k; 1) 0 and w = D2 f (k; 1) 0).
0
Continuity requires the veri…cation of two parts: upper hemicontinuity (uhc) and lower hemicontinuity (lhc).
Claim:
is upper hemicontinuous.
Consider a sequence fkn g ! k and any sequence fcn ; kn0 g such that (cn ; kn0 ) 2 (kn ) 8n 2 N
and fcn ; kn0 g ! (c; k 0 ) : We must show that (c; k 0 ) 2 (k) : Suppose otherwise, that either
c < 0; c > c; k 0 < 0; or k 0 > k: Then there must exist n such that cn < 0; cn > c; kn < 0; or
kn > k: This contradicts that (cn ; kn0 ) 2 (kn ) 8n 2 N:
Claim:
is lower hemicontinuous.
Consider a sequence fkn g ! k and any (c; k 0 ) 2
following manner:
cn ; kn0
where
n
=
=
0
n c; k
Rkn +w
c+k0
1
8n 2 N;
(k) : I de…ne the sequence fcn ; kn0 g in the
if Rkn + w < c + k 0 and c + k 0 > 0
:
otherwise
2
If c + k 0 = 0; then since R
0 and w
0 by assumption (R = D1 f (k; 1)
0 and w =
D2 f (k; 1) 0), the terms (cn ; kn0 ) = n (c; k 0 ) = (0; 0) trivially satisfy the budget constraint
cn + kn0
Rkn + w for any n 2 N: We then focus on the nontrivial case in which c + k 0 > 0: I
need to verify that the sequence fcn ; kn0 g satis…es (i) fcn ; kn0 g ! (c; k 0 ) and (ii) (cn ; kn0 ) 2 (kn )
8n 2 N: As fkn g ! k and increasing utility implies c + k 0 = Rk + w; then f n g ! 1; implying
fcn ; kn0 g ! (c; k 0 ) : Since n 2 [0; 1] and 0
c
c and 0
k0
k; then 0
cn
c and
0
0 kn k 8n 2 N: The budget constraint for any n 2 N is given by:
cn + kn0 =
n
c + k0 =
Rkn +w
c+k0
(c + k 0 ) if Rkn + w < c + k 0
1 (c + k 0 )
if Rkn + w c + k 0
Rkn + w:
Thus, (cn ; kn0 ) 2
(kn ) 8n 2 N; …nishing the proof.
4. Prove part (i) of Berge’s Maximum Theorem, which is stated as follows:
If u(c) + V (k 0 ) is continuous and is continuous, then (ii)
for
(k) = arg maxu(c) + V (k 0 ) 8k 2 A:
is upper hemicontinuous
c;k0 2 (k)
Solution:
Suppose that
is not uhc. Then for some sequence kn 2 A; (cn ; kn0 ) 2 (kn )
8n 2 N such that lim kn = k 2 A; it is not true that lim (cn ; kn0 ) = (c; k 0 ) 2 (k): As
n!1
n!1
is uhc, there is a subsequence, wlog the original sequence, such that lim (cn ; kn0 ) = (c; k 0 ) 2
n!1
(k): Then, it must be that (c; k 0 ) 2
= (k); even though (cn ; kn0 ) 2 (kn ) 8n 2 N: As is lhc,
c) +
then for every c^; k^0 2 (k); in particular c^; k^0 2 (k) such that u(c) + V (k 0 ) < u(^
V (k^0 ); there exists a sequence c^n ; k^n0 2 (kn ) for n 2 N such that lim c^n ; k^n0 = c^; k^0 :
n!1
Since u and V are continuous,
lim u(cn ) + V (kn0 ) = u(c) + V (k 0 ) < u(^
c) + V (k^0 ) = lim u(^
cn ) + V (k^n0 ):
n!1
n!1
As x c^n ; k^n0 2 (kn ) for n 2 N; then this contradicts that (cn ; kn0 ) 2
(kn ) for n 2 N:
5. Prove part (ii) of Berge’s Maximum Theorem, which is stated as follows:
If u(c) + V (k 0 ) is continuous and
T V (k) = max u(c) + V (k 0 ) 8k 2 A:
is continuous, then (ii) T V is continuous for
c;k0 2 (k)
Solution:
To prove part (ii), we use part (i):
is upper hemicontinuous. Recall that if
is upper hemicontinuous, then 8k 2 A; the set (k) is nonempty and compact. Recall the
de…nition T V (k) = max u(c) + V (k 0 ) 8k 2 A:
c;k0 2 (k)
Consider any sequence fkn g such that kn 2 A 8n 2 N and fkn g ! k: Consider a corresponding
sequence fcn ; kn0 g such that (cn ; kn0 ) 2 (kn ) 8n 2 N: There exists such a sequence due to the
Extreme Value Theorem (compact (kn ) and continuous u(c) + V (k 0 )). Since
is upper
hemicontinuous, then there is a subsequence (without loss of generality the original sequence)
such that fcn ; kn0 g ! (c; k 0 ) 2 (k): Since the objective function u(c) + V (k 0 ) is continuous,
then the sequence
fT V (kn )g = u(cn ) + V (kn0 ) ! u(c) + V (k 0 ) = T V (k):
Thus, T V is continuous.
3
6. Recall that CB(A) is the set of continuous, bounded, and concave functions with compact
domain A (a complete metric space). Show that T : CB(A) ! CB(A) ; where the mapping
T is de…ned as before:
max u(c) + V (k 0 )
(T V )(k) =
:
(1)
c; k 0 c + k 0 Rk + w
Solution:
We begin by assuming that the value function V is continuous, bounded,
and concave. From Lecture 10, we know that the new value function T V is continuous and
bounded (citing Berge’s Theorem). We will now show that T V is also concave.
Consider any two capital levels k1 and k2 : If k1 is the initial capital, de…ne c1 and k1 0 as the
optimal solution of the optimization problem (1). By de…nition, (T V )(k1 ) = u(c1 ) + V (k1 0 ):
Similarly, if k2 is the initial capital, de…ne c2 and k2 0 as the optimal solution (c; k 0 ) of the
optimization problem (1). By de…nition, (T V )(k2 ) = u(c2 ) + V (k2 0 ): For any 2 [0; 1] ; the
convex combination of initial capital is k = k1 + (1
)k2 : Given the initial capital k ; the
0
0
0
choice (c ; k ) = (c1 ; k1 ) + (1
) (c2 ; k2 ) satis…es all constraints (c
0; 0 k 0
k; and
0
0
c +k
Rk + w). Thus, the choice (c ; k ) may be chosen by the consumer, so any optimal
solution (c ; k 0 ) given the initial capital k must satisfy:
(T V )(k ) = u(c ) + V (k 0 )
u(c ) + V (k 0 ):
Given that both u and V are concave, then
u(c ) + V (k 0 )
[ u(c1 ) + (1
u(c1 ) + V (k1 0 ) + (1
=
=
V (k1 0 ) + (1
) u(c2 )] +
(T V )(k1 ) + (1
)V (k2 0 )
) u(c2 ) + V (k2 0 )
)(T V )(k2 ):
In sum,
(T V )(k )
(T V )(k1 ) + (1
)(T V )(k2 );
…nishing the argument that T V is a concave function.
7. Assume that u is strictly concave, and prove that there exists a unique solution to
max u(c) + V (k 0 )
:
c; k 0 c + k 0 Rk + w
Solution:
From the previous question, we know that V is concave. Suppose, in order to
obtain a contradiction, that there exists two solutions to the optimization problem: (c1 ; k10 )
and (c2 ; k20 ) : If both are optimal solutions, then u(c1 ) + V (k10 ) = u(c2 ) + V (k20 ): Consider
the convex combination (c ; k 0 ) = (c1 ; k10 ) + (1
) (c2 ; k20 ) for any 2 (0; 1): This choice
0
satis…es all constraints (c
0; 0 k
k; and c + k 0
Rk + w) and provides a strictly
higher payo¤ as:
u (c ) >
V k
0
u (c1 ) + (1
k10
V
+ (1
) u (c2 )
) V k20 :
The strict inequality u(c ) + V (k 0 ) > u(c1 ) + V (k10 ) = u(c2 ) + V (k20 ) contradicts our
original supposition that (c1 ; k10 ) and (c2 ; k20 ) are optimal solutions.
4
8. Write down the …rst order conditions of the Bellman equation. Use them to argue that the
value function V is di¤erentiably strictly increasing.
Solution:
The …rst order condition with respect to consumption is:
Du(c)
= 0;
where
0 is the Lagrange multiplier of the budget constraint. Since u is di¤erentiably
strictly increasing, then Du(c) > 0 for any c and > 0: The …rst order condition with respect
to k 0 is:
+ DV (k 0 ) = 0:
We know that V is di¤erentiable from the class notes. Combining the …rst order conditions
yields:
Du(c) = DV (k 0 ):
Since u is di¤erentiably strictly increasing, then Du(c) > 0 for any c: Thus, DV (k 0 ) > 0;
meaning that V is di¤erentiably strictly increasing.
9. Recall that the policy function is de…ned as g : A ! A such that
k 0 ) + V (k 0 ):
g(k) = arg max u(Rk + w
k0 2A
Assume that u is strictly concave. Then g is a function. From Berge’s Theorem, g is continuous. Prove that g satis…es the following properties:
(a) g is continuously di¤erentiable (C 1 )
(b) g is strictly increasing (Dg(k) > 0 8k 2 A)
Hint: Use the Implicit Function Theorem. You may assume that V is twice continuously
di¤erentiable (C 2 ), a fact shown by Santos, Econometrica (1991).
Solution:
Consider the maximization problem in terms of two variables (k; k 0 ) :
k 0 ) + V (k 0 ):
max
u(Rk + w
0
k 2A
The …rst order condition is necessary and su¢ cient for an optimal solution k
problem:
Du(Rk + w k 0 ) + DV (k 0 ) = 0:
De…ne the function F : A
A ! R by
F k; k 0 =
Du(Rk + w
0
to the above
k 0 ) + DV (k 0 );
where the optimal solution k 0 satis…es F (k; k 0 ) = 0: F is C 1 (as both u and V are C 2 ). The
variable k 0 is an implicit function of k:
Claim: D2 F (k; k 0 ) 6= 0:
D2 F (k; k 0 ) = D2 u(Rk + w k 0 ) + D2 V (k 0 ): As u is strictly concave and V is concave,
then D2 u(Rk + w k 0 ) < 0 and D2 V (k 0 ) 0; implying that D2 F (k; k 0 ) < 0:
Applying the Implicit Function Theorem, there exists open sets around k and k 0 (call them
O(k) and O(k 0 ); respectively) such that the implicit function g : O(k) ! O(k 0 ) de…ned by
g(k) = k 0 is C 1 and
Dg(k) =
D2 F k; k
From above, D2 F (k; k 0 ) < 0: D1 F (k; k 0 ) =
(+)
( ) > 0:
5
0
1
D1 F k; k
0
R D2 u(Rk + w
:
k 0 ) > 0: Thus, Dg(k) =

Download Report