How does a stochastic optimization/approximation algorithm adapt to a randomly evolving optimum/root with jump Markov sample paths

Stochastic optimization/approximation algorithms are widely used to recursively estimate the optimum of a suitable function or its root under noisy observations when this optimum or root is a constant or evolves randomly according to slowly time-varying continuous sample paths. In comparison, this paper analyzes the asymptotic properties of stochastic optimization/approximation algorithms for recursively estimating the optimum or root when it evolves rapidly with nonsmooth (jump-changing) sample paths. The resulting problem falls into the category of regime-switching stochastic approximation algorithms with two-time scales. Motivated by emerging applications in wireless communications, and system identification, we analyze asymptotic behavior of such algorithms. Our analysis assumes that the noisy observations contain a (nonsmooth) jump process modeled by a discrete-time Markov chain whose transition frequency varies much faster than the adaptation rate of the stochastic optimization algorithm. Using stochastic averaging, we prove convergence of the algorithm. Rate of convergence of the algorithm is obtained via bounds on the estimation errors and diffusion approximations. Remarks on improving the convergence rates through iterate averaging, and limit mean dynamics represented by differential inclusions are also presented. The research of G. Yin was supported in part by the National Science Foundation under DMS-0603287, in part by the National Security Agency under MSPF-068-029, and in part by the National Natural Science Foundation of China under #60574069. The research of C. Ion was supported in part by the Wayne State University Rumble Fellowship. The research of V. Krishnamurthy was supported in part by NSERC (Canada).     

Stochastic contagion models without immunity: their long term behaviour and the optimal level of treatment

In this paper we analyze two stochastic versions of one of the simplest classes of contagion models, namely so-called SIS models. Several formulations of such models, based on stochastic differential equations, have been recently discussed in literature, mainly with a focus on the existence and uniqueness of stationary distributions. With applicability in view, the present paper uses the Fokker–Planck equations related to SIS stochastic differential equations, not only in order to derive basic facts, but also to derive explicit expressions for stationary densities and further characteristics related to the asymptotic behaviour. Two types of models are analyzed here: The first one is a version of the SIS model with external parameter noise and saturated incidence. The second one is based on the Kramers–Moyal approximation of the simple SIS Markov chain model, which leads to a model with scaled additive noise. In both cases we analyze the asymptotic behaviour, which leads to limiting stationary distributions in the first case and limiting quasistationary distributions in the second case. Finally, we use the derived properties for analyzing the decision problem of choosing the cost-optimal level of treatment intensity.

     

Asymptotically optimal production policies in dynamic stochastic jobshops with limited buffers

We consider a production planning problem for a jobshop with unreliable machines producing a number of products. There are upper and lower bounds on intermediate parts and an upper bound on finished parts. The machine capacities are modelled as finite state Markov chains. The objective is to choose the rate of production so as to minimize the total discounted cost of inventory and production. Finding an optimal control policy for this problem is difficult. Instead, we derive an asymptotic approximation by letting the rates of change of the machine states approach infinity. The asymptotic analysis leads to a limiting problem in which the stochastic machine capacities are replaced by their equilibrium mean capacities. The value function for the original problem is shown to converge to the value function of the limiting problem. The convergence rate of the value function together with the error estimate for the constructed asymptotic optimal production policies are established.     

Parameter estimation in stochastic differential equations with Markov chain Monte Carlo and non-linear Kalman filtering

This paper is concerned with parameter estimation in linear and non-linear Itô type stochastic differential equations using Markov chain Monte Carlo (MCMC) methods. The MCMC methods studied in this paper are the Metropolis–Hastings and Hamiltonian Monte Carlo (HMC) algorithms. In these kind of models, the computation of the energy function gradient needed by HMC and gradient based optimization methods is non-trivial, and here we show how the gradient can be computed with a linear or non-linear Kalman filter-like recursion. We shall also show how in the linear case the differential equations in the gradient recursion equations can be solved using the matrix fraction decomposition. Numerical results for simulated examples are presented and discussed in detail.     

Stochastic differential inclusions and diffusion processes

Connections between weak solutions of stochastic differential inclusions and solutions of partial differential inclusions, generated by given set-valued mappings are considered. The main results are based on some continuous approximation selection theorem and weak compactness of the set of all weak solutions to a given stochastic differential inclusion.     

Solvability of Langevin differential inclusions with set-valued diffusion terms on Riemannian manifolds

