Stochastic Lipschitz dynamic programming

• 成果类型: Article
• 署名作者: Ahmed, Shabbir; Cabral, Filipe Goulart; Paulo da Costa, Bernardo Freitas
• 署名单位: University System of Georgia; Georgia Institute of Technology; Universidade Federal do Rio de Janeiro
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01569-z
• 发表日期: 2022
• 页码: 755-793
• 关键词: scale unit commitment; decomposition methods; global optimization; CONVERGENCE; algorithm

摘要

We propose a new algorithm for solving multistage stochastic mixed integer linear programming (MILP) problems with complete continuous recourse. In a similar way to cutting plane methods, we construct nonlinear Lipschitz cuts to build lower approximations for the non-convex cost-to-go functions. An example of such a class of cuts are those derived using Augmented Lagrangian Duality for MILPs. The family of Lipschitz cuts we use is MILP representable, so that the introduction of these cuts does not change the class of the original stochastic optimization problem. We illustrate the application of this algorithm on two case studies, comparing our approach with the convex relaxation of the problems, for which we can apply SDDP, and for a discretized approximation, applying SDDiP.