Weiyan Ge. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 64-68). / Abstracts in English and Chinese. / Abstract --- p.ii / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Introduction of Power Control Problem --- p.2 / Chapter 1.1.1 --- Classification of Power Control Problem --- p.2 / Chapter 1.1.2 --- Previous Works --- p.7 / Chapter 1.2 --- Scope and Contribution of the Thesis --- p.11 / Chapter 1.3 --- Organization of the Thesis --- p.12 / Chapter 2 --- Background --- p.14 / Chapter 2.1 --- Stochastic Approximation --- p.14 / Chapter 2.2 --- Lognormal Distribution --- p.17 / Chapter 2.2.1 --- Definition and Properties --- p.17 / Chapter 2.2.2 --- Application on Radio Propagation --- p.18 / Chapter 3 --- System Model and Centralized Algorithm --- p.21 / Chapter 3.1 --- System Model --- p.21 / Chapter 3.2 --- Problem Statement and the Centralized Algorithm --- p.25 / Chapter 4 --- Proposed Stochastic Power Control Algorithm --- p.30 / Chapter 4.1 --- Proposed Power Control Algorithm --- p.30 / Chapter 4.2 --- Basic Properties of the Algorithm --- p.33 / Chapter 4.3 --- Convergence Property --- p.38 / Chapter 5 --- Numerical Results --- p.44 / Chapter 5.1 --- Simulation Model --- p.44 / Chapter 5.2 --- Numerical Results --- p.47 / Chapter 6 --- Conclusions And Future Works --- p.58 / Chapter 6.1 --- Conclusions --- p.58 / Chapter 6.2 --- Future Works --- p.60 / Chapter A --- Basic Properties of LOG-Distribution --- p.62 / Bibliography --- p.64

Recently, the stochastic approximation Monte Carlo algorithm has been proposed by Liang et al. (2005) as a general-purpose stochastic optimization and simulation algorithm. An annealing version of this algorithm was developed for real small protein folding problems. The numerical results indicate that it outperforms simulated annealing and conventional Monte Carlo algorithms as a stochastic optimization algorithm. We also propose one method for the use of secondary structures in protein folding. The predicted protein structures are rather close to the true structures. Phylogenetic trees have been used in biology for a long time to graphically represent evolutionary relationships among species and genes. An understanding of evolutionary relationships is critical to appropriate interpretation of bioinformatics results. The use of the sequential structure of phylogenetic trees in conjunction with stochastic approximation Monte Carlo was developed for phylogenetic tree reconstruction. The numerical results indicate that it has a capability of escaping from local traps and achieving a much faster convergence to the global likelihood maxima than other phylogenetic tree reconstruction methods, such as BAMBE and MrBayes.

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.

Univ., Diss.--St. Gallen, 2004.

[pt] A identificação de sistemas é focalizada sob o ponto de vista da aproximação estocástica. Um sistema sem memória e invariante no tempo, com função completamente desconhecida é identificado por intermédio de uma estimação, que minimiza o critério do erro médio quadrático, tomando como base um conjunto de funções pré- selecionadas e linearmente independentes. A identificação do sistema é obtida através de uma algoritmo recursivo de aproximação estocástica, que converge para o valor real dessa estimativa, com probabilidade 1 e no sentido da média quadrática. Um estudo da aceleração desse algoritmo é efetuado, comprovando a existência de uma seqüência capaz de otimizá-lo. É demonstrada a aplicação desse algoritmo para identificação de um sistema linear e invariante no tempo, entretanto a aceleração da convergência não é mais uma conseqüência do caso anterior. Ainda é apresentada uma tentativa de contornar o problema de acessibilidade dos estados, requerida pelo algoritmo de aproximação estocástica, utilizando simultaneamente à identificação dos parâmetros do sistema, os algoritmos do filtro de Kalman, para estimação dos estados / [en] The stochastic approximation approach is used for systems identification. A memoryless time-invariant system with functional form completely unknow is identified by means of an estimate based on a preselected and linearly independent set of function which minimizes the mean-square-error criterion. The system identification is obtained using a stochastic approximation recursive algorithm, which convergs to a real value of this estimate, with probability 1 and in the mean square sense. The acceleration study of this algorithm is developd by proving the existence of an optimal sequence. The application of this algorithm for a linear timevariant system identification is proved, nevertheless the convergence acceletation is not anymore a consequence of the last case. Next is presented a tentative to by-pass the problem of states accessibility, required for the stochastic approximation, using simultaneously parameters systems identification with the Kalman-filter algorithms for states estimation.

