Bias and Variance Reduction in Assessing Solution Quality for Stochastic Programs

Persistent Link:
http://hdl.handle.net/10150/301665
Title:
Bias and Variance Reduction in Assessing Solution Quality for Stochastic Programs
Author:
Stockbridge, Rebecca
Issue Date:
2013
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:
Stochastic programming combines ideas from deterministic optimization with probability and statistics to produce more accurate models of optimization problems involving uncertainty. However, due to their size, stochastic programming problems can be extremely difficult to solve and instead approximate solutions are used. Therefore, there is a need for methods that can accurately identify optimal or near optimal solutions. In this dissertation, we focus on improving Monte-Carlo sampling-based methods that assess the quality of potential solutions to stochastic programs by estimating optimality gaps. In particular, we aim to reduce the bias and/or variance of these estimators. We first propose a technique to reduce the bias of optimality gap estimators which is based on probability metrics and stability results in stochastic programming. This method, which requires the solution of a minimum-weight perfect matching problem, can be run in polynomial time in sample size. We establish asymptotic properties and present computational results. We then investigate the use of sampling schemes to reduce the variance of optimality gap estimators, and in particular focus on antithetic variates and Latin hypercube sampling. We also combine these methods with the bias reduction technique discussed above. Asymptotic properties of the resultant estimators are presented, and computational results on a range of test problems are discussed. Finally, we apply methods of assessing solution quality using antithetic variates and Latin hypercube sampling to a sequential sampling procedure to solve stochastic programs. In this setting, we use Latin hypercube sampling when generating a sequence of candidate solutions that is input to the procedure. We prove that these procedures produce a high-quality solution with high probability, asymptotically, and terminate in a finite number of iterations. Computational results are presented.
Type:
text; Electronic Dissertation
Keywords:
Monte Carlo simulation; Stochastic programming; Variance reduction techniques; Applied Mathematics; Bias reduction techniques
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Applied Mathematics
Degree Grantor:
University of Arizona
Advisor:
Bayraksan, Güzin

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleBias and Variance Reduction in Assessing Solution Quality for Stochastic Programsen_US
dc.creatorStockbridge, Rebeccaen_US
dc.contributor.authorStockbridge, Rebeccaen_US
dc.date.issued2013-
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.abstractStochastic programming combines ideas from deterministic optimization with probability and statistics to produce more accurate models of optimization problems involving uncertainty. However, due to their size, stochastic programming problems can be extremely difficult to solve and instead approximate solutions are used. Therefore, there is a need for methods that can accurately identify optimal or near optimal solutions. In this dissertation, we focus on improving Monte-Carlo sampling-based methods that assess the quality of potential solutions to stochastic programs by estimating optimality gaps. In particular, we aim to reduce the bias and/or variance of these estimators. We first propose a technique to reduce the bias of optimality gap estimators which is based on probability metrics and stability results in stochastic programming. This method, which requires the solution of a minimum-weight perfect matching problem, can be run in polynomial time in sample size. We establish asymptotic properties and present computational results. We then investigate the use of sampling schemes to reduce the variance of optimality gap estimators, and in particular focus on antithetic variates and Latin hypercube sampling. We also combine these methods with the bias reduction technique discussed above. Asymptotic properties of the resultant estimators are presented, and computational results on a range of test problems are discussed. Finally, we apply methods of assessing solution quality using antithetic variates and Latin hypercube sampling to a sequential sampling procedure to solve stochastic programs. In this setting, we use Latin hypercube sampling when generating a sequence of candidate solutions that is input to the procedure. We prove that these procedures produce a high-quality solution with high probability, asymptotically, and terminate in a finite number of iterations. Computational results are presented.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectMonte Carlo simulationen_US
dc.subjectStochastic programmingen_US
dc.subjectVariance reduction techniquesen_US
dc.subjectApplied Mathematicsen_US
dc.subjectBias reduction techniquesen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineApplied Mathematicsen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorBayraksan, Güzinen_US
dc.contributor.committeememberSon, Young-Junen_US
dc.contributor.committeememberWatkins, Josephen_US
dc.contributor.committeememberBayraksan, Güzinen_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.