Stochastic decomposition for risk-averse two-stage stochastic linear programs

Prasad Parab (), Lewis Ntaimo () and Bernardo Pagnoncelli ()
Additional contact information
Prasad Parab: Texas A&M University
Lewis Ntaimo: Texas A&M University
Bernardo Pagnoncelli: Université Côte d’Azur

Journal of Global Optimization, 2025, vol. 91, issue 1, No 3, 59-93

Abstract: Abstract 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 outcomes 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 quantile 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 number 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.

Keywords: Stochastic decomposition; Sampling; Mean-risk; Deviation measures; Quantile measures (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-024-01432-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:91:y:2025:i:1:d:10.1007_s10898-024-01432-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-024-01432-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().