A study of progressive hedging for stochastic integer programming
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2023-12
Major/Subject
Mcode
Degree programme
Language
en
Pages
46
989-1034
989-1034
Series
Computational Optimization and Applications, Volume 86, issue 3
Abstract
Motivated by recent literature demonstrating the surprising effectiveness of the heuristic application of progressive hedging (PH) to stochastic mixed-integer programming (SMIP) problems, we provide theoretical support for the inclusion of integer variables, bridging the gap between theory and practice. We provide greater insight into the following observed phenomena of PH as applied to SMIP where optimal or at least feasible convergence is observed. We provide an analysis of a modified PH algorithm from a different viewpoint, drawing on the interleaving of (split) proximal-point methods (including PH), Gauss–Seidel methods, and the utilisation of variational analysis tools. Through this analysis, we show that under mild conditions, convergence to a feasible solution should be expected. In terms of convergence analysis, we provide two main contributions. First, we contribute insight into the convergence of proximal-point-like methods in the presence of integer variables via the introduction of the notion of persistent local minima. Secondly, we contribute an enhanced Gauss–Seidel convergence analysis that accommodates the variation of the objective function under mild assumptions. We provide a practical implementation of a modified PH and demonstrate its convergent behaviour with computational experiments in line with the provided analysis.Description
Funding Information: This work was supported by the Australian Research Council (ARC) Grant No. (ARC DP140100985). Publisher Copyright: © 2023, The Author(s).
Keywords
Gauss–Seidel methods, Progressive hedging, Stochastic mixed integer programming, Variational analysis
Other note
Citation
Christiansen, J, Dandurand, B, Eberhard, A & Oliveira, F 2023, ' A study of progressive hedging for stochastic integer programming ', Computational Optimization and Applications, vol. 86, no. 3, pp. 989-1034 . https://doi.org/10.1007/s10589-023-00532-w