Accession Number : AD0634348

Title :   CONTRACTION MAPPINGS IN THE THEORY UNDERLYING DYNAMIC PROGRAMMING,

Corporate Author : RAND CORP SANTA MONICA CALIF

Personal Author(s) : Denardo, Eric V.

Report Date : JUN 1966

Pagination or Media Count : 36

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)

Descriptors :   (*OPTIMIZATION, *DYNAMIC PROGRAMMING), (*MAPPING(TRANSFORMATIONS), DYNAMIC PROGRAMMING), DECISION THEORY, MODEL THEORY

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE