Persistent Link:
http://hdl.handle.net/10150/222892
Title:
Multistage Stochastic Decomposition and its Applications
Author:
Zhou, Zhihong
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:
In this dissertation, we focus on developing sampling-based algorithms for solving stochastic linear programs. The work covers both two stage and multistage versions of stochastic linear programs. In particular, we first study the two stage stochastic decomposition (SD) algorithm and present some extensions associated with SD. Specifically, we study two issues: a) are there conditions under which the regularized version of SD generates a unique solution? and b) in cases where a user is willing to sacrifice optimality, is there a way to modify the SD algorithm so that a user can trade-off solution times with solution quality? Moreover, we present our preliminary approach to address these questions. Secondly, we investigate the multistage stochastic linear programs and propose a new approach to solving multistage stochastic decision models in the presence of constraints. The motivation for proposing the multistage stochastic decomposition algorithm is to handle large scale multistage stochastic linear programs. In our setting, the deterministic equivalent problems of the multistage stochastic linear program are too large to be solved exactly. Therefore, we seek an asymptotically optimum solution by simulating the SD algorithmic process, which was originally designed for two-stage stochastic linear programs (SLPs). More importantly, when SD is implemented in a time-staged manner, the algorithm begins to take the flavor of a simulation leading to what we refer to as optimization simulation. As for multistage stochastic decomposition, there are a couple of advantages that deserve mention. One of the benefits is that it can work directly with sample paths, and this feature makes the new algorithm much easier to be integrated within a simulation. Moreover, compared with other sampling-based algorithms for multistage stochastic programming, we also overcome certain limitations, such as a stage-wise independence assumption.
Type:
text; Electronic Dissertation
Keywords:
Optimization Simulation; Stage-wise Independence; Stochastic Decomposition; Stochastic Dual Dynamic Programming; Systems & Industrial Engineering; Multistage Stochastic Decomposition; Multistage Stochastic Program
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Systems & Industrial Engineering
Degree Grantor:
University of Arizona
Advisor:
Sen, Suvrajeet; Bayraksan, Guzin

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleMultistage Stochastic Decomposition and its Applicationsen_US
dc.creatorZhou, Zhihongen_US
dc.contributor.authorZhou, Zhihongen_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.abstractIn this dissertation, we focus on developing sampling-based algorithms for solving stochastic linear programs. The work covers both two stage and multistage versions of stochastic linear programs. In particular, we first study the two stage stochastic decomposition (SD) algorithm and present some extensions associated with SD. Specifically, we study two issues: a) are there conditions under which the regularized version of SD generates a unique solution? and b) in cases where a user is willing to sacrifice optimality, is there a way to modify the SD algorithm so that a user can trade-off solution times with solution quality? Moreover, we present our preliminary approach to address these questions. Secondly, we investigate the multistage stochastic linear programs and propose a new approach to solving multistage stochastic decision models in the presence of constraints. The motivation for proposing the multistage stochastic decomposition algorithm is to handle large scale multistage stochastic linear programs. In our setting, the deterministic equivalent problems of the multistage stochastic linear program are too large to be solved exactly. Therefore, we seek an asymptotically optimum solution by simulating the SD algorithmic process, which was originally designed for two-stage stochastic linear programs (SLPs). More importantly, when SD is implemented in a time-staged manner, the algorithm begins to take the flavor of a simulation leading to what we refer to as optimization simulation. As for multistage stochastic decomposition, there are a couple of advantages that deserve mention. One of the benefits is that it can work directly with sample paths, and this feature makes the new algorithm much easier to be integrated within a simulation. Moreover, compared with other sampling-based algorithms for multistage stochastic programming, we also overcome certain limitations, such as a stage-wise independence assumption.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectOptimization Simulationen_US
dc.subjectStage-wise Independenceen_US
dc.subjectStochastic Decompositionen_US
dc.subjectStochastic Dual Dynamic Programmingen_US
dc.subjectSystems & Industrial Engineeringen_US
dc.subjectMultistage Stochastic Decompositionen_US
dc.subjectMultistage Stochastic Programen_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.advisorSen, Suvrajeeten_US
dc.contributor.advisorBayraksan, Guzinen_US
dc.contributor.committeememberSon, Young Junen_US
dc.contributor.committeememberLin, Wei Huaen_US
dc.contributor.committeememberSen, Suvrajeeten_US
dc.contributor.committeememberBayraksan, Guzinen_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.