Thesis (Ph.D.)--University of Adelaide, Dept. of Electrical and Electronic Engineering, 2003. / "January 2003" Includes bibliographical references (leaves 120-129).

Stochastic approximation algorithms encompass a class of iterative schemes that converge to a sought value through a series of successive approximations. Such algorithms converge even when the observations are erroneous. Errors in observations may arise due to the stochastic nature of the problem at hand or due to extraneous noise. In other words, stochastic approximation algorithms are self-correcting schemes, in that the errors are wiped out in the limit and the algorithms still converge to the sought values. The rst stochastic approximation algorithm was developed by Robbins and Monro in 1951 to solve the root- nding problem. In 1977 Ljung showed that the asymptotic behavior of a stochastic approximation algorithm can be studied by associating a deterministic ODE, called the associated ODE, and studying it's asymptotic behavior instead. This is commonly referred to as the ODE method. In 1996 Bena•m and Bena•m and Hirsch [1] [2] used the dynamical systems approach in order to develop a framework to analyze generalized stochastic approximation algorithms, given by the following recursion: xn+1 = xn + a(n) [h(xn) + Mn+1] ; (1) where xn 2 Rd for all n; h : Rd ! Rd is Lipschitz continuous; fa(n)gn 0 is the given step-size sequence; fMn+1gn 0 is the Martingale difference noise. The assumptions of [1] later became the `standard assumptions for convergence'. One bottleneck in deploying this framework is the requirement on stability (almost sure boundedness) of the iterates. In 1999 Borkar and Meyn developed a unified set of assumptions that guaranteed both stability and convergence of stochastic approximations. However, the aforementioned frameworks did not account for scenarios with set-valued mean fields. In 2005 Bena•m, Hofbauer and Sorin [3] showed that the dynamical systems approach to stochastic approximations can be extended to scenarios with set-valued mean- fields. Again, stability of the fiterates was assumed. Note that stochastic approximation algorithms with set-valued mean- fields are also called stochastic recursive inclusions (SRIs). The Borkar-Meyn theorem for SRIs [10] As stated earlier, in many applications stability of the iterates is a hard assumption to verify. In Chapter 2 of the thesis, we present an extension of the original theorem of Borkar and Meyn to include SRIs. Specifically, we present two different (yet related) easily-verifiable sets of assumptions for both stability and convergence of SRIs. A SRI is given by the following recursion in Rd: xn+1 = xn + a(n) [yn + Mn+1] ; (2) where 8 n yn 2 H(xn) and H : Rd ! fsubsets of Rdg is a given Marchaud map. As a corollary to one of our main results, a natural generalization of the original Borkar and Meyn theorem is seen to follow. We also present two applications of our framework. First, we use our framework to provide a solution to the `approximate drift problem'. This problem can be stated as follows. When an experimenter runs a traditional stochastic approximation algorithm such as (1), the exact value of the drift h cannot be accurately calculated at every stage. In other words, the recursion run by the experimenter is given by (2), where yn is an approximation of h(xn) at stage n. A natural question arises: Do the errors due to approximations accumulate and wreak havoc with the long-term behavior (convergence) of the algorithm? Using our framework, we show the following: Suppose a stochastic approximation algorithm without errors can be guaranteed to be stable, then it's `approximate version' with errors is also stable, provided the errors are bounded at every stage. For the second application, we use our framework to relax the stability assumptions involved in the original Borkar-Meyn theorem, hence making the framework more applicable. It may be noted that the contents of Chapter 2 are based on [10]. Analysis of gradient descent methods with non-diminishing, bounded errors [9] Let us consider a continuously differentiable function f. Suppose we are interested in nding a minimizer of f, then a gradient descent (GD) scheme may be employed to nd a local minimum. Such a scheme is given by the following recursion in Rd: xn+1 = xn a(n)rf(xn): (3) GD is an important implementation tool for many machine learning algorithms, such as the backpropagation algorithm to train neural networks. For the sake of convenience, experimenters often employ gradient estimators such as Kiefer-Wolfowitz estimator, simultaneous perturbation stochastic approximation, etc. These estimators provide an estimate of the gradient rf(xn) at stage n. Since these estimators only provide an approximation of the true gradient, the experimenter is essentially running the recursion given by (2), where yn is a `gradient estimate' at stage n. Such gradient methods with errors have been previously studied by Bertsekas and Tsitsiklis [5]. However, the assumptions involved are rather restrictive and hard to verify. In particular, the gradient-errors are required to vanish asymptotically at a prescribed rate. This may not hold true in many scenarios. In Chapter 3 of the thesis, the results of [5] are extended to GD with bounded, non-diminishing errors, given by the following recursion in Rd: xn+1 = xn a(n) [rf(xn) + (n)] ; (4) where k (n)k for some fixed > 0. As stated earlier, previous literature required k (n)k ! 0, as n ! 1, at a `prescribed rate'. Sufficient conditions are presented for both stability and convergence of (4). In other words, the conditions presented in Chapter 3 ensure that the errors `do not accumulate' and wreak havoc with the stability or convergence of GD. Further, we show that (4) converges to a small neighborhood of the minimum set, which in turn depends on the error-bound . To the best of our knowledge this is the first time that GD with bounded non-diminishing errors has been analyzed. As an application, we use our framework to present a simplified implementation of simultaneous perturbation stochastic approximation (SPSA), a popular gradient descent method introduced by Spall [13]. Traditional convergence-analysis of SPSA involves assumptions that `couple' the `sensitivity parameters' of SPSA and the step-sizes. These assumptions restrict the choice of step-sizes available to the experimenter. In the context of machine learning, the learning rate may be adversely affected. We present an implementation of SPSA using `constant sensitivity parameters', thereby `decoupling' the step-sizes and sensitivity parameters. Further, we show that SPSA with constant sensitivity parameters can be analyzed using our framework. Finally, we present experimental results to support our theory. It may be noted that contents of Chapter 3 are based on [9]. b(n) a(n) Stochastic recursive inclusions with two timescales [12] There are many scenarios wherein the traditional single timescale framework cannot be used to analyze the algorithm at hand. Consider for example, the adaptive heuristic critic approach to reinforcement learning, which requires a stationary value iteration (for a fixed policy) to be executed between two policy iterations. To analyze such schemes Borkar [6] introduced the two timescale framework, along with a set of sufficient conditions which guarantee their convergence. Perkins and Leslie [8] extended the framework of Borkar to include set-valued mean- fields. However, the assumptions involved were still very restrictive and not easily verifiable. In Chapter 4 of the thesis, we present a generalization of the aforementioned frameworks. The framework presented is more general when compared to the frameworks of [6] and [8], and the assumptions involved are easily verifiable. A SRI with two timescales is given by the following coupled iteration: xn+1 = xn + a(n) un + Mn1+1 ; (5) yn+1 = yn + b(n) vn + Mn2+1 ; (6) where xn 2 R d and yn 2 R k for all n 0; un 2 h(xn; yn) and vn 2 g(xn; yn) for all n 0, where h : Rd Rk ! fsubsets of Rdg and g : Rd Rk ! fsubsets of Rkg are two given Marchaud maps; fa(n)gn 0 and fb(n)gn 0 are the step-size sequences satisfying ! 0 as n ! 1; fMn1+1gn 0 and fMn2+1 gn 0 constitute the Martingale noise terms. Our main contribution is in the weakening of the key assumption that `couples' the behavior of the x and y iterates. As an application of our framework we analyze the two timescale algorithm which solves the `constrained Lagrangian dual optimization problem'. The problem can be stated as thus: Given two functions f : Rd ! R and g : Rd ! Rk, we want to minimize f(x) subject to the condition that g(x) 0. This problem can be stated in the following primal form: inf sup f(x) + T g(x) : (7) 2R 2R0 x d k Under strong duality, solving the above equation is equivalent to solving it's dual: sup inf f(x) + T g(x) : (8) 2Rk x2Rd 0 The corresponding two timescale algorithm to solve the dual is given by: xn+1 = xn a(n) rx f(xn) + nT g(xn) + Mn2+1 ; (9) n+1 = n + b(n) f(xn) + nT g(xn) + Mn1+1 : r We use our framework to show that (9) converges to a solution of the dual given by (8). Further, as a consequence of our framework, the class of objective and constraint functions, for which (9) can be analyzed, is greatly enlarged. It may be noted that the contents of Chapter 4 are based on [12]. Stochastic approximation driven by `controlled Markov' process and temporal difference learning [11] In the field of reinforcement learning, one encounters stochastic approximation algorithms that are driven by Markov processes. The groundwork for analyzing the long-term behavior of such algorithms was laid by Benveniste et. al. [4]. Borkar [7] extended the results of [4] to include algorithms driven by `controlled Markov' processes i.e., algorithms where the `state process' was in turn driven by a time varying `control' process. Another important extension was that multiple stationary distributions were allowed, see [7] for details. The convergence analysis of [7] assumed that the iterates were stable. In reinforcement learning applications, stability is a hard assumption to verify. Hence, the stability assumption poses a bottleneck when deploying the aforementioned framework for the analysis of reinforcement algorithms. In Chapter 5 of the thesis we present sufficient conditions for both stability and convergence of stochastic approximations driven by `controlled Markov' processes. As an application of our framework, sufficient conditions for stability of temporal difference (T D) learning algorithm, an important policy-evaluation method, are presented that are compatible with existing conditions for convergence. The conditions are weakened two-fold in that (a) the Markov process is no longer required to evolve in a finite state space and (b) the state process is not required to be ergodic under a given stationary policy. It may be noted that the contents of Chapter 5 are based on [11].

