| Title:
|
Bound-based decision rules in multistage stochastic programming (English) |
| Author:
|
Kuhn, Daniel |
| Author:
|
Parpas, Panos |
| Author:
|
Rustem, Berç |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
44 |
| Issue:
|
2 |
| Year:
|
2008 |
| Pages:
|
134-150 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
stochastic programming |
| Keyword:
|
bounds |
| Keyword:
|
decision rules |
| Keyword:
|
expected value constraints |
| Keyword:
|
portfolio optimization |
| MSC:
|
90C15 |
| MSC:
|
91B28 |
| idZBL:
|
Zbl 1154.90558 |
| idMR:
|
MR2428216 |
| . |
| Date available:
|
2009-09-24T20:32:58Z |
| Last updated:
|
2012-06-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135840 |
| . |
| Reference:
|
[1] Ash R.: Real Analysis and Probability.Probability and Mathematical Statistics. Academic Press, Berlin 1972 MR 0435320 |
| Reference:
|
[2] Birge J., Louveaux F.: Introduction to Stochastic Programming.Springer-Verlag, New York 1997 Zbl 1223.90001, MR 1460264 |
| Reference:
|
[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, MR 0836751 |
| Reference:
|
[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, MR 2161203 |
| Reference:
|
[5] Dupačová J.: Stochastic programming: Minimax approach.In: Encyclopedia of Optimization (C. Floudas and P. Pardalos, eds.), vol. 5, Kluwer 2001, pp. 327–330 |
| Reference:
|
[6] Žáčková) J. Dupačová (as: On minimax solutions of stochastic linear programming problems.Časopis pro pěstování matematiky 91 (1966), 423–429 MR 0216864 |
| Reference:
|
[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, MR 1290503 |
| Reference:
|
[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 MR 1894084 |
| Reference:
|
[9] Frauendorfer K.: Multistage stochastic programming: Error analysis for the convex case.Z. Oper. Res. 39 (1994), 1, 93–122 Zbl 0810.90098, MR 1268638 |
| Reference:
|
[10] Frauendorfer K.: Barycentric scenario trees in convex multistage stochastic programming.Math. Programming 75 (1996), 2, 277–294 Zbl 0874.90144, MR 1426642 |
| Reference:
|
[11] Garstka S. J., Wets R. J.-B.: On decision rules in stochastic programming.Math. Programming 7 (1974), 117–143 Zbl 0326.90049, MR 0351451 |
| Reference:
|
[12] Haneveld W. K., Vlerk M. van der: Integrated chance constraints: Reduced forms and an algorithm.Comput. Manag. Sci. 3 (2006), 2, 245–269 MR 2253949 |
| Reference:
|
[13] Heitsch H., Römisch, W., Strugarek C.: Stability of multistage stochastic programs.SIAM J. Optim. 17 (2006), 511–525 Zbl 1165.90582, MR 2247749 |
| Reference:
|
[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, MR 2303133 |
| Reference:
|
[15] Høyland K., Wallace S.: Generating scenario trees for multistage decision problems.Management Sci. 47 (2001), 2, 295–307 |
| Reference:
|
[16] Infanger G.: Planning under Uncertainty: Solving Large-Scale Stochastic Linear Programs.Boyd and Fraser, Danvers 1994 Zbl 0867.90086 |
| Reference:
|
[17] Kaňková V., Šmíd M.: On approximation in multistage stochastic programs: Markov dependence.Kybernetika 40 (2004), 5, 625–638 MR 2121001 |
| Reference:
|
[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, MR 1885572 |
| Reference:
|
[19] Koivu M.: Variance reduction in sample approximations of stochastic programs.Math. Programming, Ser. A 103 (2005), 3, 463–485 Zbl 1099.90036, MR 2166545 |
| Reference:
|
[20] Kouwenberg R.: Scenario generation and stochastic programming models for asset and liability management.European J. Oper. Res. 134 (2001), 2, 279–292 MR 1853618 |
| Reference:
|
[21] Kuhn D.: Aggregation and discretization in multistage stochastic programming.Math. Programming, Ser. A 113 (2008), 1, 61–94 Zbl 1135.90032, MR 2367066 |
| Reference:
|
[22] Kuhn D.: Convergent bounds for stochastic programs with expected value constraints.The Stochastic Programming E-Print Series (SPEPS), 2007 Zbl 1175.90304 |
| Reference:
|
[23] Kuhn D., Parpas, P., Rustem B.: Threshold accepting approach to improve bound-based approximations for portfolio optimization.In: Computational Methods in Financial Engineering (E. Kontoghiorghes, B. Rustem, and P. Winker, eds.), Springer–Verlag, Berlin 2008, pp. 3–26 Zbl 1142.91535 |
| Reference:
|
[24] Mirkov R., Pflug G.: Tree approximations of dynamic stochastic programs.SIAM J. Optim. 18 (2007), 3, 1082–1105 Zbl 1211.90150, MR 2345985 |
| Reference:
|
[25] Pennanen T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures.Math. Programming, to appear Zbl 1165.90014, MR 2421289 |
| Reference:
|
[26] Pflug G.: Scenario tree generation for multiperiod financial optimization by optimal discretization.Math. Programming, Ser. B 89 (2001), 251–271 MR 1816503 |
| Reference:
|
[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, MR 1939178 |
| Reference:
|
[28] Rockafellar R. T., Uryasev S.: Optimization of conditional value-at-risk.J. Risk 2 (2000) 3, 21–41 |
| Reference:
|
[29] Shapiro A., Nemirovski A.: On complexity of stochastic programming problems.In: Continuous Optimization: Current Trends and Applications 2005 (V. Jeyakumar and A. Rubinov, eds.), Springer-Verlag, Berlin 2006, pp. 111–144 Zbl 1115.90041, MR 2166475 |
| Reference:
|
[30] Thénié J., Vial J.-P.: Step decision rules for multistage stochastic programming: a heuristic approach.Optimization Online, 2006 |
| Reference:
|
[31] Wright S.: Primal-dual aggregation and disaggregation for stochastic linear programs.Math. Oper. Res. 19 (1994), 4, 893–908 Zbl 0821.90086, MR 1304629 |
| . |
