# Article

Full entry | PDF   (0.5 MB)
Keywords:
stochastic programming problems; stability; Wasserstein metric; ${\cal L}_{1}$ norm; Lipschitz property; empirical estimates; convergence rate; exponential tails; heavy tails; Pareto distribution; risk functionals; empirical quantiles
Summary:
“Classical” optimization problems depending on a probability measure belong mostly to nonlinear deterministic optimization problems that are, from the numerical point of view, relatively complicated. On the other hand, these problems fulfil very often assumptions giving a possibility to replace the “underlying” probability measure by an empirical one to obtain “good” empirical estimates of the optimal value and the optimal solution. Convergence rate of these estimates have been studied mostly for “underlying” probability measures with suitable (thin) tails. However, it is known that probability distributions with heavy tails better correspond to many economic problems. The paper focuses on distributions with finite first moments and heavy tails. The introduced assertions are based on the stability results corresponding to the Wasserstein metric with an “underlying” ${\cal L}_{1}$ norm and empirical quantiles convergence.
References:
[1] Dai, L., Chen, C. H., Birge, J. R.: Convergence properties of two-stage stochastic programming. J. Optim. Theory Appl. 106 (2000), 489–509. DOI 10.1023/A:1004649211111 | MR 1797371 | Zbl 0980.90057
[2] Dupačová, J., Wets, R. J.-B.: Asymptotic behaviour of statistical estimates and optimal solutions of stochastic optimization problems. Ann. Statist. 16 (1984), 1517–1549. DOI 10.1214/aos/1176351052 | MR 0964937
[3] Dvoretzky, A., Kiefer, J., Wolfowitz, J.: 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 | MR 0083864
[4] Henrion, R., Römisch, W.: Metric regularity and quantitative stability in stochastic programs with probability constraints. Math. Programming 84 (1999), 55–88. MR 1687280
[5] Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 (1963), 301, 13–30. DOI 10.1080/01621459.1963.10500830 | MR 0144363 | Zbl 0127.10602
[6] Kaniovski, Y. M., King, A. J., Wets, R. J.-B.: Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems. Ann. Oper. Res. 56 (1995), 189–208. DOI 10.1007/BF02031707 | MR 1339792 | Zbl 0835.90055
[7] Kaňková, V.: Optimum solution of a stochastic optimization problem with unknown parameters. In: Trans. Seventh Prague Conference, Academia, Prague 1977, pp. 239–244. MR 0519478
[8] Kaňková, V.: An approximative solution of stochastic optimization problem. In: Trans. Eighth Prague Conference, Academia, Prague 1978, pp. 349–353.
[9] Kaňková, V.: On the stability in stochastic programming: the case of individual probability constraints. Kybernetika 33 (1997), 5, 525–546. MR 1603961
[10] Kaňková, V.: Unemployment problem, restructuralization and stochastic programming. In: Proc. Mathematical Methods in Economics 1999 (J. Plešingr, ed.), Czech Society for Operations Research and University of Economics Prague, Jindřichův Hradec, pp. 151–158.
[11] Kaňková, V., Šmíd, M.: On approximation in multistage stochastic programs: Markov dependence. Kybernetika 40 (2004), 5, 625–638. MR 2121001
[12] 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.
[13] Kaňková, V.: Empirical Estimates via Stability in Stochastic Programming. Research Report ÚTIA AV ČR No. 2192, Prague 2007.
[14] Kaňková, V.: Multistage stochastic programs via autoregressive sequences and individual probability constraints. Kybernetika 44 (2008), 2, 151–170. MR 2428217
[15] Klebanov, L. B.: Heavy Tailed Distributions. Matfyzpress, Prague 2003.
[16] Konno, H., Yamazaki, H.: Mean-absolute deviation portfolio optimization model and its application to Tokyo stock markt. Management Sci. 37 (1991), 5, 519–531. DOI 10.1287/mnsc.37.5.519
[17] Kotz, S., Balakrishnan, N., Johnson, N. L.: Continuous Multiviariate Distributions. Volume 1: Models and Applications. Wiley, New York 2000. MR 1788152
[18] Kozubowski, T. J. , Panorska, A. K., Rachev, S. T. : Statistical issues in modeling stable portfolios. In: Handbook of Heavy Tailed Distributions in Finance (S. T. Rachev, ed.), Elsevier, Amsterdam 2003, pp. 131–168.
[19] Homen de Mello, T.: On rates of convergence for stochastic optimization problems under non-i.i.d. sampling. SIAM J. Optim. 19 (2009), 2, 524–551.
[20] Meerschaert, M. M., Scheffler, H.-P.: 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.
[21] Omelchenko, V.: Stable Distributions and Application to Finance. Diploma Thesis (supervisor L. Klebanov), Faculty of Mathematics and Physics, Charles University Prague, Prague 2007.
[22] Pflug, G. Ch.: Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Program. Ser. B 89 (2001), 251–271. DOI 10.1007/PL00011398 | MR 1816503
[23] Pflug, G. Ch.: Stochastic optimization and statistical inference. In: Stochastic Programming (Handbooks in Operations Research and Management Science, Vol. 10, A. Ruszczynski and A. A. Shapiro, eds.), Elsevier, Amsterdam 2003, pp. 427–480. MR 2052759
[24] Pflug, G. Ch., Römisch, W.: Modeling Measuring and Managing Risk. World Scientific Publishing Co. Pte. Ltd, New Jersey, 2007. MR 2424523
[25] Prékopa, A.: Probabilistic programming. In: Stochastic Programming, (Handbooks in Operations Research and Managemennt Science, Vol. 10, (A. Ruszczynski and A. A. Shapiro, eds.), Elsevier, Amsterdam 2003, pp. 267–352. MR 2051791
[26] Römisch, W., Schulz, R.: Stability of solutions for stochastic programs with complete recourse. Math. Oper. Res. 18 (1993), 590–609. DOI 10.1287/moor.18.3.590 | MR 1250562
[27] Römisch, W.: Stability of stochastic programming problems. In: Stochastic Programming, Handbooks in Operations Research and Managemennt Science, Vol 10 (A. Ruszczynski and A. A. Shapiro, eds.), Elsevier, Amsterdam 2003, pp. 483–554. MR 2052760
[28] Salinetti, G., Wets, R. J. B.: On the convergence of closed-valued measurable multifunctions. Trans. Amer. Math. Soc. 266 (1981), 1, 275–289. MR 0613796 | Zbl 0501.28005
[29] Schulz, R.: Rates of convergence in stochastic programs with complete integer recourse. SIAM J. Optim. 6 (1996), 4, 1138–1152. DOI 10.1137/S1052623494271655 | MR 1416533
[30] Serfling, J. R.: Approximation Theorems of Mathematical Statistics. Wiley, New York 1980. MR 0595165 | Zbl 1001.62005
[31] Shapiro, A.: Quantitative stability in stochastic programming. Math. Program. 67 (1994), 99–108. DOI 10.1007/BF01582215 | MR 1300821 | Zbl 0828.90099
[32] Šmíd, M.: The expected loss in the discretization of multistage stochastic programming problems-estimation and convergence rate. Ann. Oper. Res. 165 (2009), 29–45. DOI 10.1007/s10479-008-0355-9 | MR 2470981
[33] Shorack, G. R., Wellner, J. A.: Empirical Processes and Applications to Statistics. Wiley, New York 1986. MR 0838963
[34] Wets, R. J.-B.: A Statistical Approach to the Solution of Stochastic Programs with (Convex) Simple Recourse. Research Report, University Kentucky, USA 1974.

Partner of