Při práci s úlohami stochastického programování se často setkáváme s optimalizačními problémy, které jsou příliš rozsáhlé na to, aby byly zpracovány pomocí rutinních metod matematického programování. Nicméně, v některých případech mají tyto problémy vhodnou strukturu, umožňující použití specializovaných dekompozičních metod, které lze použít při řešení rozsáhlých optimalizačních problémů. Tato práce se zabývá dvěma třídami úloh stochastického programování, které mají speciální strukturu, a to dvoustupňovými stochastickými úlohami a úlohami s pravděpodobnostním omezením, a pokročilými dekompozičními metodami, které lze použít k řešení problému v těchto dvou třídách. V práci popisujeme novou metodu pro tvorbu “warm-start” řezů pro metodu zvanou “Generalized Benders Decomposition”, která se používá při řešení dvoustupňových stochastických problémů. Pro třídu úloh s pravděpodobnostním omezením zde uvádíme originální dekompoziční metodu, kterou jsme nazvali “Pool & Discard algoritmus”. Užitečnost popsaných dekompozičních metod je ukázána na několika příkladech a inženýrských aplikacích.

<div>Uncertainty quantification techniques based on the spectral approach have been studied extensively in the literature to characterize and quantify, at low computational cost, the impact that uncertainties may have on large-scale engineering problems. One such technique is the <i>generalized polynomial chaos</i> (gPC) which utilizes a time-independent orthogonal basis to expand a stochastic process in the space of random functions. The method uses a specific Askey-chaos system that is concordant with the measure defined in the probability space in order to ensure exponential convergence to the solution. For nearly two decades, this technique has been used widely by several researchers in the area of uncertainty quantification to solve stochastic problems using the spectral approach. However, a major drawback of the gPC method is that it cannot be used in the resolution of problems that feature strong nonlinear dependencies over the probability space as time progresses. Such downside arises due to the time-independent nature of the random basis, which has the undesirable property to lose unavoidably its optimality as soon as the probability distribution of the system's state starts to evolve dynamically in time.</div><div><br></div><div>Another technique is the <i>time-dependent generalized polynomial chaos</i> (TD-gPC) which utilizes a time-dependent orthogonal basis to better represent the stochastic part of the solution space (aka random function space or RFS) in time. The development of this technique was motivated by the fact that the probability distribution of the solution changes with time, which in turn requires that the random basis is frequently updated during the simulation to ensure that the mean-square error is kept orthogonal to the discretized RFS. Though this technique works well for problems that feature strong nonlinear dependencies over the probability space, the TD-gPC method possesses a serious issue: it suffers from the curse of dimensionality at the RFS level. This is because in all gPC-based methods the RFS is constructed using a tensor product of vector spaces with each of these representing a single RFS over one of the dimensions of the probability space. As a result, the higher the dimensionality of the probability space, the more vector spaces needed in the construction of a suitable RFS. To reduce the dimensionality of the RFS (and thus, its associated computational cost), gPC-based methods require the use of versatile sparse tensor products within their numerical schemes to alleviate to some extent the curse of dimensionality at the RFS level. Therefore, this curse of dimensionality in the TD-gPC method alludes to the need of developing a more compelling spectral method that can quantify uncertainties in long-time response of dynamical systems at much lower computational cost.</div><div><br></div><div>In this work, a novel numerical method based on the spectral approach is proposed to resolve the curse-of-dimensionality issue mentioned above. The method has been called the <i>flow-driven spectral chaos</i> (FSC) because it uses a novel concept called <i>enriched stochastic flow maps</i> to track the evolution of a finite-dimensional RFS efficiently in time. The enriched stochastic flow map does not only push the system's state forward in time (as would a traditional stochastic flow map) but also its first few time derivatives. The push is performed this way to allow the random basis to be constructed using the system's enriched state as a germ during the simulation and so as to guarantee exponential convergence to the solution. It is worth noting that this exponential convergence is achieved in the FSC method by using only a few number of random basis vectors, even when the dimensionality of the probability space is considerably high. This is for two reasons: (1) the cardinality of the random basis does not depend upon the dimensionality of the probability space, and (2) the cardinality is bounded from above by <i>M+n+1</i>, where <i>M</i> is the order of the stochastic flow map and <i>n</i> is the order of the governing stochastic ODE. The boundedness of the random basis from above is what makes the FSC method be curse-of-dimensionality free at the RFS level. For instance, for a dynamical system that is governed by a second-order stochastic ODE (<i>n=2</i>) and driven by a stochastic flow map of fourth-order (<i>M=4</i>), the maximum number of random basis vectors to consider within the FSC scheme is just 7, independent whether the dimensionality of the probability space is as low as 1 or as high as 10,000.</div><div><br></div><div>With the aim of reducing the complexity of the presentation, this dissertation includes three levels of abstraction for the FSC method, namely: a <i>specialized version</i> of the FSC method for dealing with structural dynamical systems subjected to uncertainties (Chapter 2), a <i>generalized version</i> of the FSC method for dealing with dynamical systems governed by (nonlinear) stochastic ODEs of arbitrary order (Chapter 3), and a <i>multi-element version</i> of the FSC method for dealing with dynamical systems that exhibit discontinuities over the probability space (Chapter 4). This dissertation also includes an implementation of the FSC method to address the dynamics of large-scale stochastic structural systems more effectively (Chapter 5). The implementation is done via a modal decomposition of the spatial function space as a means to reduce the number of degrees of freedom in the system substantially, and thus, save computational runtime.</div>

