A Nonconvex Regularization Scheme for the Stochastic Dual Dynamic Programming Algorithm
提出一种非凸正则化方案，使用折叠凹惩罚函数改进随机对偶动态规划算法，提升大规模多阶段随机规划问题的求解质量和收敛速度，并给出全局最优性保证和收敛性证明。
We propose a new nonconvex regularization scheme to improve the performance of the stochastic dual dynamic programming (SDDP) algorithm for solving large-scale multistage stochastic programs. Specifically, we use a class of nonconvex regularization functions, namely folded concave penalty functions, to improve solution quality and the convergence rate of the SDDP procedure. We develop a strategy based on mixed-integer programming to guarantee global optimality of the nonconvex regularization problem. Moreover, we establish provable convergence guarantees for our customized SDDP algorithm. The benefits of our regularization scheme are demonstrated by solving large-scale instances of two multistage stochastic optimization problems. History: Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0255 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0255 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .