Thin and heavy tails in stochastic programming

Vlasta Kaňková; Michal Houda

Kybernetika (2015)

  • Volume: 51, Issue: 3, page 433-456
  • ISSN: 0023-5954

Abstract

top
Optimization problems depending on a probability measure correspond to many applications. These problems can be static (single-stage), dynamic with finite (multi-stage) or infinite horizon, single- or multi-objective. It is necessary to have complete knowledge of the “underlying” probability measure if we are to solve the above-mentioned problems with precision. However this assumption is very rarely fulfilled (in applications) and consequently, problems have to be solved mostly on the basis of data. Stochastic estimates of an optimal value and an optimal solution can only be obtained using this approach. Properties of these estimates have been investigated many times. In this paper we intend to study one-stage problems under unusual (corresponding to reality, however) assumptions. In particular, we try to compare the achieved results under the assumptions of thin and heavy tails in the case of problems with linear and nonlinear dependence on the probability measure, problems with probability and risk measure constraints, and the case of stochastic dominance constraints. Heavy-tailed distributions quite often appear in financial problems [26] while nonlinear dependence frequently appears in problems with risk measures [22, 30]. The results we introduce follow mostly from the stability results based on the Wasserstein metric with the “underlying" ℒ 1 norm. Theoretical results are completed by a simulation investigation.

How to cite

top

Kaňková, Vlasta, and Houda, Michal. "Thin and heavy tails in stochastic programming." Kybernetika 51.3 (2015): 433-456. <http://eudml.org/doc/271580>.

