Journal Home Page

Cumulative Index

List of all Volumes

Complete Contents
of this Volume

Previous Article

Next Article

Journal of Convex Analysis 30 (2023), No. 2, 453--479
Copyright Heldermann Verlag 2023

A Bundle-Like Progressive Hedging Algorithm

Felipe Atenas
IMECC/UNICAMP, Campinas, São Paulo, Brazil

Claudia Sagastizábal
IMECC/UNICAMP, Campinas, São Paulo, Brazil

For convex multistage programming problems, we propose a variant for the Progressive Hedging algorithm inspired from bundle methods. Like in the original algorithm, iterates are generated by first solving separate problems for each scenario, and then performing a projective step to ensure non-anticipativity. An additional test checks the quality of the approximation, splitting iterates into two subsequences, akin to the dichotomy between bundle serious and null steps. The method is shown to converge in both cases, and the convergence rate is linear for the serious subsequence. Our bundle-like approach endows the Progressive Hedging algorithm with an implementable stopping test. Moreover, it is possible to vary the augmentation parameter along iterations without impairing convergence. Such enhancements with respect to the original Progressive Hedging algorithm are obtained at the expense of the solution of additional subproblems at each iteration, one per scenario.

Keywords: Bundle methods, progressive Hedging algorithm, projective descent schemes, Douglas-Rachford splitting.

MSC: 90C30, 90C33, 90C55, 65K05.

[ Fulltext-pdf  (315  KB)] for subscribers only.