Bound-based decision rules in multistage stochastic programming

Daniel Kuhn; Panos Parpas; Berç Rustem

Kybernetika (2008)

  • Volume: 44, Issue: 2, page 134-150
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Kuhn, Daniel, Parpas, Panos, and Rustem, Berç. "Bound-based decision rules in multistage stochastic programming." Kybernetika 44.2 (2008): 134-150. <http://eudml.org/doc/33918>.

@article{Kuhn2008,
abstract = {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.},
author = {Kuhn, Daniel, Parpas, Panos, Rustem, Berç},
journal = {Kybernetika},
keywords = {stochastic programming; bounds; decision rules; expected value constraints; portfolio optimization; stochastic programming; bounds; decision rules; expected value constraints; portfolio optimization},
language = {eng},
number = {2},
pages = {134-150},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Bound-based decision rules in multistage stochastic programming},
url = {http://eudml.org/doc/33918},
volume = {44},
year = {2008},
}

TY - JOUR
AU - Kuhn, Daniel
AU - Parpas, Panos
AU - Rustem, Berç
TI - Bound-based decision rules in multistage stochastic programming
JO - Kybernetika
PY - 2008
PB - Institute of Information Theory and Automation AS CR
VL - 44
IS - 2
SP - 134
EP - 150
AB - 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.
LA - eng
KW - stochastic programming; bounds; decision rules; expected value constraints; portfolio optimization; stochastic programming; bounds; decision rules; expected value constraints; portfolio optimization
UR - http://eudml.org/doc/33918
ER -

References

top
  1. Ash R., Real Analysis and Probability, Probability and Mathematical Statistics. Academic Press, Berlin 1972 MR0435320
  2. Birge J., Louveaux F., Introduction to Stochastic Programming, Springer-Verlag, New York 1997 Zbl1223.90001MR1460264
  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 (1986) Zbl0603.90104MR0836751
  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 Zbl1082.90077MR2161203
  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 (1966) MR0216864
  7. Edirisinghe N., Ziemba W., Bounding the expectation of a saddle function with application to stochastic programming, Math. Oper. Res. 19 (1994), 314–340 (1994) Zbl0824.90101MR1290503
  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 MR1894084
  9. Frauendorfer K., Multistage stochastic programming: Error analysis for the convex case, Z. Oper. Res. 39 (1994), 1, 93–122 (1994) Zbl0810.90098MR1268638
  10. Frauendorfer K., Barycentric scenario trees in convex multistage stochastic programming, Math. Programming 75 (1996), 2, 277–294 (1996) Zbl0874.90144MR1426642
  11. Garstka S. J., Wets R. J.-B., On decision rules in stochastic programming, Math. Programming 7 (1974), 117–143 (1974) Zbl0326.90049MR0351451
  12. Haneveld W. K., Vlerk M. van der, Integrated chance constraints: Reduced forms and an algorithm, Comput. Manag. Sci. 3 (2006), 2, 245–269 MR2253949
  13. Heitsch H., Römisch, W., Strugarek C., Stability of multistage stochastic programs, SIAM J. Optim. 17 (2006), 511–525 Zbl1165.90582MR2247749
  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 Zbl1144.90442MR2303133
  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 Zbl0867.90086
  17. Kaňková V., Šmíd M., On approximation in multistage stochastic programs: Markov dependence, Kybernetika 40 (2004), 5, 625–638 MR2121001
  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 Zbl0991.90090MR1885572
  19. Koivu M., Variance reduction in sample approximations of stochastic programs, Math. Programming, Ser. A 103 (2005), 3, 463–485 Zbl1099.90036MR2166545
  20. Kouwenberg R., Scenario generation and stochastic programming models for asset and liability management, European J. Oper. Res. 134 (2001), 2, 279–292 MR1853618
  21. Kuhn D., Aggregation and discretization in multistage stochastic programming, Math. Programming, Ser. A 113 (2008), 1, 61–94 Zbl1135.90032MR2367066
  22. Kuhn D., Convergent bounds for stochastic programs with expected value constraints, The Stochastic Programming E-Print Series (SPEPS), 2007 Zbl1175.90304
  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 Zbl1142.91535
  24. Mirkov R., Pflug G., Tree approximations of dynamic stochastic programs, SIAM J. Optim. 18 (2007), 3, 1082–1105 Zbl1211.90150MR2345985
  25. Pennanen T., Epi-convergent discretizations of multistage stochastic programs via integration quadratures, Math. Programming, to appear Zbl1165.90014MR2421289
  26. Pflug G., Scenario tree generation for multiperiod financial optimization by optimal discretization, Math. Programming, Ser. B 89 (2001), 251–271 MR1816503
  27. Rachev S., Römisch W., Quantitative stability in stochastic programming: the method of probability metrics, Math. Oper. Res. 27 (2002), 792–818 Zbl1082.90080MR1939178
  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 Zbl1115.90041MR2166475
  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 (1994) Zbl0821.90086MR1304629

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.