Accession Number : AD0731769

Title :   Numerical Analysis and Approximation Methods in Discrete-Time Dynamic Programming.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE OPERATIONS RESEARCH CENTER

Personal Author(s) : Wilde,Norman William Gerald

Report Date : JUN 1971

Pagination or Media Count : 156

Abstract : 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)

Descriptors :   (*DYNAMIC PROGRAMMING, APPROXIMATION(MATHEMATICS)), NUMERICAL ANALYSIS, DECISION THEORY, STOCHASTIC PROCESSES, MINIMAX TECHNIQUE, CONVERGENCE, SET THEORY, ALGORITHMS, OPTIMIZATION, THESES

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE