×
Sun, Hailin; Xu, Huifu; Wang, Yong

Asymptotic analysis of sample average approximation for stochastic optimization problems with joint chance constraints via conditional value at risk and difference of convex functions. (English) Zbl 1314.90059

J. Optim. Theory Appl. 161, No. 1, 257-284 (2014).
A problem of stochastic optimization with joint chance constraints is approximated by a problem of conditional value at risk which is attacked by the method of sample average approximation. The authors prove that under moderate conditions the optimal solutions and stationary points, obtained by applying the sample average approximation method, converge with probability one to their true counterparts. The exponential convergence rate is established for the convergence of stationary points. Similar convergence results for DC-approximation of chance constraints are listed where DC means an approximation by the difference of two convex functions. The results of numerical experiments are reported.
Reviewer: Antanas Žilinskas (Vilnius)

Cited in 13 Documents

MSC:

90C15 Stochastic programming
91G70 Statistical methods; risk measures

Keywords:

joint chance constraints; CVaR; DC-approximation; stationary point; exponential convergence
Cite Review PDF
Full Text: DOI

References:

[1] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049 · doi:10.1017/CBO9780511804441
[2] Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88, 411-424 (2000) · Zbl 0964.90025 · doi:10.1007/PL00011380
[3] Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-at-risk. J. Risk 2, 21-41 (2000)
[4] Nemirovski, A., Shapiro, A.: Convex approximations of chance constrained programs. SIAM J. Optim. 17, 969-996 (2006) · Zbl 1126.90056 · doi:10.1137/050622328
[5] Robinson, S.M.: Analysis of sample-path optimization. Math. Oper. Res. 21, 513-528 (1996) · Zbl 0868.90087 · doi:10.1287/moor.21.3.513
[6] Shapiro, A.; Rusczyński, A. (ed.); Shapiro, A. (ed.), Monte Carlo sampling methods, No. 10 (2003), Amsterdam · doi:10.1016/S0927-0507(03)10006-0
[7] Xu, H., Zhang, D.: Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications. Math. Program. 119, 371-401 (2009) · Zbl 1168.90009 · doi:10.1007/s10107-008-0214-0
[8] Meng, F.W., Sun, J., Goh, M.: Stochastic optimization problems with CVaR risk measure and their sample average approximation. J. Optim. Theory Appl. 146, 399-418 (2010) · Zbl 1213.91161 · doi:10.1007/s10957-010-9676-3
[9] Hiriart-Urruty, J.B.: Refinements of necessary optimality conditions in nondifferentiable programming I. Appl. Math. Optim. 5, 63-82 (1979) · Zbl 0389.90088 · doi:10.1007/BF01442544
[10] Pflug, G. Ch.; Rusczyński, A. (ed.); Shapiro, A. (ed.), Stochastic optimization and statistical inference, No. 10 (2003), Amsterdam · doi:10.1016/S0927-0507(03)10007-2
[11] Shapiro, A., Xu, H.: Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation. Optimization 57, 395-418 (2008) · Zbl 1145.90047 · doi:10.1080/02331930801954177
[12] Xu, H.: Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming. J. Math. Anal. Appl. 368, 692-710 (2010) · Zbl 1196.90089 · doi:10.1016/j.jmaa.2010.03.021
[13] Sun, H., Xu, H.: A note on uniform exponential convergence of sample average approximation of random functions. J. Math. Anal. Appl. 385, 698-708 (2012) · Zbl 1251.90300 · doi:10.1016/j.jmaa.2011.07.007
[14] Hong, L.J., Yang, Y., Zhang, L.: Sequential convex approximations to joint chance constrained programs: a Monte Carlo approach. Oper. Res. 59, 617-630 (2011) · Zbl 1231.90303 · doi:10.1287/opre.1100.0910
[15] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[16] Wang, W.: Sample average approximation of risk-averse stochastic programs. PhD Thesis, Georgia Institute of Technology (2007) · Zbl 1246.90110
[17] Aumann, R.J.: Integrals of set-valued functions. J. Math. Anal. Appl. 12, 1-12 (1965) · Zbl 0163.06301 · doi:10.1016/0022-247X(65)90049-1
[18] Artstein, Z., Vitale, R.A.: A strong law of large numbers for random compact set. Ann. Probab. 3, 879-882 (1975) · Zbl 0313.60012 · doi:10.1214/aop/1176996275
[19] Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer Series in Operations Research. Springer, New York (2000) · Zbl 0966.49001 · doi:10.1007/978-1-4612-1394-9
[20] Berge C, C.: Espaces Topologiques, Fonctions Multivoques. Dunod, Paris (1966) · Zbl 0164.52902
[21] Dentcheva, D., Ruszczyński, A.: Composite semi-infinite optimization. Control Cybern. 36, 1-14 (2007) · Zbl 1166.49025
[22] Sun, H., Xu, H.: Convergence analysis of stationary points in sample average approximation of stochastic programs with second order stochastic dominance constraints. Math. Program. Ser. B (2012, to appear) · Zbl 1295.90033
[23] Ralph, D., Xu, H.: Asymptotic analysis of stationary points of sample average two stage stochastic programs: a generalized equation approach. Math. Oper. Res. 36, 568-592 (2011) · Zbl 1246.90110 · doi:10.1287/moor.1110.0506
[24] Castaing, C., Valadier, M.: Convex Analysis and Measurable Multifunctions. Springer Series in Lecture Notes in Mathematics. Springer, Berlin (1977) · Zbl 0346.46038 · doi:10.1007/BFb0087685
[25] Terán, P.: On a uniform law of large numbers for random sets and subdifferentials of random functions. Stat. Probab. Lett. 78, 42-49 (2008) · Zbl 1134.60325 · doi:10.1016/j.spl.2007.05.026
[26] Qi, L., Shapiro, A., Ling, C.: Differentiability and semismoothness properties of integral functions and their applications. Math. Program. 102, 223-248 (2005) · Zbl 1079.90143 · doi:10.1007/s10107-004-0523-x
[27] Hess, C.: Conditional expectation and martingales of random sets. Pattern Recognit. 32, 1543-1567 (1999) · doi:10.1016/S0031-3203(99)00020-5
[28] Papageorgiou, N.S.: On the theory of Banach space valued multifunctions, I: integration and conditional expectation. J. Multivar. Anal. 17, 185-206 (1985) · Zbl 0579.28009 · doi:10.1016/0047-259X(85)90078-8
[29] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998) · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3
[30] Hong, L.J., Zhang, L.: CVaR approximation to chance constrained program: what is lost and how to find it back? Report, The Hong Kong University of Science and Technology (2010)
[31] Sun, H., Xu, H., Wang, Y.: Asymptotic analysis of sample average approximation for stochastic optimization problems with joint chance constraints via CVaR/DC approximations. Optimization online, old version (2012) · Zbl 0163.06301
[32] Pflug, C.C., Römisch, W.: Modeling, Measuring and Managing Risk. World Scientific, Singapore (2007) · Zbl 1153.91023 · doi:10.1142/6478
[33] Conego, A.J., Carrión, M., Morales, J.M.: Decision Making Under Uncertainty in Electricity Markets. Springer, New York (2010) · Zbl 1209.91007 · doi:10.1007/978-1-4419-7421-1
[34] Alexander, G.J., Baptista, A.M.: A comparison of VaR and CVaR constraints on portfolio selection with the mean-variance model. Manag. Sci. 50, 1261-1273 (2004) · doi:10.1287/mnsc.1040.0201
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.