Bound-based decision rules in multistage stochastic programming

Kuhn, Daniel   ; Parpas, Panos   ; Rustem, Berç

Kybernetika, Tome 44 (2008) no. 2, pp. 134-150

Abstract (VO)

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.

Détail

Classification : 90C15, 91B28
Keywords: stochastic programming; bounds; decision rules; expected value constraints; portfolio optimization

Bibliographie

[1] Ash R.: Real Analysis and Probability. Probability and Mathematical Statistics. Academic Press, Berlin 1972 | MR

[2] Birge J., Louveaux F.: Introduction to Stochastic Programming. Springer-Verlag, New York 1997 | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[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

[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

[7] Edirisinghe N., Ziemba W.: Bounding the expectation of a saddle function with application to stochastic programming. Math. Oper. Res. 19 (1994), 314–340 | MR | Zbl

[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

[9] Frauendorfer K.: Multistage stochastic programming: Error analysis for the convex case. Z. Oper. Res. 39 (1994), 1, 93–122 | MR | Zbl

[10] Frauendorfer K.: Barycentric scenario trees in convex multistage stochastic programming. Math. Programming 75 (1996), 2, 277–294 | MR | Zbl

[11] Garstka S. J., Wets R. J.-B.: On decision rules in stochastic programming. Math. Programming 7 (1974), 117–143 | MR | Zbl

[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

[13] Heitsch H., Römisch, W., Strugarek C.: Stability of multistage stochastic programs. SIAM J. Optim. 17 (2006), 511–525 | MR | Zbl

[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 | MR | Zbl

[15] Høyland K., Wallace S.: Generating scenario trees for multistage decision problems. Management Sci. 47 (2001), 2, 295–307

[16] Infanger G.: Planning under Uncertainty: Solving Large-Scale Stochastic Linear Programs. Boyd and Fraser, Danvers 1994 | Zbl

[17] Kaňková V., Šmíd M.: On approximation in multistage stochastic programs: Markov dependence. Kybernetika 40 (2004), 5, 625–638 | MR

[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 | MR | Zbl

[19] Koivu M.: Variance reduction in sample approximations of stochastic programs. Math. Programming, Ser. A 103 (2005), 3, 463–485 | MR | Zbl

[20] Kouwenberg R.: Scenario generation and stochastic programming models for asset and liability management. European J. Oper. Res. 134 (2001), 2, 279–292 | MR

[21] Kuhn D.: Aggregation and discretization in multistage stochastic programming. Math. Programming, Ser. A 113 (2008), 1, 61–94 | MR | Zbl

[22] Kuhn D.: Convergent bounds for stochastic programs with expected value constraints. The Stochastic Programming E-Print Series (SPEPS), 2007 | Zbl

[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

[24] Mirkov R., Pflug G.: Tree approximations of dynamic stochastic programs. SIAM J. Optim. 18 (2007), 3, 1082–1105 | MR | Zbl

[25] Pennanen T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Math. Programming, to appear | MR | Zbl

[26] Pflug G.: Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Programming, Ser. B 89 (2001), 251–271 | MR

[27] Rachev S., Römisch W.: Quantitative stability in stochastic programming: the method of probability metrics. Math. Oper. Res. 27 (2002), 792–818 | MR | Zbl

[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. In: Continuous Optimization: Current Trends and Applications 2005 (V. Jeyakumar and A. Rubinov, eds.), Springer-Verlag, Berlin 2006, pp. 111–144 | MR | Zbl

[30] Thénié J., Vial J.-P.: Step decision rules for multistage stochastic programming: a heuristic approach. Optimization Online, 2006

[31] Wright S.: Primal-dual aggregation and disaggregation for stochastic linear programs. Math. Oper. Res. 19 (1994), 4, 893–908 | MR | Zbl