×

Bound-based decision rules in multistage stochastic programming. (English) Zbl 1154.90558

Summary: We study bounding approximations for a multistage stochastic program with expected value constraints. Two simpler approximate stochastic programs, which provide upper and lower bounds on the original problem, are obtained by replacing the original stochastic data process by finitely supported approximate processes. We model the original and approximate processes as dependent random vectors on a joint probability space. This probabilistic coupling allows us to transform the optimal solution of the upper bounding problem to a near-optimal decision rule for the original problem. Unlike the scenario tree based solutions of the bounding problems, the resulting decision rule is implementable in all decision stages, i.e., there is no need for dynamic reoptimization during the planning period. Our approach is illustrated with a mean-risk portfolio optimization model.

MSC:

90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: EuDML Link

References:

[1] Ash R.: Real Analysis and Probability. Probability and Mathematical Statistics. Academic Press, Berlin 1972 · Zbl 1381.28001
[2] Birge J., Louveaux F.: Introduction to Stochastic Programming. Springer-Verlag, New York 1997 · Zbl 1223.90001 · doi:10.1007/978-1-4614-0237-4
[3] Birge J., Wets R.-B.: Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse. Math. Programming Stud. 27 (1986), 54-102 · Zbl 0603.90104 · doi:10.1007/BFb0121114
[4] Dokov S. P., Morton D. P.: Second-order lower bounds on the expectation of a convex function. Math. Oper. Res. 30 (2005), 3, 662-677 · Zbl 1082.90077 · doi:10.1287/moor.1040.0136
[5] Dupačová J.: Stochastic programming: Minimax approach. Encyclopedia of Optimization (C. Floudas and P. Pardalos, vol. 5, Kluwer 2001, pp. 327-330
[6] Žáčková) J. Dupačová (as: On minimax solutions of stochastic linear programming problems. Časopis pro pěstování matematiky 91 (1966), 423-429
[7] Edirisinghe N., Ziemba W.: Bounding the expectation of a saddle function with application to stochastic programming. Math. Oper. Res. 19 (1994), 314-340 · Zbl 0824.90101
[8] Fleten S.-E., Høyland, K., Wallace S. W.: The performance of stochastic dynamic and fixed mix portfolio models. European J. Oper. Res. 140 (2002), 1, 37-49 · Zbl 1030.90044 · doi:10.1016/S0377-2217(01)00195-3
[9] Frauendorfer K.: Multistage stochastic programming: Error analysis for the convex case. Z. Oper. Res. 39 (1994), 1, 93-122 · Zbl 0810.90098 · doi:10.1007/BF01440737
[10] Frauendorfer K.: Barycentric scenario trees in convex multistage stochastic programming. Math. Programming 75 (1996), 2, 277-294 · Zbl 0874.90144 · doi:10.1007/BF02592156
[11] Garstka S. J., Wets R. J.-B.: On decision rules in stochastic programming. Math. Programming 7 (1974), 117-143 · Zbl 0326.90049 · doi:10.1007/BF01585511
[12] Haneveld W. K., Vlerk M. van der: Integrated chance constraints: Reduced forms and an algorithm. Comput. Manag. Sci. 3 (2006), 2, 245-269 · Zbl 1136.90424 · doi:10.1007/s10287-005-0007-3
[13] Heitsch H., Römisch, W., Strugarek C.: Stability of multistage stochastic programs. SIAM J. Optim. 17 (2006), 511-525 · Zbl 1165.90582 · doi:10.1137/050632865
[14] Hochreiter R., Pflug, G.: Financial scenario generation for stochastic multi-stage decision processes as facility location problems. Ann. Oper. Res. 156 (2007), 1, 257-272 · Zbl 1144.90442 · doi:10.1007/s10479-006-0140-6
[15] Høyland K., Wallace S.: Generating scenario trees for multistage decision problems. Management Sci. 47 (2001), 2, 295-307 · Zbl 1232.91132 · doi:10.1287/mnsc.47.2.295.9834
[16] Infanger G.: Planning under Uncertainty: Solving Large-Scale Stochastic Linear Programs. Boyd and Fraser, Danvers 1994 · Zbl 0867.90086
[17] Kaňková V., Šmíd M.: On approximation in multistage stochastic programs: Markov dependence. Kybernetika 40 (2004), 5, 625-638 · Zbl 1249.90183
[18] Kleywegt A. J., Shapiro, A., Homem-de-Mello T.: The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12 (2002), 2, 479-502 · Zbl 0991.90090 · doi:10.1137/S1052623499363220
[19] Koivu M.: Variance reduction in sample approximations of stochastic programs. Math. Programming, Ser. A 103 (2005), 3, 463-485 · Zbl 1099.90036 · doi:10.1007/s10107-004-0557-0
[20] Kouwenberg R.: Scenario generation and stochastic programming models for asset and liability management. European J. Oper. Res. 134 (2001), 2, 279-292 · Zbl 1008.91050 · doi:10.1016/S0377-2217(00)00261-7
[21] Kuhn D.: Aggregation and discretization in multistage stochastic programming. Math. Programming, Ser. A 113 (2008), 1, 61-94 · Zbl 1135.90032 · doi:10.1007/s10107-006-0048-6
[22] Kuhn D.: Convergent bounds for stochastic programs with expected value constraints. The Stochastic Programming E-Print Series (SPEPS), 2007 · Zbl 1175.90304 · doi:10.1007/s10957-008-9476-1
[23] Kuhn D., Parpas, P., Rustem B.: Threshold accepting approach to improve bound-based approximations for portfolio optimization. Computational Methods in Financial Engineering (E. Kontoghiorghes, B. Rustem, and P. Winker, Springer-Verlag, Berlin 2008, pp. 3-26 · Zbl 1142.91535
[24] Mirkov R., Pflug G.: Tree approximations of dynamic stochastic programs. SIAM J. Optim. 18 (2007), 3, 1082-1105 · Zbl 1211.90150 · doi:10.1137/060658552
[25] Pennanen T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Math. Programming, to appear · Zbl 1165.90014 · doi:10.1007/s10107-007-0113-9
[26] Pflug G.: Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Programming, Ser. B 89 (2001), 251-271 · Zbl 0987.91034 · doi:10.1007/s101070000202
[27] Rachev S., Römisch W.: Quantitative stability in stochastic programming: the method of probability metrics. Math. Oper. Res. 27 (2002), 792-818 · Zbl 1082.90080 · doi:10.1287/moor.27.4.792.304
[28] Rockafellar R. T., Uryasev S.: Optimization of conditional value-at-risk. J. Risk 2 (2000) 3, 21-41
[29] Shapiro A., Nemirovski A.: On complexity of stochastic programming problems. Continuous Optimization: Current Trends and Applications 2005 (V. Jeyakumar and A. Rubinov, Springer-Verlag, Berlin 2006, pp. 111-144 · Zbl 1115.90041
[30] Thénié J., Vial J.-P.: Step decision rules for multistage stochastic programming: a heuristic approach. Optimization Online, 2006 · Zbl 1283.90027 · doi:10.1016/j.automatica.2008.02.001
[31] Wright S.: Primal-dual aggregation and disaggregation for stochastic linear programs. Math. Oper. Res. 19 (1994), 4, 893-908 · Zbl 0821.90086 · doi:10.1287/moor.19.4.893
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.