Type
Text
Type
Dissertation
Advisor
Hu, Jiaqiao | Feinberg, Eugene | Arkin, Estie | Djuric, petar
Date
2012-05-01
Keywords
Operations research
Department
Department of Applied Mathematics and Statistics
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/71513
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
This thesis studies a class of model-based randomized algorithms for solving general optimization problems. These are iterative algorithms that sample from and update an underlying distribution over the feasible solution space. We find that the model-based algorithms can be interpreted as the well-known stochastic approximation (SA) method. Following the connection between model-based algorithms and SA, we build a framwork to analyze the convergence and the convergence rate of these algorithms. Moreover, we present an instantiation of this framework which is the modified version of the Cross Entropy (CE) method, and analyze its convergence properties and numerical performance. In addition, we also propose a novel random search algorithm called Model-based Annealing Random Search (MARS). By exploiting its connection to SA we provide its global convergence result and analyze the asymptotic convergence rate as well. Finally, the empirical results of MARS show promising performance in comparison with some other existing methods. | 144 pages
Recommended Citation
Hu, Ping, "A Stochastic Approximation Interpretation for Model-based Optimization Algorithms" (2012). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 719.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/719