Complexity of stochastic dual dynamic programming
Complexity of stochastic dual dynamic programming
复制标题
随机对偶动态规划的复杂性
DOI：
10.1007/s10107-020-01567-1
复制
发表时间：
2020
影响因子：
2.7
通讯作者：
Lan, Guanghui
中科院分区：
文献类型：
--
作者：
Lan, Guanghui
随机对偶动态规划是一种多阶段随机优化的割平面型算法，产生于30多年前。尽管它在实践中很受欢迎，但并没有对这种方法的收敛速度进行分析。在本文中，我们首先建立迭代次数，即，迭代的复杂性，所需的一个基本的双动态规划方法解决单场景多阶段优化问题，通过引入新的数学工具，包括饱和的搜索点。然后，我们完善这些基本工具，并建立迭代复杂性的探索性对偶动态规划方法提出本文和经典的随机对偶动态规划方法解决更一般的多阶段随机优化问题的标准阶段明智的独立性假设下。我们的研究结果表明，这些方法的复杂性温和的stagesT的数量增加，实际上线性依赖于折扣问题的T。因此，他们是有效的战略决策，涉及大量的阶段，但在每个阶段的决策变量相对较少。在没有明确离散化状态和动作空间的情况下，这些方法也可能与相关的强化学习和随机控制领域有关。
Stochastic dual dynamic programming is a cutting plane type algorithm for multi-stage stochastic optimization originated about 30 years ago. In spite of its popularity in practice, there does not exist any analysis on the convergence rates of this method. In this paper, we first establish the number of iterations, i.e., iteration complexity, required by a basic dual dynamic programming method for solving single-scenario multi-stage optimization problems, by introducing novel mathematical tools including the saturation of search points. We then refine these basic tools and establish the iteration complexity for an explorative dual dynamic programing method proposed herein and the classic stochastic dual dynamic programming method for solving more general multi-stage stochastic optimization problems under the standard stage-wise independence assumption. Our results indicate that the complexity of these methods mildly increases with the number of stagesT, in fact linearly dependent onTfor discounted problems. Therefore, they are efficient for strategic decision making which involves a large number of stages, but with a relatively small number of decision variables in each stage. Without explicitly discretizing the state and action spaces, these methods might also be pertinent to the related reinforcement learning and stochastic control areas.
登录
查看更多内容
ReSa：一种求解多级随机线性规划的方法
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
M. Hindsberger
通讯作者：
M. Hindsberger
MIDAS：混合整数动态逼近方案
影响因子：
2.7
作者：
A. Philpott;F. Wahid;Frédéric Bonnans
通讯作者：
Frédéric Bonnans
DOI：
10.1287/moor.16.3.650
发表时间：
1991-08
期刊：
Math. Oper. Res.
影响因子：
--
作者：
J. Higle;S. Sen
通讯作者：
J. Higle;S. Sen
影响因子：
1.9
作者：
Karsten Linowsky;A. Philpott
通讯作者：
Karsten Linowsky;A. Philpott
影响因子：
2.7
作者：
Jikai Zou;Shabbir Ahmed;X. Sun
通讯作者：
Jikai Zou;Shabbir Ahmed;X. Sun