# A Review on the Performance of Linear and Mixed Integer Two-Stage Stochastic Programming Software
## 5 Scenario Decomposition Methods
### Progressive Hedging (PH) Algorithm  
The progressive hedging (PH) algorithm [9] is a popular approximation for solving multi-stage stochastic programs. Although it was initially proposed for convex stochastic problems, it has been successfully applied as a heuristic to solve mixed-integer stochastic programs [52; 53]. To find a solution of problem (2), PH aggregates a new set of variables \(\hat{x}\) (also known as a first-stage policy) that replaces the NACs (2b). Then, it solves the reformulated program (20) using a specialized variant of the alternating direction method of multipliers (ADMM) [54,55]:  
\[\min_{x_{\omega},y_{\omega},x}\ \ TC=\ \sum_{\omega\in\Omega}(c^{T}x_{\omega}+d_{ \omega}^{T}y_{\omega})\] (20a) s.t. \[(x_{\omega},y_{\omega})\in G_{\omega},\ \ x_{\omega}=\hat{x},\ \ \forall\omega\in\Omega,\ \ \hat{x}\in X \tag{20b}\]  
Related to dual decomposition, PH relaxes the non-anticipativity restrictions on the first stage. The augmented Lagrangian relaxation \(L^{\rho}\) of constraints \(x_{\omega}=\hat{x},\forall\omega\in\Omega\) yields a lower bound \(D(\lambda)\) of the original deterministic formulation (20). The best lower bound is estimated by solving the following problem:  
\[TC\geq\max_{\lambda}\{D(\lambda)\ \ \text{s.t.}\ \ \sum_{\omega\in\Omega}\tau_{ \omega}\lambda_{\omega}=0\}\] (21a) where \[D(\lambda)=\min_{x,x,y}\ \ L^{\rho}(x,\hat{x},y,\lambda)\ \ \text{s.t.}\ \ (x_{\omega},y_{\omega})\in G_{ \omega}\ \ \forall\omega\in\Omega,\ \ \hat{x}\in X \tag{21b}\] \[L^{\rho}(x,y,\hat{x},\lambda)=\sum_{\omega\in\Omega}\tau_{\omega}L_{\omega}(x_ {\omega},y_{\omega},\hat{x},\lambda_{\omega})\] (21c) \[L_{\omega}(x_{\omega},y_{\omega},\hat{x},\lambda_{\omega})=c^{T}x_{\omega}+d_{ \omega}^{T}y_{\omega}+\lambda^{T}(x_{\omega}-\hat{x})+\rho/2\|x-\hat{x}\|_{2}^ {2}\] (21d) and \[\rho>0\] is a penalty parameter. Constraint \[\sum_{\omega\in\Omega}\tau_{\omega}\lambda_{\omega}=0\] is required to make \[L^{\rho}\] bounded from below. To mitigate the computational difficulties of minimizing the augmented Lagrangian dual function (21b), PH decomposes the problem by scenarios. To achieve the complete separability of subproblems, [PERSON] and [PERSON] [9] proposed to fix the first-stage policy temporarily, and repeatedly solve the program (22) to update the multipliers and the value of \[\hat{x}\] : \[(x_{\omega},y_{\omega})\in G_{\omega},\ \ x_{\omega}=\hat{x},\ \ \forall\omega\in\Omega,\ \ \hat{x}\in X \tag{20b}\]0  
Algorithm 4 summarizes the procedure to solve the dual problem (21). ```
1 set \(k\longleftarrow 0\), \(\lambda^{0}=0\)
2 SOLVE \((x_{\omega}^{1},y_{\omega}^{2})=\arg\min_{x_{\omega},y_{\omega}}\{c^{T}x_{ \omega}+d_{\omega}^{T}y_{\omega}\ \ \ s.t\ \ \ (x_{\omega},y_{\omega})\in G_{\omega}\}\) for all \(\omega\) in \(\Omega\)
3 repeat
4 set \(k\longleftarrow k+1\)
5 set \(\hat{x}^{k}\longleftarrow\sum_{\omega\in\Omega}\tau_{\omega}x_{\omega}^{k}\)
6 set \(\lambda_{\omega}^{k}\longleftarrow\lambda_{\omega}^{k-1}+\rho(x_{\omega}^{k-1 }-\hat{x}^{k-1})\)
7 SOLVE (22) for every \(\omega\in\Omega\) to compute \(x_{\omega}^{k+1}\)
8 until\(k>k_{max}\) or \(\sqrt{\sum_{\omega\in\Omega}\tau_{\omega}(x_{\omega}^{k+1}-\hat{x})^{2}}<\epsilon\); return\(\hat{x}^{k},x_{\omega}^{k+1},y_{\omega}^{k+1}\)
```  
**Algorithm 4**Two-stage progressive hedging algorithm  
The termination of the algorithm is achieved when the first-stage policy is non-anticipative. In the case of convex instances, \(\hat{x}^{k\longrightarrow\infty}\) is equivalent to the optimal solution of the deterministic formulation (2), and the convergence is guaranteed. These conditions do not hold for mixed-integer programs; however, a high-quality solution and upper bound can be computed from a non-convergent value of \(\{\hat{x}^{k}\}_{k=k_{max}}\) and \(TC_{\rho}(\hat{x}^{k})_{k=k_{max}}\), respectively [52]. Recent investigations have focused on the improvement and acceleration of PH.