In this dissertation, we apply stochastic approximation (SA) to two different problems addressed respectively in Part I and Part II. / The contribution of Part I is mostly theoretical. We consider the problem of online tracking of moving targets such as a signals, through noisy measurements. In particular, we study a non-stationary environment that is subject to sudden discontinuous changes in the underlying parameters of the system. We assume no a priori knowledge about the parameters nor the change-times. Our approach is based on constant stepsize SA. However, because of the unpredictable discontinuous changes, the choice of stepsize is difficult. Small stepsizes improve precision while large stepsizes allow the SA iterates to react faster to sudden changes. / We first investigate target estimation. Our work appears in [Levy 09]. We propose to combine a small constant stepsize with change-point monitoring, and to reset the process at a value closer to the new target when a change is detected. Because the environment is not stationary, we cannot directly apply the usual limit theorems. We thus give a theoretical characterization and discuss the tradeoff between precision and fast adaptation. We also introduce a new monitoring scheme, the regression-based hypothesis test. / Secondly, we consider an online version of the well-known Q-learning algorithm, which operates directly in its target environment, to optimize a Markov decision process. Online algorithms are challenging because the errors, necessarily made when learning, affect performance. Again, under a switching environment the usual limit theorems are not applicable. We introduce an adaptive stepsize selection algorithm based on weak convergence results for SA. Our algorithm automatically achieves a desirable balance between speed and accuracy. These findings are published in [Levy 06, Costa 09]. / In Part II, we study an applied problem related to the mining industry. Strategic management requires managing large portfolios of investments. Because financial resources are limited, only the projects with the highest net present value (NPV), their measure of economic value, will be funded. To value a mine project we need to consider future uncertainties. The approach commonly taken to value a project is to assume that if funded, the mine will be operated optimally throughout its life. Our final aim is not to provide an exact strategy, but to propose an optimization tool to improve decision-making in complex scenarios. Of all the variables involved, the typically large investments in infrastructure, as well as the uncertainty in commodity price, have the most significant impact on the mine value. We thus adopt a simplified model of the infrastructure and extraction optimization problem, subject to price uncertainty. / Common optimization methods are impractical for realistic size models. Our main contribution is the threshold optimization methodology based on measured valued differentiation (MVD) and SA. We also present another simulation-based method, the particles method [Dallagi 07], for comparison purposes. Both methods are well-adapted for high dimensional problems. We provide numerical results and discuss their characteristics and applicability.
| Identifer | oai:union.ndltd.org:ADTP/273056 |
| Date | January 2009 |
| Creators | Levy, Kim |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | Restricted Access: Abstract and Citation Only |
Page generated in 0.0017 seconds