A study of progressive hedging for stochastic integer programming

Jeffrey Christiansen (), Brian Dandurand (), Andrew Eberhard () and Fabricio Oliveira ()
Additional contact information
Jeffrey Christiansen: RMIT University
Brian Dandurand: RMIT University
Andrew Eberhard: RMIT University
Fabricio Oliveira: Aalto University

Computational Optimization and Applications, 2023, vol. 86, issue 3, No 8, 989-1034

Abstract: 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.

Keywords: Stochastic mixed integer programming; Progressive hedging; Variational analysis; Gauss–Seidel methods; 68Q25; 68R10; 68U05 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-023-00532-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:86:y:2023:i:3:d:10.1007_s10589-023-00532-w

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-023-00532-w

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().