RIEB Discussion Paper Series No.2019-24

RIEB Discussion Paper Series No.2019-24


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


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