MIDAS: A mixed integer dynamic approximation scheme

• 成果类型: Article
• 署名作者: Philpott, A. B.; Wahid, F.; Bonnans, J. F.
• 署名单位: University of Auckland; Inria
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01368-1
• 发表日期: 2020
• 页码: 19-50
• 关键词: Decomposition methods; CONVERGENCE

摘要

Mixed integer dynamic approximation scheme (MIDAS) is a new sampling-based algorithm for solving finite-horizon stochastic dynamic programs with monotonic Bellman functions. MIDAS approximates these value functions using step functions, leading to stage problems that are mixed integer programs. We provide a general description ofMIDAS, and prove its almost-sure convergence to a 2T e-optimal policy for problems with T stages when the Bellman functions are known to be monotonic, and the sampling process satisfies standard assumptions.