Fast Bellman Iteration: An Application of Legendre-Fenchel Duality to Infinite-Horizon Dynamic Programming 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 DP2015-11, Discussion Paper Series from Research Institute for Economics & Business Administration, Kobe University

Abstract: We propose an algorithm, which we call "Fast Bellman Iteration" (FBI), to compute the value function of an infinite-horizon dynamic programming problem in discrete time. FBI is an extremely efficient linear-time 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.

Pages: 19 pages
Date: 2015-03
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/DP2015-11.pdf First version, 2015 (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:dp2015-11

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 ().