
Accession Number : AD0731769
Title : Numerical Analysis and Approximation Methods in DiscreteTime 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