# Permanent Income Model 4: Value Function Iteration¶

Now we solve the model by backward induction.

This is not efficient in this case, but gets us started on methods for the more general Huggett model.

## The math¶

Bellman equation:

$$V(k,t)=\max_{k'} U(w+rk-k') + \beta V(k',t+1)$$

with first order condition

$$U'(w+rk-k')=\beta V_{k}(k',t+1)$$

and envelope condition

$$V_{k}(k,t) = r U'(w + rk - k')$$

## Value Function Iteration¶

Start at $$t = T$$ with $$V(k,T) = U(w+rk)$$.

Set up a grid for $$k$$.

For each $$k$$ on the grid:

• maximize $$U(w+rk-k') + \beta V(k',t+1)$$
• by searching over $$k'$$
• this gives $$k'=G(k,t)$$
• compute $$V(k,t) = U(w+rk-G(k,t)) + \beta V(G(k,t), t+1)$$

Problem: We need to evaluate $$V(k',t+1)$$ off the grid.

Solution: Interpolation (below).

This is inefficient

• it involves a numerical maximization for each $$k$$ grid point
• it is much easier (numerically) to find a root than to maximize a function

Therefore, we switch to finding roots of the Euler equation instead.

## Approximate $$V_{k}(k,t)$$¶

Start at $$t=T$$ with $$V_{k}(k,T)=U'(w+rk-k')$$.

Set up a grid for $$k$$.

For each $$k$$ on the grid:

• Search for the root of $$U'(w+rk-k')-\beta V_{k}(k',t+1)$$
• Compute the decision rule $$k' = G(k,t)$$
• Compute $$V_{k}(k,t) = r U'(w + rk - G(k,t))$$

Problem: We have $$V_{k}$$ on the grid, but for the root finding we need $$V_{k}$$ off the grid.

Solution: Construct a function that approximates $$V_{k}$$ based on the grid points that we have computed.

Problem: $$V_{k}$$ is highly nonlinear, so it is hard to approximate.

Solution:

• Restate the FOC as $$w+rk-k'=U'^{-1}(\beta V_{k}(k',t+1))$$.
• Approximate the RHS of this expression.
• Find the root of the corresponding deviation: $$k'=G(k,t)$$.
• Use this to compute $$V_{k}(k,t)$$ on the grid.

This is a viable algorithm, but we will implement something different.

## Policy Function Iteration¶

We don't really care about value functions per se ($$V$$ or $$V_{k}$$).

We care about decision rules $$k'=G(k,t)$$.

So we approximate them directly.

Start at $$t=T$$ with $$G(k,T) = 0$$.

Set up a grid for $$k$$.

For each $$k$$ on the grid:

• find the root of the Euler equation $$U'(w+rk-k') - \beta R U'(w'+rk'-G(k', t+1))$$
• but better (not as non-linear): $$w+rk-k' - U'^{-1}(\beta R U'(w'+rk'-G(k', t+1)))$$
• this gives $$k'=G(k,t)$$ on the $$k$$ grid.

Again, we need to interpolate the policy function between grid points.

$$w+rk-k' - U'^{-1}(\beta R U'(w'+rk'-G(k', t+1)))$$

can be thought of as $$D(k',k)$$. We are looking for $$D(k',k) = 0$$. The solution is $$G(k', t)$$.

Let's start from the "inside" of the problem. Suppose we have $$D(k', k)$$ on the grid, our first task is to make this a continuous function.

This is done with interpolation. One approach that we used before: each time we need to get a value $$D(k', k)$$, we call an interpolation function.

But this is tedious and inelegant. The better approach is to construct a continuous function that represents $$D(k', k)$$.

One package that does this is Interpolations.jl. QuantEcon contains a nice description that we will use here.

## Making a package¶

Before we write the code, we should ensure that UtilityFunctions is nicely reusable as a package.

Here are the instructions.

Once this is all done, we will set up a separate package for the policy function iteration code. Follow the same directions, but label your package PihVfi890 (permanent income hypothesis model via value function iteration).

Note that you can simply reuse the template that you generated for the UtilityFunctions890 package. Go back to the Econ890 directory and just type t("PihVfi890"). You just created a package in 10 seconds.

We need to add UtilityFunctions890 as a dependency for our new package. But it's not registered.

Solution: pkg> dev ../UtilityFunctions890. Take a look at Project.toml to see what we just did.

This is why packages are so useful. We can now reuse UtilityFunctions890 in all future code that we write.

These packages all now live in my github repo.

## Writing the solution code¶

This looks complicated. So how do we make it tractable?

Structured programming and top down design to the rescue.

The trick is to simply write out the steps that we want to perform without worrying about how to do each:

1. Solve the last period: $$G(k', T) = 0$$. This is trivial.
2. For each $$t$$ (backwards):
1. Make a capital grid for period $$t$$.
2. Find $$k' = G(k, t)$$ for each grid point.
3. Interpolate $$G(k, t)$$ to make a continuous function.
3. When all is done: check the solution.

That's surprisingly it. It translates fairly directly into code.

Now write this out in code and you have solve() in PihVfi890.jl.

Next, we fill in details.

1. solve_last_period is basically trivial.
2. solve_one_period just iterates over grid points and then calls ...
3. solve_one_point which
1. checks for corner solutions
2. runs find_zero on $$D(k', k)$$
4. Finally, we need to check the solution to make sure it satisfies
1. budget constraint and
2. Euler equation

### Exercise: write this code.¶

• My solution is in the PihVfi890 repo.
• Don't forget the tests!