Sequential decision making problems are ubiquitous in a number of research areas such as operations research, finance, engineering and computer science. The main challenge with these problems comes from the fact that, firstly, there is uncertainty about the future. And secondly, decisions have to be made over a period of time, sequentially. These problems, in many cases, are modeled as Markov Decision Process (MDP). Most real-life MDPs are ‘high dimensional’ in nature making them challenging from a numerical point of view. We consider a number of such high dimensional MDPs. In some cases such problems can be approximately solved using Approximate Dynamic Programming. In other cases problem specific analysis can be solved to device tractable policies that are near-optimal. In Chapter 2, we presents a novel and practical non-parametric approximate dynamic programming (ADP) algorithm that enjoys graceful, dimension-independent approximation and sample complexity guarantees. In particular, we establish both theoretically and computationally that our proposal can serve as a viable replacement to state of the art parametric ADP algorithms, freeing the designer from carefully specifying an approximation architecture. We accomplish this by ‘kernelizing’ a recent mathematical program for ADP (the ‘smoothed’ approximate LP) proposed by [Desai et al., 2011]. In Chapter 3, we consider a class of stochastic control problems where the action space at each time can be described by a class of matching or, more generally, network flow polytopes. Special cases of this class of dynamic matching problems include many problems that are well-studied in the literature, such as: (i) online keyword matching in Internet advertising (the adwords problem); (ii) the bipartite matching of donated kidneys from cadavers to recipients; and (iii) the allocation of donated kidneys through exchanges over cycles of live donor-patient pairs. We provide an approximate dynamic program (ADP) algorithm for dynamic matching with stochastic arrivals and departures. Our framework is more general than the methods prevalent in the literature in that it is applicable to a broad range of problems characterized by a variety of action polytopes and generic arrival and departure processes. In Chapter 4, we consider the problem of A-B testing when the impact of the treatment is marred by a large number of covariates. Randomization can be highly inefficient in such settings, and thus we consider the problem of optimally allocating test subjects to either treatment with a view to maximizing the efficiency of our estimate of the treatment effect. Our main contribution is a tractable algorithm for this problem in the online setting, where subjects arrive, and must be assigned, sequentially. We characterize the value of optimized allocations relative to randomized allocations and show that this value grows large as the number of covariates grows. In particular, we show that there is a lot to be gained from ‘optimizing’ the process of A-B testing relative to the simple randomized trials that are the mainstay of A-B testing in the ‘big data’ regime of modern e-commerce applications, where the number of covariates is often comparable to the number of experimental trials.