<p>In the real world, uncertainty is a common challenging problem faced by individuals, organizations, and firms. Decision quality is highly impacted by uncertainty because decision makers lack complete information and have to leverage the loss and gain in many possible outcomes or scenarios. This study explores dynamic decision making (with known distributions) and decision learning (with unknown distributions but some samples) in not-for-profit operations and supply chain management. We first study dynamic staffing for paid workers and volunteers with uncertain supply in a nonprofit operation where the optimal policy is too complex to compute and implement. Then, we consider dynamic inventory control and pricing under both supply and demand uncertainties where unmet demand is lost leading to a challenging non-concave dynamic problem. Furthermore, we explore decision learning from limited data of focal system and available data of related but different systems by transfer learning, cross learning, and co-learning utilizing the similarities among related systems.</p>

No description available.

No description available.

We present results that span three interconnected domains. Initially, our analysis is centred on Backward Stochastic Differential Equations (BSDEs) featuring time-delayed generators. Subsequently, we direct our interest towards Mean Field Games (MFGs) incorporating absorption aspects, with a focus on the corresponding Master Equation within a confined domain under the imposition of Dirichlet boundary conditions. The investigation culminates in exploring pertinent Machine Learning methodologies applied to financial and economic decision-making processes.

With the rapidly growing need for long-term decision making in the presence of stochastic future events, it is important to devise novel mathematical optimization tools and develop computationally efficient solution approaches for solving them. Two-stage stochastic programming is one of the powerful modeling tools that allows probabilistic data parameters in mixed integer programming, a well-known tool for optimization modeling with deterministic input data. However, akin to the mixed integer programs, these stochastic models are theoretically intractable and computationally challenging to solve because of the presence of integer variables. This dissertation focuses on theory, algorithms and applications of two-stage stochastic mixed integer (non)linear programs and it has three-pronged plan. In the first direction, we study two-stage stochastic p-order conic mixed integer programs (TSS-CMIPs) with p-order conic terms in the second-stage objectives. We develop so called scenario-based (non)linear cuts which are added to the deterministic equivalent of TSS-CMIPs (a large-scale deterministic conic mixed integer program). We provide conditions under which these cuts are sufficient to relax the integrality restrictions on the second-stage integer variables without impacting the integrality of the optimal solution of the TSS-CMIP. We also introduce a multi-module capacitated stochastic facility location problem and TSS-CMIPs with structured CMIPs in the second stage to demonstrate the significance of the foregoing results for solving these problems. In the second direction, we propose risk-neutral and risk-averse two-stage stochastic mixed integer linear programs for load shed recovery with uncertain renewable generation and demand. The models are implemented using a scenario-based approach where the objective is to maximize load shed recovery in the bulk transmission network by switching transmission lines and performing other corrective actions (e.g. generator re-dispatch) after the topology is modified. Experiments highlight how the proposed approach can serve as an offline contingency analysis tool, and how this method aids self-healing by recovering more load shedding. In the third direction, we develop a dual decomposition approach for solving two-stage stochastic quadratically constrained quadratic mixed integer programs. We also create a new module for an open-source package DSP (Decomposition for Structured Programming) to solve this problem. We evaluate the effectiveness of this module and our approach by solving a stochastic quadratic facility location problem. / Doctor of Philosophy / With the rapidly growing need for long-term decision making in the presence of stochastic future events, it is important to devise novel mathematical optimization tools and develop computationally efficient solution approaches for solving them. Two-stage stochastic programming is one of the powerful modeling tools that allows two-stages of decision making where the first-stage strategic decisions (such as deciding the locations of facilities or topology of a power transmission network) are taken before the realization of uncertainty, and the second-stage operational decisions (such as transportation decisions between customers and facilities or power flow in the transmission network) are taken in response to the first-stage decision and a realization of the uncertain (demand) data. This modeling tool is gaining wide acceptance because of its applications in healthcare, power systems, wildfire planning, logistics, and chemical industries, among others. Though intriguing, two-stage stochastic programs are computationally challenging. Therefore, it is crucial to develop theoretical results and computationally efficient algorithms, so that these models for real-world applied problems can be solved in a realistic time frame. In this dissertation, we consider two-stage stochastic mixed integer (non)linear programs, provide theoretical and algorithmic results for them, and introduce their applications in logistics and power systems. First, we consider a two-stage stochastic mixed integer program with p-order conic terms in the objective that has applications in facility location problem, power system, portfolio optimization, and many more. We provide a so-called second-stage convexification technique which greatly reduces the computational time to solve a facility location problem, in comparison to solving it directly with a state-of-the-art solver, CPLEX, with its default settings. Second, we introduce risk-averse and risk-neutral two-stage stochastic models to deal with uncertainties in power systems, as well as the risk preference of decision makers. We leverage the inherent flexibility of the bulk transmission network through the systematic switching of transmission lines in/out of service while accounting for uncertainty in generation and demand during an emergency. We provide abundant computational experiments to quantify our proposed models, and justify how the proposed approach can serve as an offline contingency analysis tool. Third, we develop a new solution approach for two-stage stochastic mixed integer programs with quadratic terms in the objective function and constraints and implement it as a new module for an open-source package DSP We perform computational experiments on a stochastic quadratic facility location problem to evaluate the performance of this module.

