An optimal one-way multigrid algorithm for discrete-time stochastic control
- 1 January 1991
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 36 (8) , 898-914
- https://doi.org/10.1109/9.133184
Abstract
We consider the numerical solution of discrete-time stationary infinite-horizon discounted stochastic control problems, for the case where the state space is continuous and the problem is to be solved approximately, within a desired accuracy. After a discussion of problem discretization, we introduce a multigrid version of the successive approximation algorithm that proceeds "one way" from coarse to fine grids, and analyze its computational requirements as a function of the desired accuracy and of the discount factor. We also study the effects of a certain mixing (ergodicity) condition on the algorithm's performance. We show that the one-way multigrid algorithm improves upon the complexity of its single-grid variant and is, in a certain sense, optimal.This publication has 18 references indexed in Scilit:
- The complexity of dynamic programmingJournal of Complexity, 1989
- Adaptive Markov Control ProcessesPublished by Springer Nature ,1989
- Multi-grid methods for Hamilton-Jacobi-Bellman equationsNumerische Mathematik, 1986
- Approximation and bounds in discrete event dynamic programmingIEEE Transactions on Automatic Control, 1986
- Multi-Grid Methods and ApplicationsPublished by Springer Nature ,1985
- Multi-Grid Algorithms with Applications to Elliptic Boundary Value ProblemsSIAM Journal on Numerical Analysis, 1984
- Approximations of Dynamic Programs, IIMathematics of Operations Research, 1979
- Contraction mappings underlying undiscounted Markov decision problemsJournal of Mathematical Analysis and Applications, 1978
- Approximations of Dynamic Programs, IMathematics of Operations Research, 1978
- Contraction Mappings in the Theory Underlying Dynamic ProgrammingSIAM Review, 1967