Computational Complexity of Adaptive Algorithms in Monte Carlo Optimization (Math Programming, Stochastic Analysis).
dc.contributor.author | Zabinsky, Zelda Barbara | |
dc.date.accessioned | 2020-09-09T02:08:10Z | |
dc.date.available | 2020-09-09T02:08:10Z | |
dc.date.issued | 1985 | |
dc.identifier.uri | https://hdl.handle.net/2027.42/160749 | |
dc.description.abstract | This dissertation examines the complexity of a class of adaptive Monte Carlo algorithms used to solve convex programs. We define a measure of computational complexity involving the distribution of the number of iterations needed to achieve a solution within a specified error. This error is the difference between the obtained solution and the optimum. A conical convex program is then a stochastic worst case according to this measure. Finally, applying the complexity measure to the stochastic worst case provides an upper bound on complexity as a function of problem dimension. The analysis yields sufficient conditions for a Monte Carlo algorithm to have a linear bound on complexity as a function of dimension. It also provides confidence intervals for the true optimum in terms of observed performance of the algorithm. We analyze the complexity of two new Monte Carlo algorithms: a conceptual Pure Adaptive Search and an implementable Adaptive Mixing Algorithm. We show that the complexity of Pure Adaptive Search has a bound that is linear in dimension for convex programs. We experimentally approximate a linear bound on the complexity of the Adaptive Mixing Algorithm for a subset of convex programs. The advantages and disadvantages of these two algorithms clarify some of the conditions and results of the analysis. Furthermore, the Adaptive Mixing Algorithm is a first step in using this analysis to design a practical algorithm with linear complexity in dimension. | |
dc.format.extent | 134 p. | |
dc.language | English | |
dc.title | Computational Complexity of Adaptive Algorithms in Monte Carlo Optimization (Math Programming, Stochastic Analysis). | |
dc.type | Thesis | |
dc.description.thesisdegreename | PhD | en_US |
dc.description.thesisdegreediscipline | Operations research | |
dc.description.thesisdegreegrantor | University of Michigan | |
dc.subject.hlbtoplevel | Engineering | |
dc.contributor.affiliationumcampus | Ann Arbor | |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/160749/1/8521018.pdf | en_US |
dc.owningcollname | Dissertations and Theses (Ph.D. and Master's) |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.