DYNAMIC PROGRAMMING

“[Dynamic] also has a very interesting property as an adjective, and that is its impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. Its impossible. Thus, I thought dynamic programming was a good name. ”-Richard Bellman Most of our applications of optimal control involved choosing something as a function of time. Dynamic programming is another approach to solving optimization problems that involve time. Dynamic programming can be especially useful for problems that in-volve uncertainty. Dynamic programming has the advantage that it lets us focus on one period at a time, which can often be easier to think about than the whole sequence. Be-cause it only requires maximizing over a few variables at a time, dynamic programming can be a much more efficient way to calculate solutions. The computational advantage of dynamic programming is especially pronounced when some of the variables being max-imized over are discrete. 1. REFERENCES These notes are about dynamic programming. References from our text books are chap-ter 11 of Dixit (1990). Adda and Cooper (2003) is very nice and available online from UBC library. Stokey, Lucas Jr, and Prescott (1989) is the classic economics reference for dynamic programming, but is more advanced than what we will cover. Applied dynamic programming by Bellman and Dreyfus (1962) and Dynamic programming and the calculus of variations by Dreyfus (1965) provide a good introduction to the main idea of dynamic programming, and are especially useful for contrasting the dynamic pro-gramming and optimal control approaches. Dreyfus (2002) has some amusing anecdotes from Bellman about the initial development of dynamic programming. Bertsekas (1976) is the classic reference for dynamic programming with uncertainty. 1 DYNAMIC PROGRAMMIN