# Can a dynamic programming problem be transformed into a linear algebra problem?

Here is a simple standard economic problem:

Let Robin Crusoe have an endowment $w_0$ of lembas bread. She is immortal and discounts at a rate of $\beta$ per period. Each period (from $t=0$ on) she choose to consume some amount $c_t\in [0,w_t]$, and since lembas bread does not decay, $w_{t+1} = w_t - c_t$. Optimize Robin's utility $$\sum_{t=0}^\infty \beta^t u(c_t)$$ subject to the constraint $w_{t+1} + c_t = w_t$.

Here $u$ is a concave function, e.g., $u(c) = c^{\theta}$ or $u(c) = \log(c)$.

To solve this using dynamic programming, one uses Bellman's principle that each period, a choice will be made given optimal behavior in all future periods. Thus one obtains a series of value functions $v_t$ solving $$v_t(w_t) = \max_{w'\in [0,w_t]} u(w'-w_t) + \beta v_t(w').$$ This is to say, on the constraint set $\Omega_t = [0,w_t]$, $v_t$ is a stationary point of the maximization operator $$T_uv(b) = \max_{b'\in \Omega_t}u(b'-b) + \beta v(b'),$$ acting on (say) $L^\infty(\Omega_t)$.

This is not a linear operator, so tools from linear algebra cannot be brought to bear. I'm wondering if the problem can be "linearized" in the following sense:

Is there a linear operator $L_u$ acting on $L^\infty(\Omega_t)$ which "contains the same information as $T_u$" in the sense that a stable point of $T_u$ will either be an eigenvector of $L_u$ or will lie in the kernel of $L_u$?

I've played around with the idea that an integral operator $L$, say, $Lv(b) = \int U(b,b')v(b')db'$, might be able to capture this maximization problem, but I'm afraid I just don't yet have the intuition to see how this should play out. So I put the question to you.

-
Have you considered offering a bounty to get the attention to this question? I would like to chip in too. Thanks. –  triomphe Oct 14 '13 at 21:12
in the formulation, do you mean $w_{t+1}=w_t - c_t$? –  user76844 Oct 22 '13 at 18:54
@Eupraxis1981 Yes, thank you. –  Neal Oct 22 '13 at 20:33
Does Crusoe has only the initial endowment to consume, during her infinite life? –  Alecos Papadopoulos Oct 25 '13 at 22:27
Are you certain you want to maximize over the state variable? Utility comes from consumption, not from endowment. Why go roundabout? –  Alecos Papadopoulos Oct 25 '13 at 22:30

Select $c_t : u(c_t) = \beta u(w_t-c_t)\;,\; \sum\limits_{t=0}^{\infty} c_t = w_0$ That way, you eat in time t until the opportunity cost for eating the rest becomes negative relative to eating the rest it the next day.
Actually, one would want $u'(c_t) = \beta u'(w_t - c_t)$ so that you eat in time $t$ until the marginal opportunity cost of the rest becomes negative relative to eating the rest of it the next day. This is the beginning of a standard sequential approach to solving these problems. –  Neal Oct 22 '13 at 20:51