Previous |  Up |  Next


multistage stochastic programming; scenarios; discrete approximation
We propose two methods to solve multistage stochastic programs when only a (large) finite set of scenarios is available. The usual scenario tree construction to represent non-anticipativity constraints is replaced by alternative discretization schemes coming from non-parametric estimation ideas. In the first method, a penalty term is added to the objective so as to enforce the closeness between decision variables and the Nadaraya–Watson estimation of their conditional expectation. A numerical application of this approach on an hydro-power plant management problem is developed. The second method exploits the interpretation of kernel estimators as a sum of basis functions.
[1] Babuska I., Melenk J.: The partition of unity method. International Journal for Numerical Methods in Engineering 40 (1998), 727–758 MR 1429534
[2] Barty K.: Contributions à la discrétisation des contraintes de mesurabilité pour les problčmes d’optimisation stochastiques. PhD. Thesis, Ecole nationale des ponts et chaussées, 2004
[3] Cohen G.: Optimal scenario tree topology and corresponding rate of convergence. In: Proc. 11th Conference on Stochastic Programming, 2007
[4] Dallagi A.: Méthodes particulaires en commande optimale stochastique. PhD. Thesis, Université Paris I, 2007
[5] Devroye L. P.: On the almost everywhere convergence of nonparametric regression function estimates. Ann. Statist. 9 (1981), 1310–1319 MR 0630113 | Zbl 0477.62025
[6] Devroye L. P., Wagner T.: Distribution-free consistency results in nonparametric discrimination and regression function estimation. Ann. Statist. 8 (1980), 231–239 MR 0560725 | Zbl 0431.62025
[7] Gröwe-Kuska N., Heitsch, H., Römisch W.: Scenario reduction and scenario tree construction for power management problem. In: Power Tech Conference Proceedings, IEEE Bologna, 2003
[8] Heitsch H., Römisch W.: Generation of multivariate scenario trees to model stochasticity in power management. IEEE St. Petersburg Power Tech 2005, 2005
[9] Heitsch H., Römisch W.: Scenario Tree Modeling for Multistage Stochastic Programs. Preprint Humboldt-University Berlin, Institute of Mathematics, 2005 MR 2470797 | Zbl 1173.90007
[10] Nadaraya E.: On estimating regression. Theory Probab. Appl. 9 (1964), 141–142 Zbl 0136.40902
[11] Pennanen T.: Epi-convergent discretizations of multistage stochastic programs. Math. Oper. Res. 30 (2005), 245–256 MR 2125146 | Zbl 1165.90014
[12] Spiegelman C., Sacks J.: Consistent window estimation in nonparametric regression. Ann. Statist. 8 (1980), 240–246 MR 0560726 | Zbl 0432.62066
[13] Watson G.: Smooth regression analysis. Sankhya Ser. A 26 (1964), 359–372 MR 0185765 | Zbl 0137.13002
Partner of
EuDML logo