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

Ronaldo Carpio and Takashi Kamihigashi
Additional contact information
Ronaldo Carpio: School of Business and Finance, University of International Business and Economics

No DP2019-24, Discussion Paper Series from Research Institute for Economics & Business Administration, Kobe University

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 efficient 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 (search for similar items in EconPapers)
Pages: 17 pages
Date: 2019-12
New Economics Papers: this item is included in nep-cmp and nep-dge
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.rieb.kobe-u.ac.jp/academic/ra/dp/English/DP2019-24.pdf First version, 2019 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kob:dpaper:dp2019-24

Access Statistics for this paper

More papers in Discussion Paper Series from Research Institute for Economics & Business Administration, Kobe University 2-1 Rokkodai, Nada, Kobe 657-8501 JAPAN. Contact information at EDIRC.
Bibliographic data for series maintained by Office of Promoting Research Collaboration, Research Institute for Economics & Business Administration, Kobe University ().