»ã±¨Ö÷Ì⣺Ëæ»ú¶Ôż¶¯Ì¬¹æ»®µÄ¸´ÔÓÐÔ£¨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

Ö÷°ì²¿ÃÅ£ºÐ±¦GGÔ˳ïÓëÓÅ»¯Ê¢¿ª³¢ÊÔÊÒ-¹ú¼Ê¿ÆÑкÏ×÷ƽ̨¡¢ÉϺ£ÊÐÔ˳ïѧ»á¡¢Ð±¦GGÀíѧԺÊýѧϵ

»ã±¨ÌáÒª£º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.

Ó­½ÓÀÏʦ¡¢Ñ§Éú²ÎÓ룡