Fast Bellman Iteration: An Application of Legendre-Fenchel Duality to Deterministic Dynamic Programming in Discrete Time


We propose an algorithm, which we call "Fast Bellman Iteration" (FBI), to compute the value function of a deterministic infinite-horizon dynamic programming problem in discrete time. FBI is an efficient algorithm applicable to a class of multidimensional dynamic programming problems with concave return (or convex cost) functions and linear constraints. In this algorithm, a sequence of functions is generated starting from the zero function by repeatedly applying a simple algebraic rule involving the Legendre-Fenchel transform of the return function. The resulting sequence is guaranteed to converge, and the Legendre-Fenchel transform of the limiting function coincides with the value function.


Ronaldo CARPIO
School of Business and Finance, University of International Business and Economics

Research Institute for Economics and Business Administration,
Kobe University
Rokkodai-cho, Nada-ku, Kobe
657-8501 Japan
Phone: +81-78-803-7036
FAX: +81-78-803-7059