Abstract
Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criterion. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk objective, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various mean-risk objective functions in addressing risk in stochastic programming models. We prove that the classical mean-variance criterion leads to computational intractability even in the simplest stochastic programs. On the other hand, a number of alternative mean-risk functions are shown to be computationally tractable using slight variants of existing stochastic programming decomposition algorithms. We propose decomposition-based parametric cutting plane algorithms to generate mean-risk efficient frontiers for two particular classes of mean-risk objectives.
Similar content being viewed by others
References
Ahmed, S.: Mean-risk objectives in stochastic programming. Technical report, Georgia Institute of Technology, 2004. E-print available at http://www.optimization-online.org.
Birge, J.R., Louveaux, F.: Introduction to stochastic programming. Springer, New York, NY, 1997
Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Co., 1979
Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex analysis and minimization algorithms II. Springer-Verlag, Berlin Heidelberg, 1996
Lemaréchal, C., Nemirovski, A., Nesterov, Yu.: New variants of bundle methods. Math. Prog. 69, 111–148 (1995)
Linderoth, J., Wright, S.: Decomposition algorithms for stochastic programming on a computational grid. Comput. Optim. Appl. 24, 207–250 (2003)
Makhorin, A.: GNU Linear Progamming Kit, Reference Manual, Version 3.2.3. http://www.gnu.org/software/glpk/glpk.html, 2002
Markowitz, H.M.: Portfolio selection: efficient diversification of investments. John Wiley & Sons, 1959
Ogryczak, W., Ruszczyński, A.: On consistency of stochastic dominance and mean-semideviation models. Math. Prog. 89, 217–232 (2001)
Ogryczak, W., Ruszczyński, A.: Dual stochastic dominance and related mean-risk models. SIAM J. Optim. 13, 60–78 (2002)
Porter, R.B.: Semivariance and stochastic dominance. American Economic Review 64, 200–204 (1974)
Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-at-risk. J. Risk 2, 21–41 (2000)
Ruszczyński, A., Shapiro, A. (eds.): Stochastic programming. volume 10 of Handbooks in Operations Research and Management Science. North-Holland, 2003
Ruszczyński, A., Shapiro, A.: Optimization of convex risk functions. Submitted for publication. E-print available at http://www.optimization-online.org, 2004
Ruszczyński, A., Vanderbei, R.: Frontiers of stochastically nondominated portfolios. Econometrica 71, 1287–1297 (2004)
Schultz, R.: Stochastic programming with integer variables. Math. Prog. 97, 285–309 (2003)
Shapiro, A., Ahmed, S.: On a class of minimax stochastic programs. SIAM J. Optim. 14, 1237–1249 (2004)
Takriti, S., Ahmed, S.: On robust optimization of two-stage systems. Math. Prog. 99, 109–126 (2004)
Yitzhaki, S.: Stochastic dominance, mean variance, and Gini's mean difference. American Economic Review 72 (1), 178–185 (1982)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ahmed, S. Convexity and decomposition of mean-risk stochastic programs. Math. Program. 106, 433–446 (2006). https://doi.org/10.1007/s10107-005-0638-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-005-0638-8