Infinite-horizon deterministic dynamic programming in discrete time: a monotone convergence principle and a penalty method. (2nd October 2016)

• Record Type: Journal Article
• Authors: Kamihigashi, Takashi; Yao, Masayuki
• Is Part Of: Optimization. Volume 65:Number 10(2016)
• Page Start: 1899
• Page End: 1908
• Publication Date: 2016-10-02
• Subjects: Dynamic programming -- Bellman operator -- fixed point -- value iteration -- penalty method; 90C39 -- 47N10; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2016.1193737
• Languages: English
• ISSNs: 0233-1934

Abstract

Abstract : We consider infinite-horizon deterministic dynamic programming problems in discrete time. We show that the value function of such a problem is always a fixed point of a modified version of the Bellman operator. We also show that value iteration converges increasingly to the value function if the initial function is dominated by the value function, is mapped upward by the modified Bellman operator and satisfies a transversality-like condition. These results require no assumption except for the general framework of infinite-horizon deterministic dynamic programming. As an application, we show that the value function can be approximated by computing the value function of an unconstrained version of the problem with the constraint replaced by a penalty function.