The Library
Efficient information collection in stochastic optimisation
Tools
Fei, Xin (2019) Efficient information collection in stochastic optimisation. PhD thesis, University of Warwick.
|
PDF
WRAP_Theses_Fei_2019.pdf - Submitted Version - Requires a PDF viewer. Download (3320Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b3438548~S15
Abstract
This thesis focuses on a class of information collection problems in stochastic optimisation. Algorithms in this area often need to measure the performances of several potential solutions, and use the collected information in their search for high-performance solutions, but only have a limited budget for measuring. A simple approach that allocates simulation time equally over all potential solutions may waste time in collecting additional data for the alternatives that can be quickly identified as non-promising. Instead, algorithms should amend their measurement strategy to iteratively examine the statistical evidences collected thus far and focus computational efforts on the most promising alternatives. This thesis develops new efficient methods of collecting information to be used in stochastic optimisation problems.
First, we investigate an efficient measurement strategy used for the solution selection procedure of two-stage linear stochastic programs. In the solution selection procedure, finite computational resources must be allocated among numerous potential solutions to estimate their performances and identify the best solution. We propose a two-stage sampling approach that exploits a Wasserstein-based screening rule and an optimal computing budget allocation technique to improve the efficiency of obtaining a high-quality solution. Numerical results show our method provides good trade-offs between computational effort and solution performance.
Then, we address the information collection problems that are encountered in the search for robust solutions. Specifically, we use an evolutionary strategy to solve a class of simulation optimisation problems with computationally expensive blackbox functions. We implement an archive sample approximation method to ix reduce the required number of evaluations. The main challenge in the application of this method is determining the locations of additional samples drawn in each generation to enrich the information in the archive and minimise the approximation error. We propose novel sampling strategies by using the Wasserstein metric to estimate the possible benefit of a potential sample location on the approximation error. An empirical comparison with several previously proposed archive-based sample approximation methods demonstrates the superiority of our approaches.
In the final part of this thesis, we propose an adaptive sampling strategy for the rollout algorithm to solve the clinical trial scheduling and resource allocation problem under uncertainty. The proposed sampling strategy method exploits the variance reduction technique of common random numbers and the empirical Bernstein inequality in a statistical racing procedure, which can balance the exploration and exploitation of the rollout algorithm. Moreover, we present an augmented approach that utilises a heuristic-based grouping rule to enhance the simulation efficiency by breaking down the overall action selection problem into a selection problem involving small groups. The numerical results show that the proposed method provides competitive results within a reasonable amount of computational time.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics |
||||
Library of Congress Subject Headings (LCSH): | Algorithms, Mathematical optimization, Stochastic processes | ||||
Official Date: | May 2019 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Warwick Business School | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Gulpinar, Nalan ; Branke, Jürgen, 1969- | ||||
Format of File: | |||||
Extent: | x, 117 leaves : charts | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year