Stochastic Decomposition for Risk-Averse Two-Stage Stochastic Linear Programs

Two-stage risk-averse stochastic programming goes beyond the classical expected value framework and aims at controlling the variability of the cost associated with different out- comes based on a choice of a risk measure. In this paper, we study stochastic decomposition (SD) for solving large-scale risk-averse stochastic linear programs with deviation and quan- tile risk measures. Large-scale problems refer to instances involving too many outcomes to handle using a direct solver, requiring the use of sampling approaches. SD follows an internal sampling approach in which only one sample is randomly generated at each iteration of the algorithm and has been successful for the risk-neutral setting. We extend SD to the risk-averse setting and establish asymptotic convergence of the algorithm to an optimal solution if one exists. A salient feature of the SD algorithm is that the number of samples is not fixed a priori, which allows obtaining good candidate solutions using a relatively small number of samples. We derive two variations of the SD algorithm, one with a single cut (Single-Cut SD) to approximate both the expected recourse function and dispersion statistic, and the other with two separate cuts (Separate-Cut SD). We report on a computational study based on standard test instances to evaluate the empirical performance of the SD algorithms in the risk-averse setting. The study shows that both SD algorithms require a relatively small num- ber of scenarios to converge to an optimal solution. In addition, the comparative performance of the Single-Cut and Separate-Cut SD algorithms is problem-dependent.