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 Dimensionality [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 performance 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 noise in continuous time, since this type of noise is separable in time just as the optimization steps in the principle of optimality. Thus, the stochastic perturbations treated here will be of the continuous, but non-smooth Gaussian type or the discontinuous, randomly distributed Poisson type. Due to its continuity property, Gaussian noise is suitable for modeling background randomness. In contrast, Poisson noise is suitable for modeling the catastrophic, rare random events. For some stochastic models, random shocks to the system are more important than the continuous perturbations, although the continuous changes are more easy to treat.
Unlike deterministic applications of dynamical programming, the use of general stochastic noise in continuous time makes it difficult to use different formulations other than the partial differential equation of dynamic programming or Bellman equation. For deterministic problems in continuous time, there is the option of applying the maximum principle to formulate a dual set of forward and adjoint backward ordinary differential equations coupled with information on the critical points of the Hamiltonian, so the method of solution is quite different from the dynamic programming approach. Other methods will be discussed later.
Numerical partial differential equation (PDE) methods have been modified for the nonstandard characteristics of the PDE of stochastic dynamic programming. In order to manage the large computational requirements, high performance supercomputers have been employed [17, 116, 117, 118]. For instance, the problems with up to 5 states and 32 mesh points per state have been successfully solved using finite difference methods [116, 117, 58, 118] on both Cray and Connection Machines. Larger problems are possible with recent hardware and software advances.
The finite element method has computational and memory advantages. This method requires a smaller number of nodes than the corresponding finite difference method of similar accuracy. We have shown [20] that the finite element method not only helps to alleviate Bellman’s Curse of Dimensionality in dynamical programming computations by permitting the solution of higher dimension problems, but also saving supercomputer storage requirements.
Download
PDF Ebook Techniques in Computational Stochastic Dynamic Programming
