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 method’s convergence guarantees are deterministic and do not require randomization, in contrast to some other proposed asynchronous variations of progressive hedging. We describe a distributed implementation within the mpi-sppy system and present computational experiments on up to a million scenarios and using as many as 2,400 processor cores in an HPC (high-performance computing) environment. These experiments evaluate the performance of the method when operating in a “block asynchronous” manner, meaning that it alternates between non-overlapping decomposition and coordination phases, with only a subset of the subproblems being re-solved during each decomposition phase. Our experiments show that this tactic can make significantly more efficient use of computational resources than the original form of progressive hedging.
Article