Dual-based methods for solving infinite-horizon nonstationary deterministic dynamic programs

• 成果类型: Article
• 署名作者: Ryan, Christopher Thomas; Smith, Robert L.
• 署名单位: University of British Columbia; University of Michigan System; University of Michigan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01478-1
• 发表日期: 2021
• 页码: 253-285
• 关键词: markov decision-processes; simplex algorithm; flow problems; approximations; optimality; EXISTENCE; time

摘要

We develop novel dual-ascent and primal-dual methods to solve infinite-horizon nonstationary deterministic dynamic programs. These methods are finitely implementable and converge in value to optimality. Moreover, the dual-ascent method produces a sequence of improving dual solutions that pointwise converge to an optimal dual solution, while the primal-dual algorithm provides a sequence of primal basic feasible solutions with value error bounds from optimality that converge to zero. Our dual-based methods work on a more general class of infinite network flow problems that include the shortest-path formulation of dynamic programs as a special case. To our knowledge, these are the first dual-based methods proposed in the literature to solve infinite-horizon nonstationary deterministic dynamic programs.