The existence of weak solution is proved for a Langevin type second-order stochastic differential inclusion on a complete Riemannian manifold, having both drift and diffusion terms set-valued. The construction of solution involves integral operators with Riemannian parallel translation and a special sequence of continuous ?-approximations for an upper semicontinuous set-valued mapping with convex bounded closed values, that is proved to converge point-wise to a Borel measurable selection.     

A self-dual variational approach to stochastic partial differential equations

Unlike many of their deterministic counterparts, stochastic partial differential equations are not amenable to the methods of calculus of variations à la Euler–Lagrange. In this paper, we show how self-dual variational calculus leads to variational solutions of various stochastic partial differential equations driven by monotone vector fields. We construct solutions as minima of suitable non-negative and self-dual energy functionals on Itô spaces of stochastic processes. We show how a stochastic version of Bolza's duality leads to solutions for equations with additive noise. We then use a Hamiltonian formulation to construct solutions for non-linear equations with non-additive noise such as the stochastic Navier–Stokes equations in dimension two.     

Discretization error of irregular sampling approximations of stochastic integrals

This paper studies the limit distributions for discretization error of irregular sampling approximations of stochastic integral. The irregular sampling approximation was first presented in Hayashi et al.[3], which was more general than the sampling approximation in Lindberg and Rootz′en [10]. As applications, we derive the asymptotic distribution of hedging error and the Euler scheme of stochastic differential equation respectively.     

A class of split-step balanced methods for stiff stochastic differential equations

In this paper we design a class of general split-step balanced methods for solving It? stochastic differential systems with m-dimensional multiplicative noise, in which the drift or deterministic increment function can be taken from any chosen one-step ODE solver. We then give an analysis of their order of strong convergence in a general setting, but for the mean-square stability analysis, we confine our investigation to a special case in which the drift increment function of the methods is replaced by the one from the well known Rosenbrock method. The resulting class of stochastic differential equation (SDE) solvers will have more appropriate and useful mean-square stability properties for SDEs with stiffness in their drift and diffusion parts, compared to some other already reported split-step balanced methods. Finally, numerical results show the effectiveness of these methods.     

Stochastic approximation with long range dependent and heavy tailed noise

Stability and convergence properties of stochastic approximation algorithms are analyzed when the noise includes a long range dependent component (modeled by a fractional Brownian motion) and a heavy tailed component (modeled by a symmetric stable process), in addition to the usual ‘martingale noise’. This is motivated by the emergent applications in communications. The proofs are based on comparing suitably interpolated iterates with a limiting ordinary differential equation. Related issues such as asynchronous implementations, Markov noise, etc. are briefly discussed.     

Stochastic recursive inclusion in two timescales with an application to the Lagrangian dual problem

In this paper we present a framework to analyze the asymptotic behavior of two timescale stochastic approximation algorithms including those with set-valued mean fields. This paper builds on the works of Borkar and Perkins & Leslie. The framework presented herein is more general as compared to the synchronous two timescale framework of Perkins & Leslie, however the assumptions involved are easily verifiable. As an application, we use this framework to analyze the two timescale stochastic approximation algorithm corresponding to the Lagrangian dual problem in optimization theory.     

Asymptotic analysis of P.D.E.s with wide–band noise disturbances,and expansion of the moments

We present an asymptotic analysis -in the “ white-noise limit”- of a linear parabolic partial differential equation, whose coefficients are perturbed by a wide-band noise. After having studied some ergodic properties of a class of diffusion processes, we prove the convergence in law towards the solution of an Ito stochastic P.D.E. We then establish an expansion in powers of Δ ( 1/Δ being a measure of the bandwith of the driving noise) of the first moment of the solution     

Yosida approximations for multivalued stochastic partial differential equations driven by Lévy noise on a Gelfand triple

We prove the existence and uniqueness of solutions for a class of multivalued stochastic partial differential equations with maximal monotone drift on Banach space driven by multiplicative Lévy noise. We also establish the strong convergence result for solutions of the approximating equations where the maximal monotone drift operator is replaced by its Yosida approximation. As an application, the existence and uniqueness of solutions for multivalued stochastic porous medium equations is obtained.     

A variable step-size control algorithm for the weak approximation of stochastic differential equations

