Techniques in Computational Stochastic Dynamic Programming.pdfVIP

1 Techniques in Computational Stochastic Dynamic Programming Floyd B. Hanson
University of Illinois at Chicago Chicago, Illinois 60607-7045 I. INTRODUCTION When Bellman introduced dynamic programming in his original monograph [8], computers were not as powerful as current personal computers. Hence, his description of the extreme computational demands as the Curse of Dimen- sionality [9] would not have had the super and massively parallel processors of today in mind. However, massive and super computers can not overcome the Curse of Dimensionality alone, but parallel and vector computation can permit the solution of higher dimension than was previously possible and thus permit more realistic dynamic programming applications. Today such large problems are called Grand and National Challenge problems [45, 46] in high perfor- mance computing. Today’s availability of high performance vector supercomputers and massively parallel processors have made it possible to compute optimal policies and values of control systems for much larger dimensions than was possible earlier. Advances in algorithms have also paid a large role. In this chapter, the focus will be on the stochastic dynamic programming in continuous time, yet related problems and methods will be discussed where appropriate. The primary stochastic noise considered here is Markov