Stochastic global optimization as a filtering problem

We present a reformulation of stochastic global optimization as a filtering problem. The motivation behind this reformulation comes from the fact that for many optimization problems we cannot evaluate exactly the objective function to be optimized. Similarly, we may not be able to evaluate exactly the functions involved in iterative optimization algorithms. For example, we may only have access to noisy measurements of the functions or statistical estimates provided through Monte Carlo sampling. This makes iterative optimization algorithms behave like stochastic maps. Naive global optimization amounts to evolving a collection of realizations of this stochastic map and picking the realization with the best properties. This motivates the use of filtering techniques to allow focusing on realizations that are more promising than others. In particular, we present a filtering reformulation of global optimization in terms of a special case of sequential importance sampling methods called particle filters. The increasing popularity of particle filters is based on the simplicity of their implementation and their flexibility. We utilize the flexibility of particle filters to construct a stochastic global optimization algorithm which can converge to the optimal solution appreciably faster than naive global optimization. Several examples of parametric exponential density estimation are provided to demonstrate the efficiency of the approach.     

A Bayesian tutorial for data assimilation

Data assimilation is the process by which observational data are fused with scientific information. The Bayesian paradigm provides a coherent probabilistic approach for combining information, and thus is an appropriate framework for data assimilation. Viewing data assimilation as a problem in Bayesian statistics is not new. However, the field of Bayesian statistics is rapidly evolving and new approaches for model construction and sampling have been utilized recently in a wide variety of disciplines to combine information. This article includes a brief introduction to Bayesian methods. Paying particular attention to data assimilation, we review linkages to optimal interpolation, kriging, Kalman filtering, smoothing, and variational analysis. Discussion is provided concerning Monte Carlo methods for implementing Bayesian analysis, including importance sampling, particle filtering, ensemble Kalman filtering, and Markov chain Monte Carlo sampling. Finally, hierarchical Bayesian modeling is reviewed. We indicate how this approach can be used to incorporate significant physically based prior information into statistical models, thereby accounting for uncertainty. The approach is illustrated in a simplified advection–diffusion model.     

Generalized Langevin equation driven by Lévy processes: A probabilistic, numerical and time series based approach

Lévy processes have been widely used to model a large variety of stochastic processes under anomalous diffusion. In this note we show that Lévy processes play an important role in the study of the Generalized Langevin Equation (GLE). The solution to the GLE is proposed using stochastic integration in the sense of convergence in probability. Properties of the solution processes are obtained and numerical methods for stochastic integration are developed and applied to examples. Time series methods are applied to obtain estimation formulas for parameters related to the solution process. A Monte Carlo simulation study shows the estimation of the memory function parameter. We also estimate the stability index parameter when the noise is a Lévy process.     

Estimating parameters in stochastic systems: A variational Bayesian approach

This work is concerned with approximate inference in dynamical systems, from a variational Bayesian perspective. When modelling real world dynamical systems, stochastic differential equations appear as a natural choice, mainly because of their ability to model the noise of the system by adding a variation of some stochastic process to the deterministic dynamics. Hence, inference in such processes has drawn much attention. Here a new extended framework is derived that is based on a local polynomial approximation of a recently proposed variational Bayesian algorithm. The paper begins by showing that the new extension of this variational algorithm can be used for state estimation (smoothing) and converges to the original algorithm. However, the main focus is on estimating the (hyper-) parameters of these systems (i.e. drift parameters and diffusion coefficients). The new approach is validated on a range of different systems which vary in dimensionality and non-linearity. These are the Ornstein-Uhlenbeck process, the exact likelihood of which can be computed analytically, the univariate and highly non-linear, stochastic double well and the multivariate chaotic stochastic Lorenz ’63 (3D model). As a special case the algorithm is also applied to the 40 dimensional stochastic Lorenz ’96 system. In our investigation we compare this new approach with a variety of other well known methods, such as the hybrid Monte Carlo, dual unscented Kalman filter, full weak-constraint 4D-Var algorithm and analyse empirically their asymptotic behaviour as a function of observation density or length of time window increases. In particular we show that we are able to estimate parameters in both the drift (deterministic) and the diffusion (stochastic) part of the model evolution equations using our new methods.     

A Eulerian PDF scheme for LES of nonpremixed turbulent combustion with second-order accurate mixture fraction

