Fast Bellman Iteration: An Application of Legendre-Fenchel Duality to a Class of Deterministic Dynamic Programming Problems 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.


Dynamic programming, Legendre-Fenchel transform, Bellman operator, Convex analysis


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