Abstract
We study sample approximations of chance constrained problems. In particular, we consider the sample average approximation (SAA) approach and discuss the convergence properties of the resulting problem. We discuss how one can use the SAA method to obtain good candidate solutions for chance constrained problems. Numerical experiments are performed to correctly tune the parameters involved in the SAA. In addition, we present a method for constructing statistical lower bounds for the optimal value of the considered problem and discuss how one should tune the underlying parameters. We apply the SAA to two chance constrained problems. The first is a linear portfolio selection problem with returns following a multivariate lognormal distribution. The second is a joint chance constrained version of a simple blending problem.
Similar content being viewed by others
References
Charnes, A., Cooper, W.W., Symmonds, G.H.: Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil. Manag. Sci. 4, 235–263 (1958)
Prékopa, A.: Stochastic Programming. Kluwer Academic, Dordrecht (1995)
Dupačová, J., Gaivoronski, A., Kos, Z., Szántai, T.: Stochastic programming in water management: a case study and a comparison of solution techniques. Eur. J. Oper. Res. 52, 28–44 (1991)
Henrion, R., Li, P., Möller, A., Steinbach, S.G., Wendt, M., Wozny, G.: Stochastic optimization for operating chemical processes under uncertainty. In: Grötschel, M., Krunke, S., Rambau, J. (eds.) Online Optimization of Large Scale Systems, pp. 457–478. Springer, Berlin (2001)
Henrion, R., Möller, A.: Optimization of a continuous distillation process under random inflow rate. Comput. Math. Appl. 45, 247–262 (2003)
Dentcheva, D., Prékopa, A., Ruszczyński, A.: Concavity and efficient points of discrete distributions in probabilistic programming. Math. Program. 89, 55–77 (2000)
Luedtke, J., Ahmed, S.: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19, 674–699 (2008)
Nemirovski, A., Shapiro, A.: Convex approximations of chance constrained programs. SIAM J. Optim. 17(4), 969–996 (2006)
Shapiro, A.: Monte Carlo sampling methods. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in OR & MS, vol. 10, pp. 353–425. North-Holland, Amsterdam (2003)
Atlason, J., Epelman, M.A., Henderson, S.G.: Optimizing call center staffing using simulation and analytic center cutting plane methods. Manag. Sci. 54, 295–309 (2008)
Luedtke, J., Ahmed, S.: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19, 674–699 (2008)
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)
Artstein, Z., Wets, R.J.-B.: Consistency of minimizers and the SLLN for stochastic programs. J. Convex Anal. 2, 1–17 (1996)
Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum observations. Ann. Math. Stat. 23, 493–507 (1952)
Markowitz, H.: Portfolio selection. J. Financ. 7, 77–97 (1952)
Wang, Y., Chen, Z., Zhang, K.: A chance-constrained portfolio selection problem under t-distribution. Asia Pac. J. Oper. Res. 24(4), 535–556 (2007)
Campi, M.C., Garatti, S.: The exact feasibility of randomized solutions of robust convex programs. Optimization online (www.optimization-online.org) (2007)
Calafiore, G., Campi, M.C.: The scenario approach to robust control design. IEEE Trans. Autom. Control. 51, 742–753 (2006)
Klein Haneveld, W.K., van der Vlerk, M.H.: Stochastic Programming (lecture notes) (2007)
Law, A., Kelton, W.D.: Simulation Modeling and Analysis. Industrial Engineering and Management Science Series. McGraw–Hill Science/Engineering/Math, New York (1999)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by P.M. Pardalos.
B.K. Pagnoncelli’s research was supported by CAPES and FUNENSEG.
S. Ahmed’s research was partly supported by the NSF Award DMI-0133943.
A. Shapiro’s research was partly supported by the NSF Award DMI-0619977.
Rights and permissions
About this article
Cite this article
Pagnoncelli, B.K., Ahmed, S. & Shapiro, A. Sample Average Approximation Method for Chance Constrained Programming: Theory and Applications. J Optim Theory Appl 142, 399–416 (2009). https://doi.org/10.1007/s10957-009-9523-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-009-9523-6