# 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.

Recall that we already talked about root finding.

Let's think about this problem a bit more. The expression

\(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:

- Solve the last period: \(G(k', T) = 0\). This is trivial.
- For each \(t\) (backwards):
- Make a capital grid for period \(t\).
- Find \(k' = G(k, t)\) for each grid point.
- Interpolate \(G(k, t)\) to make a continuous function.

- 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.

`solve_last_period`

is basically trivial.`solve_one_period`

just iterates over grid points and then calls ...`solve_one_point`

which- checks for corner solutions
- runs
`find_zero`

on \(D(k', k)\)

- Finally, we need to check the solution to make sure it satisfies
- budget constraint and
- Euler equation

### Exercise: write this code.¶

- My solution is in the
`PihVfi890`

repo. - Don't forget the tests!