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
f262900@dac.unicamp.br
Claudia Sagastizábal
IMECC/UNICAMP, Campinas, São Paulo, Brazil
sagastiz@unicamp.br
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.