Fast Bellman Iteration: An Application of Legendre-Fenchel Duality to Deterministic 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 DP2016-26, 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 a deterministic infinite-horizon dynamic programming problem in discrete time. FBI 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 (search for similar items in EconPapers)
Pages: 15 pages
Date: 2016-07
New Economics Papers: this item is included in 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/DP2016-26.pdf First version, 2016 (application/pdf)

Related works:
Working Paper: Fast Bellman Iteration: An Application of Legendre-Fenchel Duality to Deterministic Dynamic Programming in Discrete Time (2016)
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:dp2016-26

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