The Markov chain Monte Carlo approach to importance sampling in stochastic programming
Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2012.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/85220 |
| _version_ | 1811096570001620992 |
|---|---|
| author | Ustun, Berk (Tevfik Berk) |
| author2 | Mort Webster |
| author_facet | Mort Webster Ustun, Berk (Tevfik Berk) |
| author_sort | Ustun, Berk (Tevfik Berk) |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2012. |
| first_indexed | 2024-09-23T16:45:26Z |
| format | Thesis |
| id | mit-1721.1/85220 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:45:26Z |
| publishDate | 2014 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/852202019-04-11T07:01:31Z The Markov chain Monte Carlo approach to importance sampling in stochastic programming Ustun, Berk (Tevfik Berk) Mort Webster Massachusetts Institute of Technology. Computation for Design and Optimization Program. Massachusetts Institute of Technology. Computation for Design and Optimization Program. Computation for Design and Optimization Program. Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2012. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 85-87). Stochastic programming models are large-scale optimization problems that are used to facilitate decision-making under uncertainty. Optimization algorithms for such problems need to evaluate the expected future costs of current decisions, often referred to as the recourse function. In practice, this calculation is computationally difficult as it involves the evaluation of a multidimensional integral whose integrand is an optimization problem. Accordingly, the recourse function is estimated using quadrature rules or Monte Carlo methods. Although Monte Carlo methods present numerous computational benefits over quadrature rules, they require a large number of samples to produce accurate results when they are embedded in an optimization algorithm. We present an importance sampling framework for multistage stochastic programming that can produce accurate estimates of the recourse function using a fixed number of samples. Our framework uses Markov Chain Monte Carlo and Kernel Density Estimation algorithms to create a non-parametric importance sampling distribution that can form lower variance estimates of the recourse function. We demonstrate the increased accuracy and efficiency of our approach using numerical experiments in which we solve variants of the Newsvendor problem. Our results show that even a simple implementation of our framework produces highly accurate estimates of the optimal solution and optimal cost for stochastic programming models, especially those with increased variance, multimodal or rare-event distributions. by Berk Ustun. S.M. 2014-03-05T15:55:58Z 2014-03-05T15:55:58Z 2012 2012 Thesis http://hdl.handle.net/1721.1/85220 870969873 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 87 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Computation for Design and Optimization Program. Ustun, Berk (Tevfik Berk) The Markov chain Monte Carlo approach to importance sampling in stochastic programming |
| title | The Markov chain Monte Carlo approach to importance sampling in stochastic programming |
| title_full | The Markov chain Monte Carlo approach to importance sampling in stochastic programming |
| title_fullStr | The Markov chain Monte Carlo approach to importance sampling in stochastic programming |
| title_full_unstemmed | The Markov chain Monte Carlo approach to importance sampling in stochastic programming |
| title_short | The Markov chain Monte Carlo approach to importance sampling in stochastic programming |
| title_sort | markov chain monte carlo approach to importance sampling in stochastic programming |
| topic | Computation for Design and Optimization Program. |
| url | http://hdl.handle.net/1721.1/85220 |
| work_keys_str_mv | AT ustunberktevfikberk themarkovchainmontecarloapproachtoimportancesamplinginstochasticprogramming AT ustunberktevfikberk markovchainmontecarloapproachtoimportancesamplinginstochasticprogramming |