×

Convergent bounds for stochastic programs with expected value constraints. (English) Zbl 1175.90304

Summary: This article describes a bounding approximation scheme for convex multistage stochastic programs (MSP) that constrain the conditional expectation of some decision-dependent random variables. Expected value constraints of this type are useful for modelling a decision maker’s risk preferences, but they may also arise as artifacts of stage-aggregation. We develop two finite-dimensional approximate problems that provide bounds on the (infinite-dimensional) original problem, and we show that the gap between the bounds can be made smaller than any prescribed tolerance. Moreover, the solutions of the approximate MSPs give rise to a feasible policy for the original MSP, and this policy’s optimality gap is shown to be smaller than the difference of the bounds. The considered problem class comprises models with integrated chance constraints and conditional value-at-risk constraints. No relatively complete recourse is assumed.

MSC:

90C15 Stochastic programming

Software:

EVPI
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (1997) · Zbl 0892.90142
[2] Kall, P., Wallace, S.W.: Stochastic Programming. Wiley, Chichester (1994)
[3] Prékopa, A.: Stochastic Programming. Kluwer Academic, Dordrecht (1995) · Zbl 0834.90098
[4] Wallace, S.W., Ziemba, W.T. (eds.): Applications of Stochastic Programming. MPS/SIAM Series on Optimization, vol. 5. SIAM, Philadelphia (2005) · Zbl 1068.90002
[5] Kaut, M., Wallace, S.W.: Evaluation of scenario-generation methods for stochastic programming. Pac. J. Optim. 3(2), 257–271 (2007) · Zbl 1171.90490
[6] Høyland, K., Wallace, S.W.: Generating scenario trees for multistage decision problems. Manag. Sci. 47(2), 295–307 (2001) · Zbl 1232.91132 · doi:10.1287/mnsc.47.2.295.9834
[7] Shapiro, A.: On complexity of multistage stochastic programs. Oper. Res. Lett. 34, 1–8 (2006) · Zbl 1080.90056 · doi:10.1016/j.orl.2005.02.003
[8] Shapiro, A.: Inference of statistical bounds for multistage stochastic programming problems. Math. Methods Oper. Res. 58(1), 57–68 (2003) · Zbl 1116.90384 · doi:10.1007/s001860300280
[9] Koivu, M.: Variance reduction in sample approximations of stochastic programs. Math. Program. Ser. A 103, 463–485 (2005) · Zbl 1099.90036 · doi:10.1007/s10107-004-0557-0
[10] Pennanen, T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Math. Program. Ser. B 116(1), 461–479 (2009) · Zbl 1165.90014 · doi:10.1007/s10107-007-0113-9
[11] Pflug, G.Ch.: Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Program. Ser. B 89, 251–271 (2001) · Zbl 0987.91034 · doi:10.1007/PL00011398
[12] Hochreiter, R., Pflug, G.Ch.: Financial scenario generation for stochastic multi-stage decision processes as facility location problems. Ann. Oper. Res. 156(1), 257–272 (2007) · Zbl 1144.90442 · doi:10.1007/s10479-006-0140-6
[13] Dupačová, J., Gröwe-Kuska, N., Römisch, W.: Scenario reduction in stochastic programming: an approach using probability metrics. Math. Program. Ser. A 95, 493–511 (2003) · Zbl 1023.90043 · doi:10.1007/s10107-002-0331-0
[14] Heitsch, H., Römisch, W.: Scenario reduction algorithms in stochastic programming. Comput. Optim. Appl. 24, 187–206 (2003) · Zbl 1094.90024 · doi:10.1023/A:1021805924152
[15] Rachev, S.T., Römisch, W.: Quantitative stability in stochastic programming: the method of probability metrics. Math. Oper. Res. 27, 792–818 (2002) · Zbl 1082.90080 · doi:10.1287/moor.27.4.792.304
[16] Dantzig, G.B., Infanger, G.: Large-scale stochastic linear programs–importance sampling and Benders decomposition. Comput. Appl. Math. I, 111–120 (1992) · Zbl 0781.65052
[17] Dempster, M.A.H., Thompson, R.T.: EVPI-based importance sampling solution procedures for multistage stochastic linear programmes on parallel MIMD architectures. Ann. Oper. Res. 90, 161–184 (1999) · Zbl 0937.90075 · doi:10.1023/A:1018956530304
[18] Ermoliev, Y.M., Gaivoronski, A.A.: Stochastic quasigradient methods for optimization of discrete event systems. Ann. Oper. Res. 39, 1–39 (1992) · Zbl 0765.90069 · doi:10.1007/BF02060934
[19] Higle, J.L., Sen, S.: Stochastic decomposition: an algorithm for two-stage linear programs with recourse. Math. Oper. Res. 16, 650–669 (1991) · Zbl 0746.90045 · doi:10.1287/moor.16.3.650
[20] Infanger, G.: Planning under Uncertainty: Solving Large-Scale Stochastic Linear Programs. Boyd and Fraser, Danvers (1994) · Zbl 0867.90086
[21] Birge, J.R., Wets, R.J.-B.: Computing bounds for stochastic programming problems by means of a generalized moment problem. Math. Oper. Res. 12, 149–162 (1987) · Zbl 0619.90053 · doi:10.1287/moor.12.1.149
[22] Dupačová, J.: On minimax solutions of stochastic linear programming problems. Časopis Pěstování Mat. 91, 423–429 (1966). (As Žáčková)
[23] Frauendorfer, K.: Solving SLP recourse problems with arbitrary multivariate distributions–the dependent case. Math. Oper. Res. 13, 377–394 (1988) · Zbl 0652.90080 · doi:10.1287/moor.13.3.377
[24] Gassmann, G., Ziemba, W.T.: A tight upper bound for the expectation of a convex function of a multivariate random variable. Math. Program. Study 27, 39–53 (1986) · Zbl 0603.60014
[25] Kall, P.: An upper bound for SLP using first and total second moments. Ann. Oper. Res. 30, 267–276 (1991) · Zbl 0749.90055 · doi:10.1007/BF02204820
[26] Madansky, A.: Inequalities for stochastic linear programming problems. Manag. Sci. 6, 197–204 (1960) · Zbl 0995.90601 · doi:10.1287/mnsc.6.2.197
[27] Edirisinghe, N.C.P., Ziemba, W.T.: Bounding the expectation of a saddle function with application to stochastic programming. Math. Oper. Res. 19, 314–340 (1994) · Zbl 0824.90101 · doi:10.1287/moor.19.2.314
[28] Edirisinghe, N.C.P., Ziemba, W.T.: Bounds for two-stage stochastic programs with fixed recourse. Math. Oper. Res. 19, 292–313 (1994) · Zbl 0824.90100 · doi:10.1287/moor.19.2.292
[29] Frauendorfer, K.: Stochastic Two-Stage Programming. Lecture Notes in Economics and Mathematical Systems, vol. 392. Springer, Berlin (1992) · Zbl 0794.90042
[30] Frauendorfer, K.: Multistage stochastic programming: error analysis for the convex case. Z. Oper. Res. 39(1), 93–122 (1994) · Zbl 0810.90098
[31] Frauendorfer, K.: Barycentric scenario trees in convex multistage stochastic programming. Math. Program. 75(2), 277–294 (1996) · Zbl 0874.90144
[32] Kuhn, D.: Generalized Bounds for Convex Multistage Stochastic Programs. Lecture Notes in Economics and Mathematical Systems, vol. 548. Springer, Berlin (2004) · Zbl 1103.90069
[33] Wright, S.E.: Primal-dual aggregation and disaggregation for stochastic linear programs. Math. Oper. Res. 19(4), 893–908 (1994) · Zbl 0821.90086 · doi:10.1287/moor.19.4.893
[34] Kuhn, D.: Aggregation and discretization in multistage stochastic programming. Math. Program. Ser. A 113(1), 61–94 (2008) · Zbl 1135.90032 · doi:10.1007/s10107-006-0048-6
[35] Prékopa, A.: Contributions to the theory of stochastic programming. Math. Program. 4, 202–221 (1973) · Zbl 0273.90045 · doi:10.1007/BF01584661
[36] Charnes, A., Cooper, W.W.: Chance-constrained programming. Manag. Sci. 6, 73–79 (1959/1960) · Zbl 0995.90600 · doi:10.1287/mnsc.6.1.73
[37] Klein Haneveld, W.K.: Duality in Stochastic Linear and Dynamic Programming. Lecture Notes in Economics and Mathematical Systems, vol. 274. Springer, Berlin (1985) · Zbl 0576.90100
[38] Klein Haneveld, W.K., van der Vlerk, M.H.: Integrated chance constraints: reduced forms and an algorithm. Comput. Manag. Sci. 3(4), 245–269 (2006) · Zbl 1136.90424 · doi:10.1007/s10287-005-0007-3
[39] Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-at-risk. J. Risk 2(3), 21–41 (2000)
[40] Rockafellar, R.T., Uryasev, S.: Conditional value-at-risk for general loss distributions. J. Bank. Finance 26, 1443–1471 (2002) · doi:10.1016/S0378-4266(02)00271-6
[41] Rockafellar, R.T., Wets, R.J.-B.: The optimal recourse problem in discrete time: L 1-multipliers for inequality constraints. SIAM J. Control Optim. 16, 16–36 (1978) · Zbl 0397.90078 · doi:10.1137/0316002
[42] Rockafellar, R.T.: Conjugate Duality and Optimization. SIAM, Philadelphia (1974) · Zbl 0296.90036
[43] Rockafellar, R.T., Wets, R.J.-B.: Nonanticipativity and L 1-martingales in stochastic optimization problems. Math. Program. Study 6, 170–187 (1976) · Zbl 0377.90073
[44] Rockafellar, R.T., Wets, R.J.-B.: Stochastic convex programming: basic duality. Pac. J. Math. 62, 173–195 (1976) · Zbl 0339.90048
[45] Rockafellar, R.T., Wets, R.J.-B.: Stochastic convex programming: relatively complete recourse and induced feasibility. SIAM J. Control Optim. 14, 574–589 (1976) · Zbl 0346.90058 · doi:10.1137/0314038
[46] Rockafellar, R.T., Wets, R.J.-B.: Stochastic convex programming: singular multipliers and extended duality. Pac. J. Math. 62, 507–522 (1976) · Zbl 0346.90057
[47] Dunford, N., Schwartz, J.T.: Linear Operators: Part I. Wiley, New York/Chichester/Brisbane/Toronto/Singapore (1988) · Zbl 0635.47001
[48] Pennanen, T.: Epi-convergent discretizations of multistage stochastic programs. Math. Oper. Res. 30(1), 245–256 (2005) · Zbl 1082.90078 · doi:10.1287/moor.1040.0114
[49] Heitsch, H., Römisch, W., Strugarek, C.: Stability of multistage stochastic programs. SIAM J. Optim. 17, 511–525 (2006) · Zbl 1165.90582 · doi:10.1137/050632865
[50] Casey, M.S., Sen, S.: The scenario generation algorithm for multistage stochastic linear programming. Math. Oper. Res. 30(3), 615–631 (2005) · Zbl 1082.90076 · doi:10.1287/moor.1050.0146
[51] Kuhn, D., Parpas, P., Rustem, B.: Threshold accepting approach to improve bound-based approximations for portfolio optimization. In: Kontoghiorghes, E., Rustem, B., Winker, P. (eds.) Computational Methods in Financial Engineering, pp. 3–26. Springer, Berlin (2008) · Zbl 1142.91535
[52] Kuhn, D., Parpas, P., Rustem, B.: Bound-based decision rules in multistage stochastic programming. Kybernetika 44(2), 134–150 (2008) · Zbl 1154.90558
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.