数学系 Seminar 第 2027 期
上海大学运筹与优化开放实验室国际科研合作平台系列报告
报告主题：随机对偶动态规划的复杂性（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
主办部门：上海大学运筹与优化开放实验室-国际科研合作平台、上海市运筹学会、上海大学理学院数学系
报告摘要：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.
欢迎教师、学生参加！
