Randomized progressive hedging methods for multi-stage stochastic programming
From MaRDI portal
Publication:828821
DOI10.1007/S10479-020-03811-5zbMATH Open1467.90024arXiv2009.12186OpenAlexW3090269071MaRDI QIDQ828821FDOQ828821
Authors: Gilles Bareilles, Yassine Laguel, Dmitry Grishchenko, Franck Iutzeler, Jérôme Malick 
Publication date: 5 May 2021
Published in: Annals of Operations Research (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/2009.12186
Recommendations
- Solving stochastic programming problems with risk measures by progressive hedging
- A new interpretation of the progressive hedging algorithm for multistage stochastic minimization problems
- Structural properties of the progressive hedging algorithm
- Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems
- scientific article; zbMATH DE number 7733428
Cites Work
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- Julia: a fresh approach to numerical computing
- JuMP: a modeling language for mathematical optimization
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Convex analysis and monotone operator theory in Hilbert spaces
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- Title not available (Why is that?)
- Multi-stage stochastic optimization applied to energy planning
- Lectures on Stochastic Programming
- Decomposition methods in stochastic programming
- Scenarios and Policy Aggregation in Optimization Under Uncertainty
- Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping
- Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems
- Superquantile/CVaR risk measures: second-order theory
- Solving stochastic programming problems with risk measures by progressive hedging
- A simplified form of block-iterative operator splitting and an asynchronous algorithm resembling the multi-block alternating direction method of multipliers
- A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization
Cited In (14)
- A progressive hedging method for the multi-path travelling salesman problem with stochastic travel times
- Distributed Learning with Sparse Communications by Identification
- PySP: modeling and solving stochastic programs in Python
- On the implementation of a log-barrier progressive hedging method for multistage stochastic programs
- Solving stochastic programming problems with risk measures by progressive hedging
- A progressive hedging based branch-and-bound algorithm for mixed-integer stochastic programs
- A new interpretation of the progressive hedging algorithm for multistage stochastic minimization problems
- Ambulance location routing problem considering all sources of uncertainty: progressive estimating algorithm
- Title not available (Why is that?)
- Risk-averse stochastic programming and distributionally robust optimization via operator splitting
- Progressive hedging as a meta-heuristic applied to stochastic lot-sizing
- Scenario decomposable subgradient projection method for two-stage stochastic programming with convex risk measures
- A parallelized variable fixing process for solving multistage stochastic programs with progressive hedging
- Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging
Uses Software
This page was built for publication: Randomized progressive hedging methods for multi-stage stochastic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q828821)