@article{Kaňková2015,
abstract = {Optimization problems depending on a probability measure correspond to many applications. These problems can be static (single-stage), dynamic with finite (multi-stage) or infinite horizon, single- or multi-objective. It is necessary to have complete knowledge of the “underlying” probability measure if we are to solve the above-mentioned problems with precision. However this assumption is very rarely fulfilled (in applications) and consequently, problems have to be solved mostly on the basis of data. Stochastic estimates of an optimal value and an optimal solution can only be obtained using this approach. Properties of these estimates have been investigated many times. In this paper we intend to study one-stage problems under unusual (corresponding to reality, however) assumptions. In particular, we try to compare the achieved results under the assumptions of thin and heavy tails in the case of problems with linear and nonlinear dependence on the probability measure, problems with probability and risk measure constraints, and the case of stochastic dominance constraints. Heavy-tailed distributions quite often appear in financial problems [26] while nonlinear dependence frequently appears in problems with risk measures [22, 30]. The results we introduce follow mostly from the stability results based on the Wasserstein metric with the “underlying" $ \{\mathcal \{L\}\}_\{1\}$ norm. Theoretical results are completed by a simulation investigation.},
author = {Kaňková, Vlasta, Houda, Michal},
journal = {Kybernetika},
keywords = {stochastic programming problems; stability; Wasserstein metric; $\{\mathcal \{L\}\}_\{1\}$ norm; Lipschitz property; empirical estimates; convergence rate; linear and nonlinear dependence; probability and risk constraints; stochastic dominance; stochastic programming problems; stability; Wasserstein metric; $\{\mathcal \{L\}\}_\{1\}$ norm; Lipschitz property; empirical estimates; convergence rate; linear dependence; nonlinear dependence; probability constraints; risk constraints; stochastic dominance},
language = {eng},
number = {3},
pages = {433-456},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Thin and heavy tails in stochastic programming},
url = {http://eudml.org/doc/271580},
volume = {51},
year = {2015},
}

TY - JOUR
AU - Kaňková, Vlasta
AU - Houda, Michal
TI - Thin and heavy tails in stochastic programming
JO - Kybernetika
PY - 2015
PB - Institute of Information Theory and Automation AS CR
VL - 51
IS - 3
SP - 433
EP - 456
AB - Optimization problems depending on a probability measure correspond to many applications. These problems can be static (single-stage), dynamic with finite (multi-stage) or infinite horizon, single- or multi-objective. It is necessary to have complete knowledge of the “underlying” probability measure if we are to solve the above-mentioned problems with precision. However this assumption is very rarely fulfilled (in applications) and consequently, problems have to be solved mostly on the basis of data. Stochastic estimates of an optimal value and an optimal solution can only be obtained using this approach. Properties of these estimates have been investigated many times. In this paper we intend to study one-stage problems under unusual (corresponding to reality, however) assumptions. In particular, we try to compare the achieved results under the assumptions of thin and heavy tails in the case of problems with linear and nonlinear dependence on the probability measure, problems with probability and risk measure constraints, and the case of stochastic dominance constraints. Heavy-tailed distributions quite often appear in financial problems [26] while nonlinear dependence frequently appears in problems with risk measures [22, 30]. The results we introduce follow mostly from the stability results based on the Wasserstein metric with the “underlying" $ {\mathcal {L}}_{1}$ norm. Theoretical results are completed by a simulation investigation.
LA - eng
KW - stochastic programming problems; stability; Wasserstein metric; ${\mathcal {L}}_{1}$ norm; Lipschitz property; empirical estimates; convergence rate; linear and nonlinear dependence; probability and risk constraints; stochastic dominance; stochastic programming problems; stability; Wasserstein metric; ${\mathcal {L}}_{1}$ norm; Lipschitz property; empirical estimates; convergence rate; linear dependence; nonlinear dependence; probability constraints; risk constraints; stochastic dominance
UR - http://eudml.org/doc/271580
ER -

References

top
  1. Barrio, E., Giné, E., Matrán, E., 10.1214/aop/1022677394, Ann. Probab. 27 (1999), 2, 1009-1071. MR1698999DOI10.1214/aop/1022677394
  2. Billingsley, P., Ergodic Theory and Information., John Wiley and Sons, New York 1965. Zbl0184.43301MR0192027
  3. Birge, J. R., Louveaux, F., Introduction in Stochastic Programming., Springer, Berlin 1992. 
  4. Dai, L., Chen, C.-H., Birge, J. R., 10.1023/a:1004649211111, J. Optim. Theory Appl. 106 (2000), 489-509. Zbl0980.90057MR1797371DOI10.1023/a:1004649211111
  5. Dentcheva, D., Ruszczynski, A., 10.1016/j.jbankfin.2005.04.024, J. Banking and Finance 30 (2006), 433-451. DOI10.1016/j.jbankfin.2005.04.024
  6. Dupačová, J., B.Wets, R. J., 10.1214/aos/1176351052, Ann. Statist. 16 (1984), 1517-1549. MR0964937DOI10.1214/aos/1176351052
  7. Dvoretzky, A., Kiefer, J., Wolfowitz, J., 10.1214/aoms/1177728174, Ann. Math. Statist. 56 (1956), 642-669. MR0083864DOI10.1214/aoms/1177728174
  8. Ermoliev, Y. M., Norkin, V., 10.1137/120863277, SIAM J. Optim. 23 (2013), 4, 2231-2263. MR3129765DOI10.1137/120863277
  9. Gut, A., Probability: A Graduate Course., Springer, New York 2005. Zbl1267.60001MR2125120
  10. Houda, M., Stability and Approximations for Stochastic Programs., Doctoral Thesis, Faculty of Mathematics and Physics, Charles University Prague, Prague 2009. 
  11. Houda, M., Kaňková, V., Empirical estimates in economic and financial optimization problems., Bull. Czech Econometr. Soc. 19 (2012), 29, 50-69. 
  12. Kaniovski, Y. M., King, A. J., Wets, R. J.-B., 10.1007/bf02031707, Ann. Oper. Res. 56 (1995), 189-208. Zbl0835.90055MR1339792DOI10.1007/bf02031707
  13. Kaňková, V., Optimum solution of a stochastic optimization problem., In: Trans. 7th Prague Conf. 1974, Academia, Prague 1977, pp. 239-244. Zbl0408.90060MR0519478
  14. Kaňková, V., An approximative solution of stochastic optimization problem., In: Trans. 8th Prague Conf., Academia, Prague 1978, pp. 349-353. MR0536792
  15. Kaňková, V., Lachout, P., Convergence rate of empirical estimates in stochastic programming., Informatica 3 (1992), 4, 497-523. Zbl0906.90133MR1243755
  16. Kaňková, V., Stability in stochastic programming - the case of unknown location parameter., Kybernetika 29 (1993), 1, 97-112. Zbl0803.90096MR1227744
  17. Kaňková, V., 10.1016/0377-0427(94)90381-6, J. Comput. Appl. Math. 56 (1994), 97-112. Zbl0824.90104MR1338638DOI10.1016/0377-0427(94)90381-6
  18. Kaňková, V., On the stability in stochastic programming: the case of individual probability constraints., Kybernetika 33 (1997), 5, 525-544. Zbl0908.90198MR1603961
  19. Kaňková, V., Houda, M., Empirical estimates in stochastic programming., In: Proc. Prague Stochastics 2006 (M. Hušková and M. Janžura, eds.), MATFYZPRESS, Prague 2006, pp. 426-436. Zbl1162.90528
  20. Kaňková, V., Houda, M., Dependent samples in empirical estimation of stochastic programming problems., Austrian J. Statist. 35 (2006), 2 - 3, 271-279. 
  21. Kaňková, V., Empirical estimates in stochastic programming via distribution tails., Kybernetika 46 (2010), 3, 459-471. MR2676083
  22. Kaňková, V., Empirical estimates in optimization problems: survey with special regard to heavy tails and dependent samples., Bull. Czech Econometr. Soc. 19 (2012), 30, 92-111. 
  23. Kaňková, V., Risk measures in optimization problems via empirical estimates., Czech Econom. Rev. VII (2013), 3, 162-177. 
  24. Klebanov, L. B., Heavy Tailed Distributions., MATFYZPRESS, Prague 2003. 
  25. Meerschaert, M. M., H.-P.Scheffler, Limit Distributions for Sums of Independent Random Vectors (Heavy Tails in Theory and Practice)., John Wiley and Sons, New York 2001. MR1840531
  26. Meerschaert, M. M., H.-P.Scheffler, Portfolio Modelling with Heavy Tailed Random Vectors., In: Handbook of Heavy Tailed Distributions in Finance (S. T. Rachev, ed.), Elsevier, Amsterdam 2003, pp. 595-640. 
  27. Meerschaert, M. M., H.-P.Scheffler, Portfolio Modeling with Heavy Tailed Random Vectors., In: Handbook of Heavy Tailed Distributions in Finance (S. T. Rachev, ed.), Elsevier, Amsterdam 2003, pp. 595-640. 
  28. Pflug, G. Ch., 10.1007/pl00011398, Math. Program. Ser. B 89 (2001), 251-271. MR1816503DOI10.1007/pl00011398
  29. Pflug, G. Ch., Stochastic Optimization and Statistical Inference., In: Handbooks in Operations Research and Managemennt 10, Stochastic Programming (A. Ruszczynski and A. A. Shapiro, eds.) Elsevier, Amsterdam 2003, pp. 427-480. MR2052759
  30. Pflug, G. Ch., Römisch, W., Modeling Measuring and Managing Risk., World Scientific Publishing Co. Pte. Ltd, New Jersey 2007. Zbl1153.91023MR2424523
  31. Rachev, S. T., Römisch, W., 10.1287/moor.27.4.792.304, Math. Oper. Res. 27 (2002), 792-818. MR1939178DOI10.1287/moor.27.4.792.304
  32. Rockafellar, R., Wets, R. J. B., Variational Analysis., Springer, Berlin 1983. Zbl0888.49001
  33. Römisch, W., Wakolbinger, A., Obtaining Convergence Rate for Approximation in Stochastic Programming., In: Parametric Optimization and Related Topics (J. Guddat, H. Th. Jongen, B. Kummer and F. Nožička, eds.), Akademie-Verlag, Berlin 1987, pp. 327-343. MR0909737
  34. Römisch, W., Stability of Stochastic Programming Problems., In: Handbooks in Operations Research and Managemennt Science 10, Stochastic Programming (A. Ruszczynski and A. A. Shapiro, eds.) Elsevier, Amsterdam 2003, pp. 483-554. MR2052760
  35. Salinetti, G., Wets, R. J.-B., 10.1137/1021002, SIAM Rev. 21 (1979), 16-33. MR0516381DOI10.1137/1021002
  36. Samarodnitsky, G., Taqqu, M., Stable Non-Gaussian Random Processes., Chapman and Hall, New York 1994. 
  37. Schulz, R., 10.1137/s1052623494271655, SIAM J. Optim. 6 (1996), 4, 1138-1152. MR1416533DOI10.1137/s1052623494271655
  38. Shapiro, A., 10.1007/bf01582215, Math. Program. 67 (1994), 99-108. Zbl0828.90099MR1300821DOI10.1007/bf01582215
  39. Shapiro, A., Xu, H., 10.1080/02331930801954177, Optimization 57 (2008), 395-418. Zbl1145.90047MR2412074DOI10.1080/02331930801954177
  40. Shapiro, A., Dentcheva, D., Ruszczynski, A., Lectures on Stochastic Programming (Modeling and Theory)., Published by Society for Industrial and Applied Mathematics and Mathematical Programming Society, Philadelphia 2009. Zbl1302.90003MR2562798
  41. Shiryaev, A. N., Essential of Stochastic Finance (Facts, Models, Theory)., World Scientific, New Jersey 2008. MR1695318
  42. Shorack, G. R., Wellner, J. A., Empirical Processes and Applications to Statistics., Wiley, New York 1986. MR0838963
  43. Šmíd, M., 10.1007/s10479-008-0355-9, Ann. Oper. Res. 165 (2009), 1, 29-45. MR2470981DOI10.1007/s10479-008-0355-9
  44. Wets, R. J.-B., A Statistical Approach to the Solution of Stochastic Programs with (Convex) Simple Recourse., Research Report, University of Kentucky 1974. 

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.