Numerical maximization¶

In the Bellman equation we maximize over \((C,K')\). By substituting the aggregate resource constraint we can phrase this as a maximization over one choice variable

\[\begin{split}V(K,Z) &= \max_{K'} \left\{ u\left( f(K,Z) - K' \right) + \beta \mathbb E V(K',Z') \right\}.\end{split}\]

Optimization is a large field of numerical analysis, but in these notes we will consider just one method that is easy to understand and fairly robust called “golden section search”. Suppose we have a function \(F(x)\) and we want to maximize it on the interval \([\underline{x},\bar x]\). We start by evaluating the function at four points labeled \(A\), \(B\), \(C\), and \(D\) in the following diagram.

To start with we would set \(A = \underline{x}\) and \(D = \bar x\). We then observe that \(F(C)>F(B)\) so we use the following reasoning to discard the interval \([A,B]\) from containing the maximizer: if \(F(x)\) is concave then the derivative is weakly decreasing and if the true maximizer \(x^*\) were in \([A,B]\) then the function goes down from \(x^*\) to B and then up from B to C, which contradicts the supposition that \(f\) is concave. You could use this algorithm if \(f\) is not concave but then there are no guarantees that it will work.

Once we eliminate the interval \([A,B]\) we repeat the same steps on the interval \([B,D]\) that is smaller than our original interval \([A,D]\). So point \(B\) will become the new \(A\). The clever part of the algorithm is that we put the points \(B\) and \(C\) in just the right places so that now \(C\) becomes the new \(B\). This means we don’t need to re-evaluate the function at our new points \(A\) or \(B\). We now introduce a new point \(C\), evaluate the function there and repeat as shown in the next diagram.

In the next iteration we find \(F(B)>F(C)\) so now we discard \([C,D]\), \(C\) becomes the new \(D\), and \(B\) becomes the new \(C\).

As you can see in the diagrams, the region under consideration is shrinking towards the true maximizer. If we repeat this procedure many times over we will have \([A,D]\) tightly bracketing \(x^*\).

Finally, how do we choose the points \(B\) and \(C\)? We are going to impose some symmetry on the choice so the interval \([A,B]\) is the same length as \([C,D]\). This reduces the problem to choosing one number \(p \in (0,1)\) as shown in the following figure.

We want to choose \(p\) so that when we eliminate \([A,B]\) point \(C\) becomes the new point \(B\) so we need the ratio of \(BC\) relative to \(BD\) to be the same as \(AB\) relative to \(AD\). To accomplish this we need

\[\frac{2p-1}{p} = 1-p.\]

This equation reduces to a quadratic equation with one root \(p = (-1 + \sqrt{5})/2\). As the other root implies \(p<0\) we disregard it.

Why is the method called “golden section search”? Because \(1/p\) is the golden ratio.