In this short chapter we introduce one of the most popular and powerful methods to solve optimal control problems for deterministic and stochastic dynamic systems in discrete time. This method is known as Dynamic Programming (DP) and has been proposed in the fifties of the last century by the American mathematician Richard Bellman (Bellman (1957)) for the case of deterministic dynamics. The main feature of DP is the reduction of a computational problem of complexity order mn to n problems of complexity order m. If the resulting algorithm needs to be reduced further, then more sophisticated techniques must be employed. For a treatment of these methods, we may refer to Bertsekas (2005). Our presentation is organized as follows.
Section 3.1 presents the general setting of a discrete time optimization problem.
Section 3.2 states the problem for both deterministic and stochastic systems.
Section 3.3 introduces the Bellman principle of optimality.
Section 3.4 develops the DP algorithm for the case of deterministic systems.
The extension to stochastic systems is presented in Sect. 3.5.
Section 3.6 illustrates two major applications of DP in quantitative finance.
A final section concludes with comments on further references.
Files
Matlab file for pricing American options in the binomial model