Stochastic Decomposition Algorithms for Risk-Averse Multistage Stochastic Linear Programs and Applications
Abstract
Mean-risk stochastic linear programming provides a framework for controlling cost variability in problems involving sequential decision making under uncertainty. It goes beyond the classical expected value framework by including risk measures in the objective function and aims at controlling cost variability in the solution. This allows for modeling risk averseness in variety of applications such as long-term financial planning, scheduling of power systems, supply chain management and portfolio optimization. In this dissertation, we derive stochastic decomposition algorithms for solving mean-risk twosatge stochastic linear programs (MR-SLP) and mean-risk multistage stochastic linear programs (MR-MSLP) with deviation and quantile risk measures. Stochastic decomposition(SD) is a type of internal sampling method and at every iteration of algorithm only one linear problem is solved for approximating the recourse function. A salient feature of the SD algorithm is that the number of samples is not fixed a priori, which allows to obtain good candidate solutions early in the procedure. We also report on a computational study to evaluate the empirical performance of the SD algorithms for MR-SLP and MR-MSLP with expected excess(EE), quantile deviation(QDEV) and conditional value-at-risk(CVaR) as risk measures. The goal of the study was to analyze for a given instance how SD algorithm performs across different levels of risk, investigate the effect of different risk measures and understand when it is appropriate to use the risk-averse approach. For MR-SLP, the SD algorithm is implemented and applied to standard test instances and it shows that the risk measure QDEV has more impact on expected cost and the cost associated with extreme scenarios compared to the impact of CVaR and EE. We also observed that for higher target values, the risk measure EE becomes effective only for a relatively small number of scenarios and has little to no-effect on the optimal solution for small values of the risk trade-off factor.
The computational study also demonstrates that under risk aversion the rate of convergence of SD algorithm remains consistent as opposed to sample average approximation approach. For the multistage case, the SD algorithm is applied to an instance of long-term hydrothermal scheduling (LTHS) and it shows that the risk trade-off factor has a significant impact on the solution and the risk measure conditional value-at-risk exhibits a better control over the extreme scenarios at lower values of risk trade-off factor. The study also shows that the risk-neutral approach is still appropriate for the LTHS problem.
Subject
Multistage Stochastic Linear ProgrammingMean-Risk
Two-Stage Stochastic Linear Programming
Expected Excess
Conditional Value at Risk
Quantile Deviation
Stochastic Decomposition
Long Term Hydro-Thermal Scheduling
Citation
Parab, Prasad (2019). Stochastic Decomposition Algorithms for Risk-Averse Multistage Stochastic Linear Programs and Applications. Doctoral dissertation, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /189150.
Related items
Showing items related by title, author, creator and subject.
-
Goel, Piyush (2010-10-12)A Web-server farm is a specialized facility designed specifically for housing Web servers catering to one or more Internet facing Web sites. In this dissertation, stochastic dynamic programming technique is used to obtain ...
-
Gill, Robert Chope (Texas A&M University, 2002)The recent resurgence of interest in ethanol production has prompted the Texas State Legislature to investigate the feasibility of ethanol production in Texas. The reasons for the increased interest in ethanol production ...
-
Paternostro, Christopher Lee (Texas A&M University, 2001)In a new attempt to solve the fundamental fluid equations, this thesis details an original model with the ultimate goal of aiding commercial oil spill simulations. This model follows the approach employed by lattice gas ...