Fast Value 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 Value Iteration" (FVI), to compute the value function of a deterministic infinite-horizon dynamic programming problem in discrete time. FVI is an ecient algorithm applicable to a class of multidimen- sional 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 guaran- teed 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