An Optimal Approximate Dynamic Programming Algorithm for the Lagged Asset Acquisition Problem

• 成果类型: Article
• 署名作者: Nascimento, Juliana M.; Powell, Warren B.
• 署名单位: Princeton University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1080.0360
• 发表日期: 2009
• 页码: 210-237
• 关键词: linear-programs; stochastic-approximation; optimization; management

摘要

We consider a multistage asset acquisition problem where assets are purchased now, at a price that varies randomly over time, to be used to satisfy a random demand at a particular point in time in the future. We provide a rare proof of convergence for an approximate dynamic programming algorithm using pure exploitation, where the states we visit depend on the decisions produced by solving the approximate problem. The resulting algorithm does not require knowing the probability distribution of prices or demands, nor does it require any assumptions about its functional form. The algorithm and its proof rely on the fact that the true value function is a family of piecewise linear concave functions.