Empirical estimates in stochastic optimization via distribution tails

Vlasta Kaňková

Kybernetika (2010)

  • Volume: 46, Issue: 3, page 459-471
  • ISSN: 0023-5954

Abstract

top
“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” ℒ 1 norm and empirical quantiles convergence.

How to cite

top

Kaňková, Vlasta. "Empirical estimates in stochastic optimization via distribution tails." Kybernetika 46.3 (2010): 459-471. <http://eudml.org/doc/196465>.

@article{Kaňková2010,
abstract = {“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.},
author = {Kaňková, Vlasta},
journal = {Kybernetika},
keywords = {stochastic programming problems; stability; Wasserstein metric; $\{\mathcal \{L\}\}_\{1\}$ norm; Lipschitz property; empirical estimates; convergence rate; exponential tails; heavy tails; Pareto distribution; risk functionals; empirical quantiles; stability; Wasserstein metric; empirical estimates; stochastic programming problems; norm; Lipschitz property; convergence rate; exponential tails; heavy tails; Pareto distribution; risk functionals; empirical quantiles},
language = {eng},
number = {3},
pages = {459-471},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Empirical estimates in stochastic optimization via distribution tails},
url = {http://eudml.org/doc/196465},
volume = {46},
year = {2010},
}

TY - JOUR
AU - Kaňková, Vlasta
TI - Empirical estimates in stochastic optimization via distribution tails
JO - Kybernetika
PY - 2010
PB - Institute of Information Theory and Automation AS CR
VL - 46
IS - 3
SP - 459
EP - 471
AB - “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.
LA - eng
KW - stochastic programming problems; stability; Wasserstein metric; ${\mathcal {L}}_{1}$ norm; Lipschitz property; empirical estimates; convergence rate; exponential tails; heavy tails; Pareto distribution; risk functionals; empirical quantiles; stability; Wasserstein metric; empirical estimates; stochastic programming problems; norm; Lipschitz property; convergence rate; exponential tails; heavy tails; Pareto distribution; risk functionals; empirical quantiles
UR - http://eudml.org/doc/196465
ER -

References

top
  1. 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
  2. Dupačová, J., Wets, R. J.-B., 10.1214/aos/1176351052, Ann. Statist. 16 (1984), 1517–1549. MR0964937DOI10.1214/aos/1176351052
  3. Dvoretzky, A., Kiefer, J., Wolfowitz, J., 10.1214/aoms/1177728174, Ann. Math. Statist. 56 (1956). 642–669. MR0083864DOI10.1214/aoms/1177728174
  4. Henrion, R., Römisch, W., Metric regularity and quantitative stability in stochastic programs with probability constraints, Math. Programming 84 (1999), 55–88. MR1687280
  5. Hoeffding, W., 10.1080/01621459.1963.10500830, J. Amer. Statist. Assoc. 58 (1963), 301, 13–30. Zbl0127.10602MR0144363DOI10.1080/01621459.1963.10500830
  6. Kaniovski, Y. M., King, A. J., Wets, R. J.-B., 10.1007/BF02031707, Ann. Oper. Res. 56 (1995), 189–208. Zbl0835.90055MR1339792DOI10.1007/BF02031707
  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. MR0519478
  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. MR1603961
  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. MR2121001
  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. MR2428217
  15. Klebanov, L. B., Heavy Tailed Distributions, Matfyzpress, Prague 2003. 
  16. Konno, H., Yamazaki, H., 10.1287/mnsc.37.5.519, Management Sci. 37 (1991), 5, 519–531. DOI10.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. MR1788152
  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., 10.1007/PL00011398, Math. Program. Ser. B 89 (2001), 251–271. MR1816503DOI10.1007/PL00011398
  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. MR2052759
  24. Pflug, G. Ch., Römisch, W., Modeling Measuring and Managing Risk, World Scientific Publishing Co. Pte. Ltd, New Jersey, 2007. MR2424523
  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. MR2051791
  26. Römisch, W., Schulz, R., 10.1287/moor.18.3.590, Math. Oper. Res. 18 (1993), 590–609. MR1250562DOI10.1287/moor.18.3.590
  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. MR2052760
  28. Salinetti, G., Wets, R. J. B., On the convergence of closed-valued measurable multifunctions, Trans. Amer. Math. Soc. 266 (1981), 1, 275–289. Zbl0501.28005MR0613796
  29. Schulz, R., 10.1137/S1052623494271655, SIAM J. Optim. 6 (1996), 4, 1138–1152. MR1416533DOI10.1137/S1052623494271655
  30. Serfling, J. R., Approximation Theorems of Mathematical Statistics, Wiley, New York 1980. Zbl1001.62005MR0595165
  31. Shapiro, A., 10.1007/BF01582215, Math. Program. 67 (1994), 99–108. Zbl0828.90099MR1300821DOI10.1007/BF01582215
  32. Šmíd, M., 10.1007/s10479-008-0355-9, Ann. Oper. Res. 165 (2009), 29–45. MR2470981DOI10.1007/s10479-008-0355-9
  33. Shorack, G. R., Wellner, J. A., Empirical Processes and Applications to Statistics, Wiley, New York 1986. MR0838963
  34. Wets, R. J.-B., A Statistical Approach to the Solution of Stochastic Programs with (Convex) Simple Recourse, Research Report, University Kentucky, USA 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.