[en] We propose a generic method for obtaining quickly good upper bounds on the minimal value of a multistage stochastic program. The method is based on the simulation of a feasible decision policy, synthesized by a strategy relying on any scenario tree approximation from stochastic programming and on supervised learning techniques from machine learning.
Disciplines :
Computer science
Author, co-author :
Defourny, Boris ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Dép. d'électric., électron. et informat. (Inst.Montefiore)
Ernst, Damien ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Wehenkel, Louis ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Language :
English
Title :
Bounds for Multistage Stochastic Programs using Supervised Learning Strategies
Publication date :
2009
Event name :
Stochastic Algorithms: Foundations and Applications. Fifth International Symposium, SAGA 2009
Event organizer :
Hokkaido University
Event place :
Sapporo, Japan
Event date :
October 26-28, 2009
Audience :
International
Main work title :
Stochastic Algorithms: Foundations and Applications
This paper presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office.
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Frauendorfer, K.: Barycentric scenario trees in convex multistage stochastic programming. Mathematical Programming 75, 277-294 (1996)
Dempster, M.: Sequential importance sampling algorithms for dynamic stochastic programming. Annals of Operations Research 84, 153-184 (1998)
Dupacova, J., Consigli, G., Wallace, S.: Scenarios for multistage stochastic programs. Annals of Operations Research 100, 25-53 (2000)
Høyland, K., Wallace, S.: Generating scenario trees for multistage decision problems. Management Science 47(2), 295-307 (2001)
Shapiro, A.: Monte Carlo sampling methods. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10, pp. 353-425. Elsevier, Amsterdam (2003)
Casey, M., Sen, S.: The scenario generation algorithm for multistage stochastic linear programming. Mathematics of Operations Research 30, 615-631 (2005)
Hochreiter, R., Pflug, G.: Financial scenario generation for stochastic multistage decision processes as facility location problems. Annals of Operations Research 152, 257-272 (2007)
Pennanen, T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Mathematical Programming 116, 461-479 (2009)
Heitsch, H., Römisch, W.: Scenario tree modeling for multistage stochastic programs. Mathematical Programming 118(2), 371-406 (2009)
Shapiro, A.: On complexity of multistage stochastic programs. Operations Research Letters 34(1), 1-8 (2006)
Shapiro, A.: Inference of statistical bounds for multistage stochastic programming problems. Mathematical Methods of Operations Research 58(1), 57-68 (2003)
Golub, B., Holmer, M., McKendall, R., Pohlman, L., Zenios, S.: A stochastic programming model for money management. European Journal of Operational Research 85, 282-296 (1995)
Kouwenberg, R.: Scenario generation and stochastic programming models for asset liability management. European Journal of Operational Research 134, 279-292 (2001)
Hilli, P., Pennanen, T.: Numerical study of discretizations of multistage stochastic programs. Kybernetika 44, 185-204 (2008)
Billingsley, P.: Probability and Measure, 3rd edn. Wiley, Chichester (1995)
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd edn. Springer, Heidelberg (2009)
Wahba, G., Golub, G., Heath, M.: Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics 21, 215-223 (1979)
Efron, B., Tibshirani, R.: An introduction to the bootstrap. Chapman and Hall, London (1993)
Thénié, J., Vial, J.P.: Step decision rules for multistage stochastic programming: A heuristic approach. Automatica 44, 1569-1584 (2008)
Küchler, C., Vigerske, S.: Numerical evaluation of approximation methods in stochastic programming (2008) (submitted)
Cover, T.: Estimation by the nearest neighbor rule. IEEE Transactions on Information Theory 14, 50-55 (1968)
Akaike, H.: Information theory and an extension of the maximum likelihood principle. In: Proceedings of the Second International Symposium on Information Theory, pp. 267-281 (1973)
Schwartz, G.: Estimating the dimension of a model. Annals of Statistics 6, 461-464 (1978)
Rissanen, J.: Stochastic complexity and modeling. Annals of Statistics 14, 1080-1100 (1986)
James, G., Radchenko, P., Lv, J.: DASSO: connections between the Dantzig selector and Lasso. Journal of the Royal Statistical Society: Series B 71, 127-142 (2009)
Chapelle, O., Vapnik, V., Bengio, Y.: Model selection for small sample regression. Machine Learning 48, 315-333 (2002)
Huber, P.: Projection pursuit. Annals of Statistics 13, 435-475 (1985)
Buja, A., Hastie, T., Tibshirani, R.: Linear smoothers and additive models. Annals of Statistics 17, 453-510 (1989)
Girosi, F., Jones, M., Poggio, T.: Regularization theory and neural networks architectures. Neural Computation 7, 219-269 (1995)
Williams, C., Rasmussen, C.: Gaussian processes for regression. In: Advances in Neural Information Processing Systems 8 (NIPS 1995), pp. 514-520 (1996)
Smola, A., Schölkopf, B., Müller, K.R.: The connection between regularization operators and support vector kernels. Neural Networks 11, 637-649 (1998) (Pubitemid 28400264)
Bertsekas, D., Tsitsiklis, J.: Neuro-Dynamic Programming. Athena Scientific, Belmont (1996)
Sutton, R., Barto, A.: Reinforcement Learning, an introduction. MIT Press, Cambridge (1998)
Bagnell, D., Kakade, S., Ng, A., Schneider, J.: Policy search by dynamic programming. In: Advances in Neural Information Processing Systems 16 (NIPS 2003), pp. 831-838 (2004)
Lagoudakis, M., Parr, R.: Reinforcement learning as classification: leveraging modern classifiers. In: Proceedings of the Twentieth International Conference on Machine Learning (ICML 2003), pp. 424-431 (2003)
Ernst, D., Geurts, P., Wehenkel, L.: Tree-based batch mode reinforcement learning. Journal of Machine Learning Research 6, 503-556 (2005)
Langford, J., Zadrozny, B.: Relating reinforcement learning performance to classification performance. In: Proceedings of the Twenty-Second International Conference on Machine Learning (ICML 2005), pp. 473-480 (2005)
Fern, A., Yoon, S., Givan, R.: Approximate policy iteration with a policy language bias: solving relational Markov Decision Processes. Journal of Artificial Intelligence Research 25, 85-118 (2006)
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
