Editing Dynamic programming (section)

==== Example from economics: Ramsey's problem of optimal saving ====
{{See also|Ramsey–Cass–Koopmans model}}
In [[economics]], the objective is generally to maximize (rather than minimize) some dynamic [[social welfare function]]. In Ramsey's problem, this function relates amounts of consumption to levels of [[utility]]. Loosely speaking, the planner faces the trade-off between contemporaneous consumption and future consumption (via investment in [[Physical capital|capital stock]] that is used in production), known as [[intertemporal choice]]. Future consumption is discounted at a constant rate <math>\beta \in (0,1)</math>. A discrete approximation to the transition equation of capital is given by
:<math>k_{t+1} = \hat{g} \left( k_{t}, c_{t} \right) = f(k_{t}) - c_{t}</math>
where <math>c</math> is consumption, <math>k</math> is capital, and <math>f</math> is a [[production function]] satisfying the [[Inada conditions]]. An initial capital stock <math>k_{0} > 0</math> is assumed.

Let <math>c_t</math> be consumption in period {{mvar|t}}, and assume consumption yields [[utility]] <math>u(c_t)=\ln(c_t)</math> as long as the consumer lives. Assume the consumer is impatient, so that he [[discounting|discounts]] future utility by a factor {{mvar|b}} each period, where <math>0<b<1</math>. Let <math>k_t</math> be [[capital (economics)|capital]] in period {{mvar|t}}. Assume initial capital is a given amount <math>k_0>0</math>, and suppose that this period's capital and consumption determine next period's capital as <math>k_{t+1}=Ak^a_t - c_t</math>, where {{mvar|A}} is a positive constant and <math>0<a<1</math>. Assume capital cannot be negative. Then the consumer's decision problem can be written as follows:

: <math>\max \sum_{t=0}^T b^t \ln(c_t)</math> subject to <math>k_{t+1}=Ak^a_t - c_t \geq 0</math> for all <math>t=0,1,2,\ldots,T</math>

Written this way, the problem looks complicated, because it involves solving for all the choice variables <math>c_0, c_1, c_2, \ldots , c_T</math>. (The capital <math>k_0</math> is not a choice variable—the consumer's initial capital is taken as given.)

The dynamic programming approach to solve this problem involves breaking it apart into a sequence of smaller decisions. To do so, we define a sequence of ''value functions'' <math>V_t(k)</math>, for <math>t=0,1,2,\ldots,T,T+1</math> which represent the value of having any amount of capital {{mvar|k}} at each time {{mvar|t}}. There is (by assumption) no utility from having capital after death, <math>V_{T+1}(k)=0</math>.

The value of any quantity of capital at any previous time can be calculated by [[backward induction]] using the [[Bellman equation]]. In this problem, for each <math>t=0,1,2,\ldots,T</math>, the Bellman equation is

: <math>V_t(k_t) \, = \, \max \left( \ln(c_t) + b V_{t+1}(k_{t+1}) \right)</math> subject to <math>k_{t+1}=Ak^a_t - c_t \geq 0</math>

This problem is much simpler than the one we wrote down before, because it involves only two decision variables, <math>c_t</math> and <math>k_{t+1}</math>. Intuitively, instead of choosing his whole lifetime plan at birth, the consumer can take things one step at a time. At time {{mvar|t}}, his current capital <math>k_t</math> is given, and he only needs to choose current consumption <math>c_t</math> and saving <math>k_{t+1}</math>.

To actually solve this problem, we work backwards. For simplicity, the current level of capital is denoted as {{mvar|k}}. <math>V_{T+1}(k)</math> is already known, so using the Bellman equation once we can calculate <math>V_T(k)</math>, and so on until we get to <math>V_0(k)</math>, which is the ''value'' of the initial decision problem for the whole lifetime. In other words, once we know <math>V_{T-j+1}(k)</math>, we can calculate <math>V_{T-j}(k)</math>, which is the maximum of <math>\ln(c_{T-j}) + b V_{T-j+1}(Ak^a-c_{T-j})</math>, where <math>c_{T-j}</math> is the choice variable and <math>Ak^a-c_{T-j} \ge 0</math>.

Working backwards, it can be shown that the value function at time <math>t=T-j</math> is

: <math>V_{T-j}(k) \, = \, a \sum_{i=0}^j a^ib^i \ln k + v_{T-j}</math>

where each <math>v_{T-j}</math> is a constant, and the optimal amount to consume at time <math>t=T-j</math> is

: <math>c_{T-j}(k) \, = \, \frac{1}{\sum_{i=0}^j a^ib^i} Ak^a</math>

which can be simplified to

: <math>\begin{align}
c_{T}(k) & = Ak^a\\
c_{T-1}(k) & = \frac{Ak^a}{1+ab}\\
c_{T-2}(k) & = \frac{Ak^a}{1+ab+a^2b^2}\\
&\dots\\
c_2(k) & = \frac{Ak^a}{1+ab+a^2b^2+\ldots+a^{T-2}b^{T-2}}\\
c_1(k) & = \frac{Ak^a}{1+ab+a^2b^2+\ldots+a^{T-2}b^{T-2}+a^{T-1}b^{T-1}}\\
c_0(k) & = \frac{Ak^a}{1+ab+a^2b^2+\ldots+a^{T-2}b^{T-2}+a^{T-1}b^{T-1}+a^Tb^T}
\end{align}</math>

We see that it is optimal to consume a larger fraction of current wealth as one gets older, finally consuming all remaining wealth in period {{mvar|T}}, the last period of life.