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" [...]


  Payday Loans In Indiana. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.