报告主题：随机对偶动态规划的复杂性（Complexity of Stochastic Dual Dynamic Programming）

报 告 人：Guanghui Lan 教授（Georgia Institute of Technology）

报告时间：2020年10月24日（周六） 9:00

参会方式：腾讯会议

会议ID：137 528 345

会议密码：924924

https://meeting.tencent.com/s/ZlKAvT568vvR

主办部门：8188威尼斯娱人城运筹与优化开放实验室-国际科研合作平台、上海市运筹学会、8188威尼斯娱人城理学院数学系

报告摘要：Stochastic dual dynamic programming (SDDP) is a cutting plane type algorithm for multi-stage stochastic optimization developed more than 30 years ago. In spite of its popularity in practice, there does not exist any performance guarantees on the convergence speed of this method. In this talk we first provide a brief introduction to SDDP and its applications, e.g., in optimal control and portfolio optimization. We focus on establishing the number of iterations (iteration complexity) required by SDDP for solving general multi-stage stochastic optimization problems under the standard stage-wise independence assumption. A few novel mathematical notions and tools, including the saturation of search points, are introduced to achieve this goal. Our results indicate that the complexity of SDDP mildly increases with respect to the number of stages especially for discounted problems. Therefore, they are efficient for strategic decision making which involves a large number of stages, but with a relatively smaller number of decision variables in each stage. Without explicit discretization on the state and action spaces, these methods appear to be pertinent to the related reinforcement learning areas.

欢迎教师、学生参加！