Designing distributed algorithms for optimizing system-wide performances of large scale communication networks is a challenging task. The key part of this design involves a lot of combinatorial network optimization problems, which are computationally intractable in general and hard to approximate even in a centralized manner. Inspired by the seminal work of Jiang-Walrand, Markov approximation framework was proposed for synthesizing distributed algorithms for general combinatorial network optimization problems. To provide performance guarantees, convergence properties of these distributed algorithms are of significance. / First, we consider instances of the designed Markov chain over resource allocation algorithms. We focus on the convergence issues. We find several examples such that the related convergence results can be applied directly. These examples include optimal path (or tree) selection for wireline networks, optimal neighboring selection for peer-to-peer networks, and optimal channel (or power) assignment for wireless local area networks. / In this thesis, we first review Markov approximation framework and further develop this framework by studying convergence properties of distributed algorithms. These system-wide algorithms consist of the designed Markov chain and resource allocation algorithms. We concentrate on two general scenarios: the designed Markov chain over resource allocation algorithms and resource allocation algorithms over the designed Markov chain. With imprecise measurements of network parameters and without the time-scale separation assumption, we prove convergence to near-optimal solutions for both scenarios under mild conditions. Then we apply Markov approximation framework and associated convergence results to various combinatorial network optimization problems. / Second, we consider instances of resource allocation algorithms over the designed Markov chain. We focus on the system-wide performances. Two instances are investigated: cross-layer optimization for wireless networks with deterministic channel model and wireless networks with network coding. For both instances, guided by Markov approximation framework, we design distributed schemes to achieve maximum utilities. These schemes include primal-dual flow control algorithms, Markov chain based scheduling algorithms, and routing (or network coding) algorithms. Under time-dependent step sizes and update intervals, we show that these distributed schemes converge to the optimal solutions with probability one. Further, under constant step sizes and constant update intervals, we prove that these distributed schemes also converge to a bounded neighborhood of optimal solutions with probability one. These analytical results are validated by numerical results as well. / Shao, Ziyu. / Adviser: Shou Yen Robert Li. / Source: Dissertation Abstracts International, Volume: 73-03, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 134-140). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Huang Changquan. / "April 2002." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (p. 62-71). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web. / Abstracts in English and Chinese.

A large class of sequential decision making problems under uncertainty with multiple competing decision makers/agents can be modeled as stochastic games. Stochastic games having Markov properties are called Markov games or competitive Markov decision processes. This dissertation presents an approach to solve non cooperative stochastic games, in which each decision maker makes her/his own decision independently and each has an individual payoff function. In stochastic games, the environment is nonstationary and each agent's payoff is affected by joint decisions of all agents, which results in the conflict of interest among the decision makers. In this research, the theory of Markov decision processes (MDPs) is combined with the game theory to analyze the structure of Nash equilibrium for stochastic games. In particular, the Laurent series expansion technique is used to extend the results of discounted reward stochastic games to average reward stochastic games. As a result, auxiliary matrix games are developed that have equivalent equilibrium points and values to a class of stochastic games that are irreducible and have average reward performance metric. R-learning is a well known machine learning algorithm that deals with average reward MDPs. The R-learning algorithm is extended to develop a Nash-R reinforcement learning algorithm for obtaining the equivalent auxiliary matrices. A convergence analysis of the Nash-R algorithm is developed from the study of the asymptotic behavior of its two time scale stochastic approximation scheme, and the stability of the associated ordinary differential equations (ODEs). The Nash-R learning algorithm is tested and then benchmarked with MDP based learning methods using a well known grid game. Subsequently, a real life application of stochastic games in deregulated power market is explored. According to the current literature, Cournot, Bertrand, and Supply Function Equilibrium (SFEs) are the three primary equilibrium models that are used to evaluate the power market designs. SFE is more realistic for pool type power markets. However, for a complicated power system, the convex assumption for optimization problems is violated in most cases, which makes the problems more difficult to solve. The SFE concept in adopted in this research, and the generators' behaviors are modeled as a stochastic game instead of one shot game. The power market is considered to have features such as multi-settlement (bilateral, day-ahead market, spot markets and transmission congestion contracts), and demand elasticity. Such a market consisting of multiple competing suppliers (generators) is modeled as a competitive Markov decision processes and is studied using the Nash-R algorithm.

A hybrid design optimization method combining the stochastic method based on simultaneous perturbation stochastic approximation (SPSA) and the deterministic method of Broydon-Fletcher-Goldfarb-Shanno (BFGS) is developed in order to take advantage of the high efficiency of the gradient based methods and the global search capabilities of SPSA for applications in the optimal aerodynamic shape design of a three dimensional elliptic nozzle. The performance of this hybrid method is compared with that of SPSA, simulated annealing (SA) and gradient based BFGS method. The objective functions which are minimized are estimated by numerically solving the 3D Euler and Navier-Stokes equations using a TVD approach and a LU implicit scheme. Computed results show that the hybrid optimization method proposed in this study shows a promise of high computational efficiency and global search capabilities. / Singapore-MIT Alliance (SMA)