Master of Science / Department of Agricultural Economics / Timothy J. Dalton / In Kenya, agriculture governs the country’s fiscal economy, and this reliance on agriculture can cause both economic and hunger problems, a result of the country’s dependence upon rainfall for agricultural production. Kenyans must find ways to combat severe drought conditions; this can be accomplished through the adoption of inputs that decrease the probability of crop failure. The objective of this research is to determine whether variability exists in Kenyan maize yields, and whether or not specific inputs, specifically hybrid varieties, are either variance/skewness increasing or decreasing. The data used for this study was collected from a survey, designed by Egerton University’s Tegemeo Institute of Agricultural Policy and Development and Michigan State University, and administered in Kenya in the following years: 1997, 2000, 2004, and 2007. The survey identified factors of crop and field level production, such as inputs, crop mix, marketing data, and demographic information. This research makes use of only the 2007 data, comprising 1,397 households in total. The objectives of this thesis aim to go beyond the scope of typical production function regressions where yield is a function of a set of inputs, by examining further moments of yield, variance, and skewness to determine whether variability exists in Kenyan maize yields. Results indicate that variability does exist within Kenyan maize yields, often a result of differing input levels among households. In terms of overall impact of each variable on mean, variance, and skewness of maize yields, seed quantity, nitrogen use, and hybrid seed contribute the most to influencing these factors. In contrast, years of experience with hybrid maize, land tenure, terraced land and labor have the least influence on mean, variance and skewness within this research. Results also bring to light the popular debate against hybrid varieties versus open pollinated (OPV) or traditional varieties, and identify hybrid varieties as a source of variability in mean, variance and skewness of yields. Hybrid varieties should be paired with the knowledge of how to maximize yield in conjunction with other inputs, to give Kenya the opportunity to see substantial productivity gains throughout the country, especially in arid and semi-arid regions.