Randomized Progressive Hedging methods for Multi-stage Stochastic Programming

Gilles Bareilles (1) , Yassine Laguel (1) , Dmitry Grishchenko (1, 2) , Franck Iutzeler (1) , Jérôme Malick (1)

1 DAO - Données, Apprentissage et Optimisation
2 AMA - Analyse de données, Modélisation et Apprentissage automatique [Grenoble]

Progressive Hedging is a popular decomposition algorithm for solving multi-stage stochastic optimization problems. A computational bottleneck of this algorithm is that all scenario subproblems have to be solved at each iteration. In this paper, we introduce randomized versions of the Progressive Hedging algorithm able to produce new iterates as soon as a single scenario subproblem is solved. Building on the relation between Progressive Hedging and monotone operators, we leverage recent results on randomized fixed point methods to derive and analyze the proposed methods. Finally, we release the corresponding code as an easy-to-use Julia toolbox and report computational experiments showing the practical interest of randomized algorithms, notably in a parallel context. Throughout the paper, we pay a special attention to presentation, stressing main ideas, avoiding extra-technicalities, in order to make the randomized methods accessible to a broad audience in the Operations Research community.

Mots clés: Stochastic programming; Progressive hedging; Randomized methods; Parallel computing

Domaines: Calcul parallèle, distribué et partagé [cs.DC]; Optimisation et contrôle [math.OC]

Gilles Bareilles, Yassine Laguel, Dmitry Grishchenko, Franck Iutzeler, Jérôme Malick. Randomized Progressive Hedging methods for Multi-stage Stochastic Programming. Annals of Operations Research, 2020, 295, pp.535-560. ⟨10.1007/s10479-020-03811-5⟩. ⟨hal-02946615⟩