Monte Carlo simulations of joint probability density function (PDF) approaches have been developed in the past largely with Reynolds averaged Navier Stokes (RANS) applications. Current interests are in the extension of PDF approaches to large eddy simulation (LES). As LES resolves accurately the large scales of turbulence in time, the Monte Carlo simulation and the flow field need to be tightly coupled. A tight coupling can be achieved if the consistency between the scalar field solution obtained via finite-volume (FV) methods and that from the stochastic solution of the PDF is ensured. For nonpremixed turbulent flames with two distinct streams, the local reactive mixture is described by the mixture fraction. A Eulerian Monte Carlo method is developed to achieve a second-order accuracy in the instantaneous filtered mixture fraction that is consistent with the corresponding FV. The performances of the proposed scheme are extensively evaluated using a one-dimensional model. Then, the scheme is applied to two cases with LES. The first one is a non-reacting mixing flow of two different fluids. The second case is the Sandia piloted turbulent flame D with a steady state flamelet model. Both results confirm the consistency of the proposed method to the level of filtered mixture fraction.     

Efficient gradient estimation using finite differencing and likelihood ratios for kinetic Monte Carlo simulations

While many optimization and control methods for stochastic processes require gradient information from the process of interest, obtaining gradient information from experiments is prohibitively expensive and time-consuming. As a result, such information is often obtained from stochastic process simulations. Computing gradients efficiently and accurately from stochastic simulations is challenging, especially for simulations involving computationally expensive models with significant inherent noise. In this work, we analyze and characterize the applicability of two gradient estimation methods for kinetic Monte Carlo simulations: finite differencing and likelihood ratio. We developed a systematic method for choosing an optimal perturbation size for finite differencing and discuss, for both methods, important implementation issues such as scaling with respect to the number of elements in the gradient vector. Through a series of numerical experiments, the methods were compared across different time and size regimes to characterize the precision and accuracy associated with each method. We determined that the likelihood ratio method is appropriate for estimating gradients at short (transient) times or for systems with small population sizes, whereas finite differencing is better-suited for gradient estimation at long times (steady state) or for systems with large population sizes.     

Monte Carlo techniques for real-time quantum dynamics

The stochastic-gauge representation is a method of mapping the equation of motion for the quantum mechanical density operator onto a set of equivalent stochastic differential equations. One of the stochastic variables is termed the “weight”, and its magnitude is related to the importance of the stochastic trajectory. We investigate the use of Monte Carlo algorithms to improve the sampling of the weighted trajectories and thus reduce sampling error in a simulation of quantum dynamics. The method can be applied to calculations in real time, as well as imaginary time for which Monte Carlo algorithms are more-commonly used. The Monte-Carlo algorithms are applicable when the weight is guaranteed to be real, and we demonstrate how to ensure this is the case. Examples are given for the anharmonic oscillator, where large improvements over stochastic sampling are observed.     

Particle filtering with path sampling and an application to a bimodal ocean current model

This paper introduces a recursive particle filtering algorithm designed to filter high dimensional systems with complicated non-linear and non-Gaussian effects. The method incorporates a parallel marginalization (PMMC) step in conjunction with the hybrid Monte Carlo (HMC) scheme to improve samples generated by standard particle filters. Parallel marginalization is an efficient Markov chain Monte Carlo (MCMC) strategy that uses lower dimensional approximate marginal distributions of the target distribution to accelerate equilibration. As a validation the algorithm is tested on a 2516 dimensional, bimodal, stochastic model motivated by the Kuroshio current that runs along the Japanese coast. The results of this test indicate that the method is an attractive alternative for problems that require the generality of a particle filter but have been inaccessible due to the limitations of standard particle filtering strategies.     

Shadow hybrid Monte Carlo: an efficient propagator in phase space of macromolecules

Shadow hybrid Monte Carlo (SHMC) is a new method for sampling the phase space of large molecules, particularly biological molecules. It improves sampling of hybrid Monte Carlo (HMC) by allowing larger time steps and system sizes in the molecular dynamics (MD) step. The acceptance rate of HMC decreases exponentially with increasing system size N or time step δt. This is due to discretization errors introduced by the numerical integrator. SHMC achieves an asymptotic O(N^1/4) speedup over HMC by sampling from all of phase space using high order approximations to a shadow or modified Hamiltonian exactly integrated by a symplectic MD integrator. SHMC satisfies microscopic reversibility and is a rigorous sampling method. SHMC requires extra storage, modest computational overhead, and a reweighting step to obtain averages from the canonical ensemble. This is validated by numerical experiments that compute observables for different molecules, ranging from a small n-alkane butane with four united atoms to a larger solvated protein with 14,281 atoms. In these experiments, SHMC achieves an order magnitude speedup in sampling efficiency for medium sized proteins. Sampling efficiency is measured by monitoring the rate at which different conformations of the molecules' dihedral angles are visited, and by computing ergodic measures of some observables.     

“Exact” and Approximate Methods for Bayesian Inference: Stochastic Volatility Case Study

