Dynamic Programming a method
for solving complex problems by breaking them down into simpler
subproblems. It is applicable to problems exhibiting the properties of
overlapping subproblems which are only slightly smaller. such as Dijkstra's algorithm for the shortest path problem Fibonacci sequence Tower of Hanoi puzzle simplifying a decision by breaking it down into a sequence of decision steps over time. V_{n}(y) is the value obtained in state y at the last time n. The values V_{i} at earlier times i = n −1, n − 2, ..., 2, 1 can be found by working backwards ExampleAssume a consumer who lives over the periods t = 0, 1, 2, ..., T and must decide how much to consume and how much to save in each period.
(which is the discounted utility value as described above) subject to k_{t+1} = A k^{a}_{t} - c_{t} ≥ 0 Written this way, the problem looks complicated, because it involves solving for all the choice variables c0, c1, c2, ..., c_{T} and k1, k2, k3, ..., k_{T+1} simultaneously. (Note that k0 is not a choice variable—the consumer's initial capital is taken as given.) Dynamic ProgrammingThe dynamic programming approach to solving this problem involves breaking it apart into a sequence of smaller decisions. To do so, we define a sequence of value functions V_{t}(k), for t = 0, 1, 2, ..., T, T+1 which represent the value of having any amount of capital k at each time t. Note that V_{T+1}(k) = 0 , that is, there is (by assumption) no utility from having capital after death. The value of any quantity of capital at any previous time can be calculated by backward induction using the Bellman equation (a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming). In this case the Bellman equation is: This problem is much simpler than the one we wrote down before, because it involves only two decision variables, ct, k_{t+1}. Find the optimal amount to consume at time can be dealt with as a back tracking problem, starting from back and knowing the relationships between current consumptions and the utilities gained and time. |