Geodesic
On approximation in multistage stochastic programs: Markov dependence
Kybernetika, Tome 40 (2004) no. 5, pp. 625-638 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

A general multistage stochastic programming problem can be introduced as a finite system of parametric (one-stage) optimization problems with an inner type of dependence. Evidently, this type of the problems is rather complicated and, consequently, it can be mostly solved only approximately. The aim of the paper is to suggest some approximation solution schemes. To this end a restriction to the Markov type of dependence is supposed.
A general multistage stochastic programming problem can be introduced as a finite system of parametric (one-stage) optimization problems with an inner type of dependence. Evidently, this type of the problems is rather complicated and, consequently, it can be mostly solved only approximately. The aim of the paper is to suggest some approximation solution schemes. To this end a restriction to the Markov type of dependence is supposed.
Classification : 60K30, 90C15, 90C59
Keywords: multistage stochastic programming problem; approximation solution scheme; deterministic approximation; empirical estimate; Markov dependence 
@article{KYB_2004_40_5_a7,
     author = {Ka\v{n}kov\'a, Vlasta and \v{S}m{\'\i}d, Martin},
     title = {On approximation in multistage stochastic programs: {Markov} dependence},
     journal = {Kybernetika},
     pages = {625--638},
     year = {2004},
     volume = {40},
     number = {5},
     mrnumber = {2121001},
     zbl = {1249.90183},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2004_40_5_a7/}
}
TY  - JOUR
AU  - Kaňková, Vlasta
AU  - Šmíd, Martin
TI  - On approximation in multistage stochastic programs: Markov dependence
JO  - Kybernetika
PY  - 2004
SP  - 625
EP  - 638
VL  - 40
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/KYB_2004_40_5_a7/
LA  - en
ID  - KYB_2004_40_5_a7
ER  - 
%0 Journal Article
%A Kaňková, Vlasta
%A Šmíd, Martin
%T On approximation in multistage stochastic programs: Markov dependence
%J Kybernetika
%D 2004
%P 625-638
%V 40
%N 5
%U http://geodesic.mathdoc.fr/item/KYB_2004_40_5_a7/
%G en
%F KYB_2004_40_5_a7
Kaňková, Vlasta; Šmíd, Martin. On approximation in multistage stochastic programs: Markov dependence. Kybernetika, Tome 40 (2004) no. 5, pp. 625-638. http://geodesic.mathdoc.fr/item/KYB_2004_40_5_a7/

[1] Anděl J.: Mathematical Statistics (in Czech). SNTL, Prague 1985

[2] Dal L., Chen C. H., Birge J. R.: Convergence properties of two-stage stochastic programming. J. Optim. Theory Appl. 106 (2000), 3, 489–509 | DOI | MR

[3] 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

[4] Dupačová J.: Multistage stochastic programs: The state-of-the-art and selected bibliography. Kybernetika 31 (1995), 151–174 | MR | Zbl

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

[6] Houda M.: Stability and Estimates in Stochastic Programming (Special Cases) (in Czech). Diploma Work. Faculty of Mathematics and Physics, Charles University, Prague 2001

[7] Kaňková V.: An approximative solution of stochastic optimization problem. In: Trans. Eighth Prague Conference, Academia, Prague 1978, pp. 349–353

[8] Kaňková V.: Approximative solution of problems of two–stage stochastic nonlinear programming (in Czech). Ekonomicko–matematický obzor 16 (1980), 1, 64–76 | MR

[9] Kaňková V., Lachout P.: Convergence rate of empirical estimates in stochastic programming. Informatica 3 (1992), 4, 497–522 | MR | Zbl

[10] Kaňková V.: A note on estimates in stochastic programming. J. Comput. Math. 56 (1994), 97–112 | DOI | MR

[11] Kaňková V.: A note on multistage stochastic programming. In: Proc. 11th joint Czech–Germany–Slovak Conference: Mathematical Methods in Economy and Industry. University of Technology, Liberec (Czech Republic) 1998, pp. 45–52

[12] Kaňková V.: A remark on the analysis of multistage stochastic programs: Markov dependence. Z. angew. Math. Mech. 82 (2002), 11–12, 781–793 | MR | Zbl

[13] Kaňková V.: A remark on empirical estimates in multistage stochastic programming. Bulletin of the Czech Econometric Society 17/2002, 32–51

[14] Kaňková V., Šmíd M.: A Remark on Approximation in Multistage Stochastic Programs; Markov Dependence. Research Report ÚTIA AS CR, No. 2102, July 2004 | MR

[15] Pfug G. Ch.: Optimization of Stochastic Models; The Interface Between Simulation and Optimization. Kluwer, London 1996 | MR

[16] Prékopa A.: Stochastic Programming. Kluwer, Dordrecht and Académiai Kiadó, Budapest 1995 | MR | Zbl

[17] Rachev S. T.: Probability Metrics and the Stability of Stochastic Models. Wiley, Chichester 1991 | MR | Zbl

[18] Römisch W., Wakolbinger A.: Obtaining convergence rate for approximations in stochastic programming. In: Parametric Optimization and Related Topics (J. Guddat, ed.), Akademie Verlag, Berlin 1987, pp. 327–343 | MR

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

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

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

[22] Šmíd M.: Notes on Approximate Computation of Expectation. Research Report ÚTIA AS CR, No. 2077, May 2003

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

[24] Vallander S. S.: Calculation of the Wasserstein distance between probability distributions on the line (in Russian). Theor. Prob. Appl. 18 (1973), 783–76 | MR

[25] Vogel S.: On stability in multiobjective programming – a stochastic approach. Math. Programming 56 (1992), 91–119 | DOI | MR | Zbl

[26] Wang J.: Continuity of the feasible solution sets of probabilistic constrained programs. J. Optim. Theory Appl. 63 (1994), 1, 79–89 | DOI | MR