Kybernetika 51 no. 3, 433-456, 2015

Thin and heavy tails in stochastic programming

Vlasta Kaňková and Michal HoudaDOI: 10.14736/kyb-2015-3-0433

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 \cite {Meer 2003)} while nonlinear dependence frequently appears in problems with risk measures \cite {Kan (2012a),Pflu (2007)}. The results we introduce follow mostly from the stability results based on the Wasserstein metric with the "underlying" $ {\cal L}_{1}$ norm. Theoretical results are completed by a simulation investigation.

Keywords:

stability, stochastic dominance, Wasserstein metric, empirical estimates, stochastic programming problems, Lipschitz property, convergence rate, ${\cal L}_{1}$ norm, linear and nonlinear dependence, probability and risk constraints

Classification:

90C15

References:

  1. E. Barrio, E. Giné and E. Matrán: Central limit theorems for a Wasserstein distance between empirical and the true distributions. Ann. Probab. 27 (1999), 2, 1009-1071.   DOI:10.1214/aop/1022677394
  2. P. Billingsley: Ergodic Theory and Information. John Wiley and Sons, New York 1965.   CrossRef
  3. J. R. Birge and F. Louveaux: Introduction in Stochastic Programming. Springer, Berlin 1992.   CrossRef
  4. L. Dai, C.-H. Chen and J. R. Birge: Convergence properties of two-stage stochastic programming. J. Optim. Theory Appl. 106 (2000), 489-509.   DOI:10.1023/a:1004649211111
  5. D. Dentcheva and A. Ruszczynski: Porfolio optimization with stochastic dominance constraints. J. Banking and Finance 30 (2006), 433-451.   DOI:10.1016/j.jbankfin.2005.04.024
  6. J. Dupačová and R. J. B.Wets: Asymptotic behaviour of statistical estimates and optimal solutions of stochastic optimization problems. Ann. Statist. 16 (1984), 1517-1549.   DOI:10.1214/aos/1176351052
  7. A. Dvoretzky, J. Kiefer and J. Wolfowitz: Asymptotic minimax character of the sample distribution function and the classical multinomial estimate. Ann. Math. Statist. 56 (1956), 642-669.   DOI:10.1214/aoms/1177728174
  8. Y. M. Ermoliev and V. Norkin: Sample everage approximation method for compound stochastic optimization problems. SIAM J. Optim. 23 (2013), 4, 2231-2263.   DOI:10.1137/120863277
  9. A. Gut: Probability: A Graduate Course. Springer, New York 2005.   CrossRef
  10. M. Houda: Stability and Approximations for Stochastic Programs. Doctoral Thesis, Faculty of Mathematics and Physics, Charles University Prague, Prague 2009.   CrossRef
  11. M. Houda and V. Kaňková: Empirical estimates in economic and financial optimization problems. Bull. Czech Econometr. Soc. 19 (2012), 29, 50-69.   CrossRef
  12. Y. M. Kaniovski, A. J. King and R. J.-B. Wets: Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems. Ann. Oper. Res. 56 (1995), 189-208.   DOI:10.1007/bf02031707
  13. V. Kaňková: Optimum solution of a stochastic optimization problem. In: Trans. 7th Prague Conf. 1974, Academia, Prague 1977, pp. 239-244.   CrossRef
  14. V. Kaňková: An approximative solution of stochastic optimization problem. In: Trans. 8th Prague Conf., Academia, Prague 1978, pp. 349-353.   CrossRef
  15. V. Kaňková and P. Lachout: Convergence rate of empirical estimates in stochastic programming. Informatica 3 (1992), 4, 497-523.   CrossRef
  16. V. Kaňková: Stability in stochastic programming - the case of unknown location parameter. Kybernetika 29 (1993), 1, 97-112.   CrossRef
  17. V. Kaňková: A note on estimates in stochastic programming. J. Comput. Appl. Math. 56 (1994), 97-112.   DOI:10.1016/0377-0427(94)90381-6
  18. V. Kaňková: On the stability in stochastic programming: the case of individual probability constraints. Kybernetika 33 (1997), 5, 525-544.   CrossRef
  19. V. Kaňková and M. Houda: Empirical estimates in stochastic programming. In: Proc. Prague Stochastics 2006 (M. Hušková and M. Janžura, eds.), MATFYZPRESS, Prague 2006, pp. 426-436.   CrossRef
  20. V. Kaňková and M. Houda: Dependent samples in empirical estimation of stochastic programming problems. Austrian J. Statist. 35 (2006), 2 - 3, 271-279.   CrossRef
  21. V. Kaňková: Empirical estimates in stochastic programming via distribution tails. Kybernetika 46 (2010), 3, 459-471.   CrossRef
  22. V. Kaňková: Empirical estimates in optimization problems: survey with special regard to heavy tails and dependent samples. Bull. Czech Econometr. Soc. 19 (2012), 30, 92-111.   CrossRef
  23. V. Kaňková: Risk measures in optimization problems via empirical estimates. Czech Econom. Rev. VII (2013), 3, 162-177.   CrossRef
  24. L. B. Klebanov: Heavy Tailed Distributions. MATFYZPRESS, Prague 2003.   CrossRef
  25. M. M. Meerschaert and H.-P.Scheffler: Limit Distributions for Sums of Independent Random Vectors (Heavy Tails in Theory and Practice). John Wiley and Sons, New York 2001.   CrossRef
  26. M. M. Meerschaert and 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.   CrossRef
  27. M. M. Meerschaert and 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.   CrossRef
  28. G. Ch. Pflug: Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Program. Ser. B 89 (2001), 251-271.   DOI:10.1007/pl00011398
  29. G. Ch. Pflug: 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.   CrossRef
  30. G. Ch. Pflug and W. Römisch: Modeling Measuring and Managing Risk. World Scientific Publishing Co. Pte. Ltd, New Jersey 2007.   CrossRef
  31. S. T. Rachev and W. Römisch: Quantitative stability and stochastic programming: the method of probabilistic metrics. Math. Oper. Res. 27 (2002), 792-818.   DOI:10.1287/moor.27.4.792.304
  32. R. Rockafellar and R. J. B. Wets: Variational Analysis. Springer, Berlin 1983.   CrossRef
  33. W. Römisch and A. Wakolbinger: 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.   CrossRef
  34. W. Römisch: 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.   CrossRef
  35. G. Salinetti and R. J.-B. Wets: On the convergence of sequence of convex sets in finite dimensions. SIAM Rev. 21 (1979), 16-33.   DOI:10.1137/1021002
  36. G. Samarodnitsky and M. Taqqu: Stable Non-Gaussian Random Processes. Chapman and Hall, New York 1994.   CrossRef
  37. R. Schulz: Rates of convergence in stochastic programs with complete integer recourse. SIAM J. Optim. 6 (1996), 4, 1138-1152.   DOI:10.1137/s1052623494271655
  38. A. Shapiro: Quantitative stability in stochastic programming. Math. Program. 67 (1994), 99-108.   DOI:10.1007/bf01582215
  39. A. Shapiro and H. Xu: Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation. Optimization 57 (2008), 395-418.   DOI:10.1080/02331930801954177
  40. A. Shapiro, D. Dentcheva and A. Ruszczynski: Lectures on Stochastic Programming (Modeling and Theory). Published by Society for Industrial and Applied Mathematics and Mathematical Programming Society, Philadelphia 2009.   CrossRef
  41. A. N. Shiryaev: Essential of Stochastic Finance (Facts, Models, Theory). World Scientific, New Jersey 2008.   CrossRef
  42. G. R. Shorack and J. A. Wellner: Empirical Processes and Applications to Statistics. Wiley, New York 1986.   CrossRef
  43. M. Šmíd: The expected loss in the discretezation of multistage stochastic programming problems - estimation and convergence rate. Ann. Oper. Res. 165 (2009), 1, 29-45.   DOI:10.1007/s10479-008-0355-9
  44. R. J.-B. Wets: A Statistical Approach to the Solution of Stochastic Programs with (Convex) Simple Recourse. Research Report, University of Kentucky 1974.   CrossRef