Algorithmic Developments in Monte Carlo Sampling-Based Methods for Stochastic Programming

Persistent Link:
http://hdl.handle.net/10150/228433
Title:
Algorithmic Developments in Monte Carlo Sampling-Based Methods for Stochastic Programming
Author:
Pierre-Louis, Péguy
Issue Date:
2012
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Monte Carlo sampling-based methods are frequently used in stochastic programming when exact solution is not possible. In this dissertation, we develop two sets of Monte Carlo sampling-based algorithms to solve classes of two-stage stochastic programs. These algorithms follow a sequential framework such that a candidate solution is generated and evaluated at each step. If the solution is of desired quality, then the algorithm stops and outputs the candidate solution along with an approximate (1 - α) confidence interval on its optimality gap. The first set of algorithms proposed, which we refer to as the fixed-width sequential sampling methods, generate a candidate solution by solving a sampling approximation of the original problem. Using an independent sample, a confidence interval is built on the optimality gap of the candidate solution. The procedures stop when the confidence interval width plus an inflation factor falls below a pre-specified tolerance epsilon. We present two variants. The fully sequential procedures use deterministic, non-decreasing sample size schedules, whereas in another variant, the sample size at the next iteration is determined using current statistical estimates. We establish desired asymptotic properties and present computational results. In another set of sequential algorithms, we combine deterministically valid and sampling-based bounds. These algorithms, labeled sampling-based sequential approximation methods, take advantage of certain characteristics of the models such as convexity to generate candidate solutions and deterministic lower bounds through Jensen's inequality. A point estimate on the optimality gap is calculated by generating an upper bound through sampling. The procedure stops when the point estimate on the optimality gap falls below a fraction of its sample standard deviation. We show asymptotically that this algorithm finds a solution with a desired quality tolerance. We present variance reduction techniques and show their effectiveness through an empirical study.
Type:
text; Electronic Dissertation
Keywords:
Confidence Intervals; Monte Carlo; Stochastic Programming; Stopping Rules; Variance Reduction; Systems & Industrial Engineering; Approximation Methods
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Systems & Industrial Engineering
Degree Grantor:
University of Arizona
Advisor:
Bayraksan, Güzin

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleAlgorithmic Developments in Monte Carlo Sampling-Based Methods for Stochastic Programmingen_US
dc.creatorPierre-Louis, Péguyen_US
dc.contributor.authorPierre-Louis, Péguyen_US
dc.date.issued2012-
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractMonte Carlo sampling-based methods are frequently used in stochastic programming when exact solution is not possible. In this dissertation, we develop two sets of Monte Carlo sampling-based algorithms to solve classes of two-stage stochastic programs. These algorithms follow a sequential framework such that a candidate solution is generated and evaluated at each step. If the solution is of desired quality, then the algorithm stops and outputs the candidate solution along with an approximate (1 - α) confidence interval on its optimality gap. The first set of algorithms proposed, which we refer to as the fixed-width sequential sampling methods, generate a candidate solution by solving a sampling approximation of the original problem. Using an independent sample, a confidence interval is built on the optimality gap of the candidate solution. The procedures stop when the confidence interval width plus an inflation factor falls below a pre-specified tolerance epsilon. We present two variants. The fully sequential procedures use deterministic, non-decreasing sample size schedules, whereas in another variant, the sample size at the next iteration is determined using current statistical estimates. We establish desired asymptotic properties and present computational results. In another set of sequential algorithms, we combine deterministically valid and sampling-based bounds. These algorithms, labeled sampling-based sequential approximation methods, take advantage of certain characteristics of the models such as convexity to generate candidate solutions and deterministic lower bounds through Jensen's inequality. A point estimate on the optimality gap is calculated by generating an upper bound through sampling. The procedure stops when the point estimate on the optimality gap falls below a fraction of its sample standard deviation. We show asymptotically that this algorithm finds a solution with a desired quality tolerance. We present variance reduction techniques and show their effectiveness through an empirical study.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectConfidence Intervalsen_US
dc.subjectMonte Carloen_US
dc.subjectStochastic Programmingen_US
dc.subjectStopping Rulesen_US
dc.subjectVariance Reductionen_US
dc.subjectSystems & Industrial Engineeringen_US
dc.subjectApproximation Methodsen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineSystems & Industrial Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorBayraksan, Güzinen_US
dc.contributor.committeememberHead, Larry K.en_US
dc.contributor.committeememberLin, Weien_US
dc.contributor.committeememberSon, Young-Junen_US
dc.contributor.committeememberBayraksan, Güzinen_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.