Some functional equations in the theory of dynamic programming. I. Functions of points and point transformations
Richard Bellman · Transactions of the American Mathematical Society · 1955
Introduction.The purpose of this paper is to establish a number of basic results concerning the solutions of a large and important class of functional equations which arise in the theory of dynamic programming.Here we shall be concerned only with the analytic aspects of these equations, and refer the reader to a number of sources, [2; 3; 6; 7; 9; 11 ], where the underlying processes are discussed in connection with various applications.We shall in this paper consider only functions of points and point transformations.In a subsequent one we shall treat more general equations involving functionals and operators.Let p denote a vector representing a point in an iV-dimensional region D, and T(p, q), for all vectors q in some prescribed Af-dimensional set 5, which may consist of a finite number of points, an enumerably infinite set, or which may be a continuum, denote a transformed point lying in D for each p in D. Let f(p) denote a scalar function of p and g(p, q) and h(p, q) be two scalar functions of p and q.A representative example of functional equations we shall discuss below is(1) f(P) = Sup [g(p, q) + h(p, q)f(T(p, q))].e This is an analytic equivalent of the "principle of optimality" for multi-stage decision processes; cf.[2; 11].Apart from their interest in connection with multi-stage decision proc-