Numerical Analysis and Approximation Methods in Discrete-Time Dynamic Programming

摘要

The report is concerned with computational techniques in dynamic programming and particularly with the use of approximation methods in representing the dynamic programming benefit function. To analyze the effects of approximations, error propagation formulae are developed which show the effect on the whole computation of an error introduced at each step. Sufficient conditions are then proved for convergence of approximate dynamic programs to the true solution. Based on these error analysis results a 'state reduction' algorithm for deterministic dynamic programs is proposed. In this algorithm a series of approximate dynamic programs solved on successively smaller state spaces. An error estimate on each approximation is used to choose the state space for the next. The algorithm has the property that, if it converges, it converges to the correct solution. Several sets of conditions are proved that guarantee convergence if the initial approximation is sufficiently accurate. Some numerical results are given for two simple problems. A detailed investigation is made of the application of the state reduction algorithm to large linear programs with special structures. (Author)