Understanding Progressive Hedging Algorithm in Operations Research Seminar

Explore the Progressive Hedging algorithm discussed in the Graduate Seminar on Operations Research. Topics include general framework, resource allocation examples, and handling non-convexity in decision-making. Dive into scenario decomposition and scenario-specific decision-making for well-hedged solutions.

• Progressive Hedging Algorithm
• Operations Research
• Graduate Seminar
• Scenario Decomposition
• Decision-making

mohamed Follow

Uploaded on Jul 23, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Progressive hedging Miio Taarna 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 1

2. Outline 1. Introduction 2. General framework 3. Progressive hedging algorithm 4. Resource allocation example 5. Conclusions 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 2

3. Introduction 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 3

4. Recap [20,0.4] [22,0.3] Multi-stage stochastic programming (S1-S2) Time progression Outcomes can be defined as a scenario tree (S4) Some defined outcome With a probability [24,0.6] [27,0.5] [28,0.7] [30,0.5] 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 4

5. Motivation Various methods have been discussed (S9-11) Linear vs. non-linear How to handle non- convexity? Multi-stage parallelization? 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 5

6. General framework 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 6

7. Generalized problem Watson and Woodruff (2011) Decision maker minimizing costs Study scenarios for similarities Get a well hedged solution 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 7

8. Scenario decomposition Pr(1) + Pr(2) + Pr(3) + Pr(4) + Pr(5) + Pr(6) Pr(1) + Pr(2) Pr(3) + Pr(4) Pr(5) + Pr(6) Pr(3) Pr(4) Pr(6) Pr(1) Pr(5) Pr(2) Eckstein (2021) 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 8

9. Scenario decomposition Pr(1) Pr(2) Pr(3) Pr(4) Pr(5) Pr(6) Eckstein (2021) 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 9

10. Updated problem Watson and Woodruff (2011) Weigh scenario specific decisions Implicit non-anticipativity constraints 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 10

11. Scenario decomposition Pr(1) Pr(2) Pr(3) Pr(4) Pr(5) Pr(6) Eckstein (2021) 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 11

12. Scenario decomposition Pr(1) Pr(2) Pr(5) Pr(3) Pr(4) Pr(6) Eckstein (2021) 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 12

13. Lagrangian In dual ascent, the Lagrangian is used Boyd With the following dual ascent updates 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 13

14. Augmented Lagrangian More robust than Lagrangian in base dual ascent Boyd Augment leads to the following dual ascent updates 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 14

15. Progressive hedging algorithm 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 15

16. Basis of the algorithm Solve for each scenario after decomposition Get weighted sum of scenarios Calculate the price of each scenario Iterate until difference between scenario specific and weighted solutions below threshold 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 16

17. Progressive hedging 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 17

18. Useful properties Converges on convex sets Linearly when x is continuous Modifiable via penalty parameter Low penalty (closer to zero) leads to faster progress in primal and conversely for dual Handles multi-stage problems cleanly Works as a good heuristic for non-convex and integer problems Rockafellar and Wets (1991) Rockafellar and Wets (1991) 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 18

19. Resource allocation example 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 19

20. Resource allocation Consider a flow network with arcs between nodes For each scenario, there is a quantity that must be shipped between nodes Flow defined by continuous variables Flow availability defined by binary variables Solve with CPLEX 10.1 for 2 day baseline Compare to progressive hedging performance 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 20

21. Resource allocation 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 21

22. Results 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 22

23. Results 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 23

24. Conclusions 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 24

25. Conclusions We can decompose a scenario tree horizontally as a list of scenario sequences where some scenario nodes share decision values 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 25

26. Conclusions We can modify the dual ascent approach Boyd And iterate over decisions (primal) and scenario prices (dual) 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 26

27. Conclusions Related algorithms Alternating direction method of multipliers (ADMM) Proximal point algorithm Starting to catch on More interest in multi-stage instances Larger availability of highly parallel computing Options for using the algorithm CPLEX PySP StochasticPrograms.jl 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 27

28. References 1. Rockafellar and Wets (1991) - Scenarios and Policy Aggregation in Optimization Under Uncertainty, http://sites.math.washington.edu/~rtr/papers/rtr120-ScenariosAggregation.pdf 2. Boyd et al. (2011) Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, http://datascienceassn.org/sites/default/files/Distributed%20Optimization%20and%20Statistical %20Learning%20via%20the%20Alternating%20Direction%20Method%20of%20Multipliers.pdf 3. Watson and Woodruff (2011) - Progressive hedging innovations for a class of stochastic mixed- integer resource allocation problems, https://link.springer.com/content/pdf/10.1007/s10287- 010-0125-4.pdf 4. Boyd Alternating Direction Method of Multipliers, https://web.stanford.edu/class/ee364b/lectures/admm_slides.pdf 5. Eckstein (2018) - The ADMM, Progressive Hedging and Operator Splitting, https://www.youtube.com/watch?v=T-JUf23khZU 6. Eckstein (2021) (Asynchoronous) Projective Hedging for Convex Stochastic Programing, https://www.youtube.com/watch?v=QShCamUQIHc 28.10.2022 MS-E2191 - Graduate Seminar on Operations Research 28