Data-Driven Methods for Optimization Under Uncertainty with Application to Water Allocation

Persistent Link:
http://hdl.handle.net/10150/311177
Title:
Data-Driven Methods for Optimization Under Uncertainty with Application to Water Allocation
Author:
Love, David Keith
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.
Embargo:
Release 03-Dec-2014
Abstract:
Stochastic programming is a mathematical technique for decision making under uncertainty using probabilistic statements in the problem objective and constraints. In practice, the distribution of the unknown quantities are often known only through observed or simulated data. This dissertation discusses several methods of using this data to formulate, solve, and evaluate the quality of solutions of stochastic programs. The central contribution of this dissertation is to investigate the use of techniques from simulation and statistics to enable data-driven models and methods for stochastic programming. We begin by extending the method of overlapping batches from simulation to assessing solution quality in stochastic programming. The Multiple Replications Procedure, where multiple stochastic programs are solved using independent batches of samples, has previously been used for assessing solution quality. The Overlapping Multiple Replications Procedure overlaps the batches, thus losing the independence between samples, but reducing the variance of the estimator without affecting its bias. We provide conditions under which the optimality gap estimators are consistent, the variance reduction benefits are obtained, and give a computational illustration of the small-sample behavior. Our second result explores the use of phi-divergences for distributionally robust optimization, also known as ambiguous stochastic programming. The phi-divergences provide a method of measuring distance between probability distributions, are widely used in statistical inference and information theory, and have recently been proposed to formulate data-driven stochastic programs. We provide a novel classification of phi-divergences for stochastic programming and give recommendations for their use. A value of data condition is derived and the asymptotic behavior of the phi-divergence constrained stochastic program is described. Then a decomposition-based solution method is proposed to solve problems computationally. The final portion of this dissertation applies the phi-divergence method to a problem of water allocation in a developing region of Tucson, AZ. In this application, we integrate several sources of uncertainty into a single model, including (1) future population growth in the region, (2) amount of water available from the Colorado River, and (3) the effects of climate variability on water demand. Estimates of the frequency and severity of future water shortages are given and we evaluate the effectiveness of several infrastructure options.
Type:
text; Electronic Dissertation
Keywords:
overlapping batches; phi divergence; Stochastic programming; water allocation; Applied Mathematics; Distributionally robust optimization
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Applied Mathematics
Degree Grantor:
University of Arizona
Advisor:
Bayraksan, Guzin

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleData-Driven Methods for Optimization Under Uncertainty with Application to Water Allocationen_US
dc.creatorLove, David Keithen_US
dc.contributor.authorLove, David Keithen_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.releaseRelease 03-Dec-2014en_US
dc.description.abstractStochastic programming is a mathematical technique for decision making under uncertainty using probabilistic statements in the problem objective and constraints. In practice, the distribution of the unknown quantities are often known only through observed or simulated data. This dissertation discusses several methods of using this data to formulate, solve, and evaluate the quality of solutions of stochastic programs. The central contribution of this dissertation is to investigate the use of techniques from simulation and statistics to enable data-driven models and methods for stochastic programming. We begin by extending the method of overlapping batches from simulation to assessing solution quality in stochastic programming. The Multiple Replications Procedure, where multiple stochastic programs are solved using independent batches of samples, has previously been used for assessing solution quality. The Overlapping Multiple Replications Procedure overlaps the batches, thus losing the independence between samples, but reducing the variance of the estimator without affecting its bias. We provide conditions under which the optimality gap estimators are consistent, the variance reduction benefits are obtained, and give a computational illustration of the small-sample behavior. Our second result explores the use of phi-divergences for distributionally robust optimization, also known as ambiguous stochastic programming. The phi-divergences provide a method of measuring distance between probability distributions, are widely used in statistical inference and information theory, and have recently been proposed to formulate data-driven stochastic programs. We provide a novel classification of phi-divergences for stochastic programming and give recommendations for their use. A value of data condition is derived and the asymptotic behavior of the phi-divergence constrained stochastic program is described. Then a decomposition-based solution method is proposed to solve problems computationally. The final portion of this dissertation applies the phi-divergence method to a problem of water allocation in a developing region of Tucson, AZ. In this application, we integrate several sources of uncertainty into a single model, including (1) future population growth in the region, (2) amount of water available from the Colorado River, and (3) the effects of climate variability on water demand. Estimates of the frequency and severity of future water shortages are given and we evaluate the effectiveness of several infrastructure options.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectoverlapping batchesen_US
dc.subjectphi divergenceen_US
dc.subjectStochastic programmingen_US
dc.subjectwater allocationen_US
dc.subjectApplied Mathematicsen_US
dc.subjectDistributionally robust optimizationen_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, Guzinen_US
dc.contributor.committeememberBayraksan, Guzinen_US
dc.contributor.committeememberBrio, Moyseyen_US
dc.contributor.committeememberKennedy, Thomasen_US
dc.contributor.committeememberSon, Young-Junen_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.