Geodesic
Empirical estimates in stochastic optimization via distribution tails
Kybernetika, Tome 46 (2010) no. 3, pp. 459-471 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

“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.
“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.
Classification : 60B10, 90C15
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 
@article{KYB_2010_46_3_a10,
     author = {Ka\v{n}kov\'a, Vlasta},
     title = {Empirical estimates in stochastic optimization via distribution tails},
     journal = {Kybernetika},
     pages = {459--471},
     year = {2010},
     volume = {46},
     number = {3},
     mrnumber = {2676083},
     zbl = {1225.90092},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2010_46_3_a10/}
}
TY  - JOUR
AU  - Kaňková, Vlasta
TI  - Empirical estimates in stochastic optimization via distribution tails
JO  - Kybernetika
PY  - 2010
SP  - 459
EP  - 471
VL  - 46
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/KYB_2010_46_3_a10/
LA  - en
ID  - KYB_2010_46_3_a10
ER  - 
%0 Journal Article
%A Kaňková, Vlasta
%T Empirical estimates in stochastic optimization via distribution tails
%J Kybernetika
%D 2010
%P 459-471
%V 46
%N 3
%U http://geodesic.mathdoc.fr/item/KYB_2010_46_3_a10/
%G en
%F KYB_2010_46_3_a10
Kaňková, Vlasta. Empirical estimates in stochastic optimization via distribution tails. Kybernetika, Tome 46 (2010) no. 3, pp. 459-471. http://geodesic.mathdoc.fr/item/KYB_2010_46_3_a10/

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

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

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

[4] Henrion, R., Römisch, W.: Metric regularity and quantitative stability in stochastic programs with probability constraints. Math. Programming 84 (1999), 55–88. | MR

[5] Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 (1963), 301, 13–30. | DOI | MR | Zbl

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

[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

[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

[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

[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

[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

[17] Kotz, S., Balakrishnan, N., Johnson, N. L.: Continuous Multiviariate Distributions. Volume 1: Models and Applications. Wiley, New York 2000. | MR

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

[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

[24] Pflug, G. Ch., Römisch, W.: Modeling Measuring and Managing Risk. World Scientific Publishing Co. Pte. Ltd, New Jersey, 2007. | MR

[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

[26] Römisch, W., Schulz, R.: Stability of solutions for stochastic programs with complete recourse. Math. Oper. Res. 18 (1993), 590–609. | DOI | MR

[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

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

[29] Schulz, R.: Rates of convergence in stochastic programs with complete integer recourse. SIAM J. Optim. 6 (1996), 4, 1138–1152. | DOI | MR

[30] Serfling, J. R.: Approximation Theorems of Mathematical Statistics. Wiley, New York 1980. | MR | Zbl

[31] Shapiro, A.: Quantitative stability in stochastic programming. Math. Program. 67 (1994), 99–108. | DOI | MR | Zbl

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

[33] Shorack, G. R., Wellner, J. A.: Empirical Processes and Applications to Statistics. Wiley, New York 1986. | MR

[34] Wets, R. J.-B.: A Statistical Approach to the Solution of Stochastic Programs with (Convex) Simple Recourse. Research Report, University Kentucky, USA 1974.