We conduct a case study in which we empirically illustrate the performance of different classes of Bayesian inference methods to estimate stochastic volatility models. In particular, we consider how different particle filtering methods affect the variance of the estimated likelihood. We review and compare particle Markov Chain Monte Carlo (MCMC), RMHMC, fixed-form variational Bayes, and integrated nested Laplace approximation to estimate the posterior distribution of the parameters. Additionally, we conduct the review from the point of view of whether these methods are (1) easily adaptable to different model specifications; (2) adaptable to higher dimensions of the model in a straightforward way; (3) feasible in the multivariate case. We show that when using the stochastic volatility model for methods comparison, various data-generating processes have to be considered to make a fair assessment of the methods. Finally, we present a challenging specification of the multivariate stochastic volatility model, which is rarely used to illustrate the methods but constitutes an important practical application.     

热辐射输运问题的高效蒙特卡罗模拟方法

惯性约束聚变研究中,热辐射光子在介质中的输运以及热辐射光子与介质的相互作用是重要研究课题,蒙特卡罗方法是该类问题的重要研究手段之一.隐式蒙特卡罗方法虽然能正确地模拟热辐射在介质中的输运过程,但当模拟重介质(材料的吸收系数大)问题时,该方法花费的计算时间将变得很长,导致模拟效率很低.本文以离散扩散蒙特卡罗方法为基础,开发了"离散扩散蒙特卡罗方法辐射输运模拟程序",可以较好地解决重介质区的计算效率问题,但是离散扩散蒙卡罗方法在模拟轻介质区时精度不够高.辐射输运问题中通常既有轻介质也有重介质,为了能同时解决蒙特卡罗方法模拟的效率和精度问题,本文研究了离散扩散蒙特卡罗方法与隐式蒙特卡罗方法相结合的模拟方法,并提出了新的扩散区与输运区界面处理方法,研制了混合蒙特卡罗方法的辐射输运模拟程序.典型辐射输运问题模拟显示:在模拟重介质问题时,该程序能大幅缩短模拟时间,且能取得与隐式蒙特卡罗方法一致的结果;在模拟轻重介质均存在的问题时,与隐式蒙特卡罗方法相比,混合蒙特卡罗方法的模拟精度与其相当且计算效率同样能够得到显著提升.     

A high accuracy stochastic estimation of a nonlinear deterministic model

In this Letter, an approach to estimating a nonlinear deterministic model is presented. We introduce a stochastic model with extremely small variances so that the deterministic and stochastic models are essentially indistinguishable from each other. This point is explained in the Letter. The estimation is then carried out using stochastic optimization based on Markov chain Monte Carlo (MCMC) methods.     

基于禁忌搜索的车联网蒙特卡洛定位算法

在蒙特卡洛定位算法中引入禁忌搜索算法以提高车联网中快速定位的性能。自组织车联网高速移动的车辆和快速变化的网络拓扑结构,使用传统的蒙特卡洛定位算法,不能迅速的收敛位置信息。在滤波阶段引入禁忌搜索算法对传统蒙特卡洛定位算法进行改进, 优化滤波排除可能性较小的位置点,获得近似最优估计位置采样集。仿真结果表明,改进后的算法在样本采集数、计算时间、定位精度等方面有了显著提升,改进后的算法能更好地解决车联网的定位问题。     

Large Time Behavior and Convergence Rate for Quantum Filters Under Standard Non Demolition Conditions

A quantum system \({\mathcal S}\) undergoing continuous time measurement is usually described by a jump-diffusion stochastic differential equation. Such an equation is called a quantum filtering equation (or quantum stochastic master equation) and its solution is called a quantum filter (or quantum trajectory). This solution describes the evolution of the state of \({\mathcal S}\) . In the context of quantum non demolition measurement, we investigate the large time behavior of this solution. It is rigorously shown that, for large time, this solution behaves as if a direct Von Neumann measurement has been performed at time 0. In particular the solution converges to a random pure state which can be directly linked to the wave packet reduction postulate. Using the theory of Girsanov transformation, we obtain the explicit rate of convergence towards this random state. The problem of state estimation (used in experiment) is also investigated.     

Statistical equilibrium in simple exchange games I

Simple stochastic exchange games are based on random allocation of finite resources. These games are Markov chains that can be studied either analytically or by Monte Carlo simulations. In particular, the equilibrium distribution can be derived either by direct diagonalization of the transition matrix, or using the detailed balance equation, or by Monte Carlo estimates. In this paper, these methods are introduced and applied to the Bennati-Dragulescu-Yakovenko (BDY) game. The exact analysis shows that the statistical-mechanical analogies used in the previous literature have to be revised. An erratum to this article is available at .     