In this paper, we propose two local error estimates based on drift and diffusion terms of the stochastic differential equations in order to determine the optimal step-size for the next stage in an adaptive variable step-size algorithm. These local error estimates are based on the weak approximation solution of stochastic differential equations with one-dimensional and multi-dimensional Wiener processes. Numerical experiments are presented to illustrate the effectiveness of this approach in the weak approximation of several standard test problems including SDEs with small noise and scalar and multi-dimensional Wiener processes.     

Approximation for non-smooth functionals of stochastic differential equations with irregular drift

This paper aims at developing a systematic study for the weak rate of convergence of the Euler–Maruyama scheme for stochastic differential equations with very irregular drift and constant diffusion coefficients. We apply our method to obtain the rates of approximation for the expectation of various non-smooth functionals of both stochastic differential equations and killed diffusion. We also apply our method to the study of the weak approximation of reflected stochastic differential equations whose drift is Hölder continuous.     

The Limit Behaviour of Imprecise Continuous-Time Markov Chains

We study the limit behaviour of a nonlinear differential equation whose solution is a superadditive generalisation of a stochastic matrix, prove convergence, and provide necessary and sufficient conditions for ergodicity. In the linear case, the solution of our differential equation is equal to the matrix exponential of an intensity matrix and can then be interpreted as the transition operator of a homogeneous continuous-time Markov chain. Similarly, in the generalised nonlinear case that we consider, the solution can be interpreted as the lower transition operator of a specific set of non-homogeneous continuous-time Markov chains, called an imprecise continuous-time Markov chain. In this context, our convergence result shows that for a fixed initial state, an imprecise continuous-time Markov chain always converges to a limiting distribution, and our ergodicity result provides a necessary and sufficient condition for this limiting distribution to be independent of the initial state.     

Set-valved Markov Processes and Their Representation Theorems

Ｓｅｔ－ｖａｌｖｅｄＭａｒｋｏｖＰｒｏｃｅｓｓｅｓａｎｄＴｈｅｉｒＲｅｐｒｅｓｅｎｔａｔｉｏｎＴｈｅｏｒｅｍｓＸｕＭｉｎｇｙｕｅ（徐明跃）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＨａｖｅｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｈａｒｂｉｎ，１５...     

Stochastic Systems with Averaging in the Scheme of Diffusion Approximation

We propose a system approach to the asymptotic analysis of stochastic systems in the scheme of series with averaging and diffusion approximation. Stochastic systems are defined by Markov processes with locally independent increments in a Euclidean space with random switchings that are described by jump Markov and semi-Markov processes. We use the asymptotic analysis of Markov and semi-Markov random evolutions. We construct the diffusion approximation using the asymptotic decomposition of generating operators and solutions of problems of singular perturbation for reducibly inverse operators. __________ Translated from Ukrains'kyi Matematychnyi Zhurnal, Vol. 57, No. 9, pp. 1235–1252, September, 2005.     

Random attractors for stochastic differential equations driven by two-sided Lévy processes

Abstract

In this paper, the asymptotic behavior of solutions for a nonlinear Marcus stochastic differential equation with multiplicative two-sided Lévy noise is studied. We plan to consider this equation as a random dynamical system. Thus, we have to interpret a Lévy noise as a two-sided metric dynamical system. For that, we have to introduce some fundamental properties of such a noise. So far most studies have only discussed two-sided Lévy processes which are defined by combining two-independent Lévy processes. In this paper, we use another definition of two-sided Lévy process by expanding the probability space. Having this metric dynamical system we will show that the Marcus stochastic differential equation with a particular drift coefficient and multiplicative noise generates a random dynamical system which has a random attractor.     

Likelihood-based confidence bands for fault lines in response surfaces

 We consider the problem of constructing asymptotic confidence bands, both pointwise and simultaneous, for a smooth fault line in a response surface when the design is represented by a point process, either deterministic or stochastic, with intensity n diverging to infinity. The estimator of the fault line is defined as the ridge line on the likelihood surface which arises from locally fitting a model that employs a linear approximation to the fault line, to a kernel smooth of the data. The construction is based on analysis of the limiting behaviour of perpendicular distance from a point on the true fault line to the nearest point on the ridge. We derive asymptotic properties of bias, and the limiting distribution of stochastic error. This distribution is given by the location of the maximum of a Gaussian process with quadratic drift. Although the majority of attention is focused on the regression problem, the limiting distribution is shown to have wider relevance to local-likelihood approaches to fault line estimation for density or intensity surfaces. Received: 20 August 2000 / Revised version: 27 September 2001 / Published online: 22 August 2002