CONTRACTION MAPPINGS IN THE THEORY UNDERLYING DYNAMIC PROGRAMMING,
Abstract
A formulation and analysis of a broad class of optimization problems including many, but not all, dynamic programming problems. The formulation generalizers those of several authors and provides further insight into the class of problems which satisfy Bellman's Principle of Optimality. Three widely shared properties of optimization problems are abstracted; they are called 'contraction,' 'monotonicity,' and 'N-stage contraction' properties. Analysis is conducted of those classes of problems satisfying the first property, the first two properties, and the last two properties. In each case, a fixed-point argument guarantees that a functional equation have a unique solution; in the latter two cases that solution is the optimal return function. Policies whose return functions attain or approximate the fixed point are shown to exist, and three techniques for determining such policies are presented. The techniques are successive approximations, mathematical programming, and a generalization of one of Howard's policy improvement routines. Certain issues concerning history-remembering decision procedures and stationary processes are settled. Examples are provided, and apparent integrability issues in some of them are circumvented. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1966
- Accession Number
- AD0634348
Entities
People
- Eric V. Denardo
Organizations
- RAND Corporation