RIEB Discussion Paper Series No.2019-24

Title

Fast Value Iteration: An Application of Legendre-Fenchel Duality to a Class of Deterministic Dynamic Programming Problems in Discrete Time

Abstract

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.

Keywords

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

Inquiries

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

Takashi KAMIHIGASHI
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