Reduced complexity dynamic programming based on policy iteration
type: Item
instance of: scholarly article
title: Reduced complexity dynamic programming based on policy iteration
zbMATH Open document ID: 0774.49019
DOI: 10.1016/0022-247X(92)90007-Z
author: David S. Bayard
published in: Journal of Mathematical Analysis and Applications
publication date: 1993-04-01T00:00:00Z
review text: Optimal nonlinear control problems are considered. The problems are solved by using the dynamic programming approach of Bellman. Computational complexity of the usual dynamic programming formalism increases exponentially with the dimension of state. An iterative procedure for solving the dynamic programming equations is proposed. Instead of backward dynamic programming a forward method is introduced. The required computation is independent of the dimension but grows exponentially with the horizon length. A suboptimal method of reduced complexity is defined. The method is illustrated by numerical examples (optimization over a continuous variable, the traveling salesman problem and an \(N\)-Queens problem).
Mathematics Subject Classification ID: 49L20
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 150641
zbMATH Keywords: optimal control
zbMATH Keywords: dynamic programming
zbMATH Keywords: forward method
MaRDI profile type: Publication
cites work: Q4001603
cites work: Transient analysis of an adaptive system for optimization of design parameters
cites work: A forward method for optimal stochastic nonlinear and adaptive control
cites work: Implicit dual control for general stochastic systems
cites work: Q3241581
cites work: Dynamic Programming Treatment of the Travelling Salesman Problem
cites work: Q3292915
cites work: Q3795523
cites work: Generalized Simulated Annealing for Function Optimization
cites work: DESIGN OF EXPERIMENTS IN NON-LINEAR SITUATIONS
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: Q5628775
cites work: Q5585020
cites work: A new approach to differential dynamic programming for discrete time systems
cites work: Robust experiment design via stochastic approximation
cites work: D-Optimality for Regression Designs: A Review
cites work: The stagewise Kuhn-Tucker condition and differential dynamic programming
cites work: Computational aspects of discrete-time optimal control
Recommended article: An Efficient Policy Iteration Algorithm for Dynamic Programming Equations
Recommended article: Policy iteration for bounded-parameter POMDPs
Recommended article: Policy iteration type algorithms for recurrent state Markov decision processes
Recommended article: Q5405224
Recommended article: Improved bound on the worst case complexity of policy iteration
Recommended article: On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes
Recommended article: Policy set iteration for Markov decision processes
Recommended article: Improved and Generalized Upper Bounds on the Complexity of Policy Iteration
Recommended article: Q3755250
description: scientific article; zbMATH DE number 150641