Projective Hedging Algorithms for Multistage Stochastic Programming, Supporting Distributed and Asynchronous Implementation

• 成果类型: Article
• 署名作者: Eckstein, Jonathan; Watson, Jean-Paul; Woodruff, David L.
• 署名单位: Rutgers University System; Rutgers University New Brunswick; Rutgers University Newark; United States Department of Energy (DOE); Lawrence Livermore National Laboratory; University of California System; University of California Davis
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0228
• 发表日期: 2025
• 关键词: splitting methods; bounds; SUM

摘要

We propose a decomposition algorithm for multistage stochastic programming that resembles the progressive hedging method of Rockafellar and Wets but is provably capable of several forms of asynchronous operation. We derive the method from a class of projective operator splitting methods fairly recently proposed by Combettes and Eckstein, significantly expanding the known applications of those methods. Our derivation assures convergence for convex problems whose feasible set is compact, subject to some standard regularity conditions and a mild fairness condition on subproblem selection. The meth-od's convergence guarantees are deterministic and do not require randomization, in con-trast to other proposed asynchronous variations of progressive hedging. Computational experiments described in an online appendix show the method to outperform progressive hedging on large-scale problems in a highly parallel computing environment.