×

On feasibility of sample average approximation solutions. (English) Zbl 1448.90064

Summary: When there are infinitely many scenarios, the current studies of two-stage stochastic programming problems rely on the relatively complete recourse assumption. However, such an assumption can be unrealistic for many real-world problems. This motivates us to study general stochastic programming problems where the sample average approximation (SAA) solutions are not necessarily feasible. When the problems are convex and the true solutions lie in the interior of feasible solutions, we show that the portion of infeasible SAA solutions decays exponentially as the sample size increases. We also study functions with a chain-constrained domain and show that the portion of SAA solutions having a low degree of feasibility decays exponentially as the sample size increases. This result is then extended to the multistage stochastic programming.

MSC:

90C15 Stochastic programming
03E75 Applications of set theory

Software:

SUTIL
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] G. Barbarosoǧlu and Y. Arda, A two-stage stochastic programming framework for transportation planning in disaster response, J. Oper. Res. Soc., 55 (2004), pp. 43-53. · Zbl 1095.90586
[2] G. Calafiore and M. Campi, Uncertain convex programs: Randomized solutions and confidence levels, Math. Program., 102 (2005), pp. 25-46. · Zbl 1177.90317
[3] M. C. Campi and S. Garatti, The exact feasibility of randomized solutions of uncertain convex programs, SIAM J. Optim., 19 (2008), pp. 1211-1230, https://doi.org/10.1137/07069821X. · Zbl 1180.90235
[4] M. C. Campi and S. Garatti, Introduction to the Scenario Approach, SIAM, Philadelphia, 2018, https://doi.org/10.1137/1.9781611975444. · Zbl 1426.90151
[5] X. Chen, A. Shapiro, and H. Sun, Convergence analysis of sample average approximation of two-stage stochastic generalized equations, SIAM J. Optim., 29 (2019), pp. 135-161, https://doi.org/10.1137/17M1162822. · Zbl 1410.90134
[6] J. Dupacova and R. Wets, Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems, Ann. Statist., 16 (1988), pp. 1517-1549. · Zbl 0667.62018
[7] G. Folland, Real Analysis: Modern Techniques and Their Applications, 2nd ed., John Wiley & Sons, New York, 1999. · Zbl 0924.28001
[8] L. J. Halbeisen, Combinatorial Set Theory, Springer-Verlag, New York, 2017. · Zbl 1400.03002
[9] G. H. Huang and D. P. Loucks, An inexact two-stage stochastic programming model for water resources management under uncertainty, Civ. Eng. Environ. Syst., 17 (2000), pp. 95-118.
[10] A. J. Kleywegt, A. Shapiro, and T. Homem-de-Mello, The sample average approximation method for stochastic discrete optimization, SIAM J. Optim., 12 (2001), pp. 479-502, https://doi.org/10.1137/S1052623499363220. · Zbl 0991.90090
[11] J. Linderoth, A. Shapiro, and S. Wright, The empirical behavior of sampling methods for stochastic programming, Ann. Oper. Res., 142 (2006), pp. 215-241. · Zbl 1122.90391
[12] W. Mak, D. Morton, and K. Wood, Monte Carlo bounding techniques for determining solution quality in stochastic programs, Oper. Res. Lett., 24 (1999), pp. 47-56. · Zbl 0956.90022
[13] C. Niculescu and L. Persson, Convex Functions and Their Applications, 2nd ed., CMS Books Math./Ouvrages Math. SMC, Springer, Cham, 2018. · Zbl 1404.26003
[14] G. C. Pflug and A. Pichler, Multistage Stochastic Optimization, 2nd ed., Springer-Verlag, New York, 2014. · Zbl 1317.90220
[15] R. T. Rockafellar and R. J.-B. Wets, Stochastic convex programming: Relatively complete recourse and induced feasibility, SIAM J. Control Optim., 14 (1976), pp. 574-589, https://doi.org/10.1137/0314038. · Zbl 0346.90058
[16] A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, 1986. · Zbl 0665.90063
[17] A. Shapiro, D. Dentcheva, and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, 2nd ed., SIAM and MPS, Philadelphia, 2014, https://doi.org/10.1137/1.9781611973433. · Zbl 1302.90003
[18] A. Shapiro and A. Nemirovski, On complexity of stochastic programming problems, in Continuous Optimization, Springer, New York, 2005, pp. 111-146. · Zbl 1115.90041
[19] H. Sun and H. Xu, A note on uniform exponential convergence of sample average approximation of random functions, J. Math. Anal. Appl., 385 (2012), pp. 698-708. · Zbl 1251.90300
[20] R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge University Press, Cambridge, UK, 2018. · Zbl 1430.60005
[21] B. Verweij, S. Ahmed, A. Kleywegt, G. Nemhauser, and A. Shapiro, The sample average approximation method applied to stochastic routing problems: A computational study, Comput. Optim. Appl., 24 (2003), pp. 289-333. · Zbl 1094.90029
[22] Q. Wang, Y. Guan, and J. Wang, A chance-constrained two-stage stochastic program for unit commitment with uncertain wind power output, IEEE Trans. Power Syst., 27 (2012), pp. 206-215.
[23] H. Xu, Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming, J. Math. Anal. Appl., 368 (2010), pp. 692-710. · Zbl 1196.90089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.