Linear-scaling and parallelisable algorithms for stochastic quantum chemistry

For many decades, quantum chemical method development has been dominated by algorithms which involve increasingly complex series of tensor contractions over one-electron orbital spaces. Procedures for their derivation and implementation have evolved to require the minimum amount of logic and rely heavily on computationally efficient library-based matrix algebra and optimised paging schemes. In this regard, the recent development of exact stochastic quantum chemical algorithms to reduce computational scaling and memory overhead requires a contrasting algorithmic philosophy, but one which when implemented efficiently can achieve higher accuracy/cost ratios with small random errors. Additionally, they can exploit the continuing trend for massive parallelisation which hinders the progress of deterministic high-level quantum chemical algorithms. In the Quantum Monte Carlo community, stochastic algorithms are ubiquitous but the discrete Fock space of quantum chemical methods is often unfamiliar, and the methods introduce new concepts required for algorithmic efficiency. In this paper, we explore these concepts and detail an algorithm used for Full Configuration Interaction Quantum Monte Carlo (FCIQMC), which is implemented and available in MOLPRO and as a standalone code, and is designed for high-level parallelism and linear-scaling with walker number. Many of the algorithms are also in use in, or can be transferred to, other stochastic quantum chemical methods and implementations. We apply these algorithms to the strongly correlated chromium dimer to demonstrate their efficiency and parallelism.     

An Analysis of Polynomial Chaos Approximations for Modeling Single-Fluid-Phase Flow in Porous Medium Systems

We examine a variety of polynomial-chaos-motivated approximations to a stochastic form of a steady state groundwater flow model. We consider approaches for truncating the infinite dimensional problem and producing decoupled systems. We discuss conditions under which such decoupling is possible and show that to generalize the known decoupling by numerical cubature, it would be necessary to find new multivariate cubature rules. Finally, we use the acceleration of Monte Carlo to compare the quality of polynomial models obtained for all approaches and find that in general the methods considered are more efficient than Monte Carlo for the relatively small domains considered in this work. A curse of dimensionality in the series expansion of the log-normal stochastic random field used to represent hydraulic conductivity provides a significant impediment to efficient approximations for large domains for all methods considered in this work, other than the Monte Carlo method.     

非定常粒子输运蒙特卡罗散射源分层抽样方法

定常粒子输运蒙特卡罗并行计算是成功的,因为粒子游动是独立的,可以把模拟的粒子数等分到每个处理器去.然而,对非定常问题,由于每个时间步涉及散射源和几何网格的通讯,它严重的制约了并行规模,导致并行不可扩展.研究了两种算法,采用自适应分配处理器,提高了加速比和处理器的利用率;采用蒙特卡罗分层抽样大大降低了处理器之间散射源的通讯量,并行可扩展性显著改善,取得了理想的加速比.     

Many-body approximation scheme beyond GW

We explore the combination of the extended dynamical mean field theory (EDMFT) with the GW approximation (GWA); the former sums the local contributions to the self-energies to infinite order in closed form and the latter handles the nonlocal ones to lowest order. We investigate the different levels of self-consistency that can be implemented within this method by comparing to the exact quantum Monte Carlo solution of a finite-size model Hamiltonian. We find that using the EDMFT solution for the local self-energies as input to the GWA for the nonlocal self-energies gives the best result.     

A linear stability analysis for nonlinear,grey, thermal radiative transfer problems

We present a new linear stability analysis of three time discretizations and Monte Carlo interpretations of the nonlinear, grey thermal radiative transfer (TRT) equations: the widely used “Implicit Monte Carlo” (IMC) equations, the Carter Forest (CF) equations, and the Ahrens–Larsen or “Semi-Analog Monte Carlo” (SMC) equations. Using a spatial Fourier analysis of the 1-D Implicit Monte Carlo (IMC) equations that are linearized about an equilibrium solution, we show that the IMC equations are unconditionally stable (undamped perturbations do not exist) if α, the IMC time-discretization parameter, satisfies 0.5 < α ? 1. This is consistent with conventional wisdom. However, we also show that for sufficiently large time steps, unphysical damped oscillations can exist that correspond to the lowest-frequency Fourier modes. After numerically confirming this result, we develop a method to assess the stability of any time discretization of the 0-D, nonlinear, grey, thermal radiative transfer problem. Subsequent analyses of the CF and SMC methods then demonstrate that the CF method is unconditionally stable and monotonic, but the SMC method is conditionally stable and permits unphysical oscillatory solutions that can prevent it from reaching equilibrium. This stability theory provides new conditions on the time step to guarantee monotonicity of the IMC solution, although they are likely too conservative to be used in practice. Theoretical predictions are tested and confirmed with numerical experiments.