Empirical estimates in stochastic optimization via distribution tails. (English) Zbl 1225.90092

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” \( {\mathcal L}_{1}\) norm and empirical quantiles convergence.


90C15 Stochastic programming
Full Text: EuDML Link


[1] Dai, L., Chen, C. H., Birge, J. R.: Convergence properties of two-stage stochastic programming. J. Optim. Theory Appl. 106 (2000), 489-509. · 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. · Zbl 0667.62018
[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. · Zbl 0073.14603
[4] Henrion, R., Römisch, W.: Metric regularity and quantitative stability in stochastic programs with probability constraints. Math. Programming 84 (1999), 55-88. · Zbl 1050.90534
[5] Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 (1963), 301, 13-30. · 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. · Zbl 0835.90055
[7] Kaňková, V.: Optimum solution of a stochastic optimization problem with unknown parameters. Trans. Seventh Prague Conference, Academia, Prague 1977, pp. 239-244.
[8] Kaňková, V.: An approximative solution of stochastic optimization problem. 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. · Zbl 0908.90198
[10] Kaňková, V.: Unemployment problem, restructuralization and stochastic programming. Proc. Mathematical Methods in Economics 1999 (J. Plešingr, 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. · Zbl 1249.90183
[12] Kaňková, V., Houda, M.: Empirical estimates in stochastic programming. Proc. Prague Stochastics 2006 (M. Hušková and M. Janžura, 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. · Zbl 1154.90557
[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.
[17] Kotz, S., Balakrishnan, N., Johnson, N. L.: Continuous Multiviariate Distributions. Volume 1: Models and Applications. Wiley, New York 2000.
[18] Kozubowski, T. J. , Panorska, A. K., Rachev, S. T. : Statistical issues in modeling stable portfolios. Handbook of Heavy Tailed Distributions in Finance (S. T. Rachev, 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. Handbook of Heavy Tailed Distributions in Finance (S. T. Rachev, 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. · Zbl 0987.91034
[23] Pflug, G. Ch.: Stochastic optimization and statistical inference. Stochastic Programming (Handbooks in Operations Research and Management Science, Vol. 10, A. Ruszczynski and A. A. Shapiro, Elsevier, Amsterdam 2003, pp. 427-480.
[24] Pflug, G. Ch., Römisch, W.: Modeling Measuring and Managing Risk. World Scientific Publishing Co. Pte. Ltd, New Jersey, 2007. · Zbl 1153.91023
[25] Prékopa, A.: Probabilistic programming. Stochastic Programming, (Handbooks in Operations Research and Managemennt Science, Vol. 10, (A. Ruszczynski and A. A. Shapiro, Elsevier, Amsterdam 2003, pp. 267-352.
[26] Römisch, W., Schulz, R.: Stability of solutions for stochastic programs with complete recourse. Math. Oper. Res. 18 (1993), 590-609. · Zbl 0797.90070
[27] Römisch, W.: Stability of stochastic programming problems. Stochastic Programming, Handbooks in Operations Research and Managemennt Science, Vol 10 (A. Ruszczynski and A. A. Shapiro, Elsevier, Amsterdam 2003, pp. 483-554.
[28] Salinetti, G., Wets, R. J. B.: On the convergence of closed-valued measurable multifunctions. Trans. Amer. Math. Soc. 266 (1981), 1, 275-289. · Zbl 0501.28005
[29] Schulz, R.: Rates of convergence in stochastic programs with complete integer recourse. SIAM J. Optim. 6 (1996), 4, 1138-1152. · Zbl 0868.90088
[30] Serfling, J. R.: Approximation Theorems of Mathematical Statistics. Wiley, New York 1980. · Zbl 1001.62005
[31] Shapiro, A.: Quantitative stability in stochastic programming. Math. Program. 67 (1994), 99-108. · 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. · Zbl 1163.90676
[33] Shorack, G. R., Wellner, J. A.: Empirical Processes and Applications to Statistics. Wiley, New York 1986. · Zbl 1170.62365
[34] Wets, R. J.-B.: A Statistical Approach to the Solution of Stochastic Programs with (Convex) Simple Recourse. Research Report, University Kentucky, USA 1974.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.