Conditions for the discovery of solution horizons |
| |
Authors: | James C. Bean Robert L. Smith |
| |
Affiliation: | (1) Department of Industrial and Operations Engineering, The University of Michigan, IOE Building, 1205 Beal Avenue, 48109 Ann Arbor, MI, USA |
| |
Abstract: | We present necessary and sufficient conditions for discrete infinite horizon optimization problems with unique solutions to be solvable. These problems can be equivalently viewed as the task of finding a shortest path in an infinite directed network. We provide general forward algorithms with stopping rules for their solution. The key condition required is that of weak reachability, which roughly requires that for any sequence of nodes or states, it must be possible from optimal states to reach states close in cost to states along this sequence. Moreover the costs to reach these states must converge to zero. Applications are considered in optimal search, undiscounted Markov decision processes, and deterministic infinite horizon optimization.This work was supported in part by NSF Grant ECS-8700836 to The University of Michigan. |
| |
Keywords: | Dynamic programming deterministic and Markov infinite state: infinite stage problems programming infinite dimensional: infinite horizon optimization shortest paths infinite networks |
本文献已被 SpringerLink 等数据库收录! |
|