Fast value iteration: an application of Legendre-Fenchel duality to a class of deterministic dynamic programming problems in discrete time* |
| |
Authors: | Ronaldo Carpio |
| |
Institution: | School of Business and Finance, University of International Business and Economics, Beijing, People's Republic of China |
| |
Abstract: | ABSTRACTWe 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 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. |
| |
Keywords: | Dynamic programming Legendre-Fenchel transform Bellman operator convex analysis |
|
|