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
School of Business and Finance, University of International Business and Economics
Research Institute for Economics and Business Administration,
Rokkodai-cho, Nada-ku, Kobe