Randomized progressive hedging methods for multi-stage stochastic programming
From MaRDI portal
Publication:828821
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.
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
- scientific article; zbMATH DE number 2121076 (Why is no real title available?)
- A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization
- A simplified form of block-iterative operator splitting and an asynchronous algorithm resembling the multi-block alternating direction method of multipliers
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- Convex analysis and monotone operator theory in Hilbert spaces
- Decomposition methods in stochastic programming
- JuMP: a modeling language for mathematical optimization
- Julia: a fresh approach to numerical computing
- Lectures on Stochastic Programming
- Multi-stage stochastic optimization applied to energy planning
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
- Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems
- Scenarios and Policy Aggregation in Optimization Under Uncertainty
- Solving stochastic programming problems with risk measures by progressive hedging
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping
- Superquantile/CVaR risk measures: second-order theory
Cited in
(15)- A randomized progressive hedging algorithm for stochastic variational inequality
- Progressive hedging as a meta-heuristic applied to stochastic lot-sizing
- A progressive hedging method for the multi-path travelling salesman problem with stochastic travel times
- scientific article; zbMATH DE number 7733428 (Why is no real title available?)
- A new interpretation of the progressive hedging algorithm for multistage stochastic minimization problems
- Scenario decomposable subgradient projection method for two-stage stochastic programming with convex risk measures
- Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging
- PySP: modeling and solving stochastic programs in Python
- A progressive hedging based branch-and-bound algorithm for mixed-integer stochastic programs
- Risk-averse stochastic programming and distributionally robust optimization via operator splitting
- Solving stochastic programming problems with risk measures by progressive hedging
- Ambulance location routing problem considering all sources of uncertainty: progressive estimating algorithm
- A parallelized variable fixing process for solving multistage stochastic programs with progressive hedging
- On the implementation of a log-barrier progressive hedging method for multistage stochastic programs
- Distributed Learning with Sparse Communications by Identification
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)
