Friday, 11:30 - 11:55 h, Room: MA 141


Jean-Paul Watson
Asynchronous progressive hedging

Coauthors: Roger Jb Wets, David L. Woodruff


Progressive Hedging (PH) is a scenario-based decomposition strategy for solving multi-stage stochastic programs. An attractive feature of PH is the ease with which it can be parallelized, by assigning sub-problems to each of many available processors; sub-problems may be linear programs, mixed-integer linear programs, or non-linear programs. The PH algorithm as stated parallelizes synchronously, in that all scenario sub-problems are solved before averages and sub-gradients are computed. However, for large-scale parallelization, such barrier synchronization leads to poor parallel efficiency, especially as sub-problem solve time variability increases. To mitigate this issue, we introduce the Asynchronous Progressive Hedging (APH) algorithm, where updates are done without waiting for all scenario sub-problem solves to complete. APH is critical on parallel computing architectures that are inherently heterogeneous and unreliable, or when so many compute nodes are employed that at least one of them is likely to fail during execution. We show that key convergence properties of PH hold in APH, and report computational experiences on mixed-integer linear and non-linear stochastic programs.


Talk 3 of the invited session Fri.1.MA 141
"Progressive hedging: Innovations and applications" [...]
Cluster 22
"Stochastic optimization" [...]


  Illinois Loans Online should not be obtained by people who do not have the capacity to repay the lenders. Since its introduction in the market buying Buy Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.