Fast simulation, large deviations, and associated Hamilton-Jacobi-Bellman equations

快速仿真、大偏差和相关的 Hamilton-Jacobi-Bellman 方程

• 批准号: 1008331
• 负责人: Paul Dupuis
• 金额: $ 28万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1008331&HistoricalAwards=false
• 关键词: Fast; simulation; large; deviations; associated

This research project is concerned with developing efficient Monte Carlo algorithms for rare event simulation and the associated large deviations theory. We consider two broad classes of problems where rare events are either of direct interest or a determining factor of the performance of the Monte Carlo scheme. For the first class of problems, importance sampling and particle branching methods have proven to be powerful tools. A unifying approach for the design of these types of schemes is to exploit an important connection between well-designed schemes and the subsolutions to an associated Hamiltonian-Jacobi-Bellman equation. The approach has been successfully applied in the setting of piecewise homogenous dynamics such as queueing networks. The research project aims to consider more complicated models such as small noise diffusions with fast oscillating components where the dynamics are fully nonlinear. With regard to the second class of problems, a particularly important topic is the approximation of the invariant distribution for systems with multiple metastable states by the occupation measure of a related Markov process. Moving from one metastable state to another is a rare event, and its treatment is the key question in the design of efficient Monte Carlo schemes. There are many ad hoc algorithms available. However, these algorithms do not always work well and have to be applied with some care. The research project will rigorously analyze some existing algorithms as well as design new ones with better performance. Two classes of fast simulation schemes that are of particular interest for this problem are parallel tempering and importance sampling.In many branches of science, such as biology, chemistry, physics, and engineering, the study of rare events or events with very little chance of happening is often of central interest. For example, in the study of proteins or biomolecules, physics-based models are employed to study the interaction of atoms or molecules. Due to the complexity of the model, analytical calculation is impossible, and the primary tool of analysis is simulation, which provides valuable insight into the dynamic evolution of the system. However, the simulation can take an exceedingly long time before the system moves from one configuration to another (a rare event). In the context of highly reliable and secure systems, the rare event is something to be avoided, and accurate assessment is a key tool for purposes of design. To accelerate simulations in situations with important rare events, many ad hoc algorithms have been proposed. For the many schemes that lack a firm theoretical foundation, key design quantities are usually selected only on the basis of prior experience. As a consequence, these schemes may work in specialized situations, but can also perform quite poorly in general. This research project has two goals. One is the rigorous analysis of existing schemes, which can be very useful in understanding the power of the schemes as well as their limitations. The second goal is to develop, based on the analysis of existing approaches, new schemes whose performance is provably better than the existing ones. This work will be of use not only to theoreticians who are interested rare event simulation, but also to a large community of practitioners and scientists who use simulation as a basic tool for their research.

本研究项目是关于发展有效的蒙特卡罗算法的罕见事件模拟和相关的大偏差理论。我们考虑两大类问题，其中稀有事件要么是直接感兴趣的，要么是蒙特卡罗方案性能的决定因素。对于第一类问题，重要性采样和粒子分支方法已被证明是有效的工具。设计这类格式的统一方法是利用设计良好的格式与相关哈密顿-雅可比-贝尔曼方程的子解之间的重要联系。该方法已成功地应用于分段同质动力学的设置，如排队网络。该研究项目旨在考虑更复杂的模型，如具有快速振荡成分的小噪声扩散，其中动力学是完全非线性的。关于第二类问题，一个特别重要的主题是用相关马尔可夫过程的占用度量来逼近具有多个亚稳态的系统的不变分布。从一个亚稳态转移到另一个亚稳态是一个罕见的事件，它的处理是设计有效蒙特卡罗方案的关键问题。有许多特别的算法可用。然而，这些算法并不总是很好地工作，必须谨慎使用。本研究项目将严格分析现有的一些算法，并设计性能更好的新算法。对这一问题特别感兴趣的两类快速模拟方案是并行回火和重要采样。在许多科学分支中，如生物学、化学、物理学和工程学，对罕见事件或发生几率极低的事件的研究往往是人们感兴趣的中心问题。例如，在蛋白质或生物分子的研究中，基于物理的模型被用来研究原子或分子的相互作用。由于模型的复杂性，分析计算是不可能的，而分析的主要工具是仿真，这为了解系统的动态演变提供了有价值的见解。然而，在系统从一种配置转移到另一种配置之前，模拟可能会花费非常长的时间（这种情况很少见）。在高度可靠和安全的系统环境中，要避免罕见的事件，准确的评估是设计目的的关键工具。为了在具有重要罕见事件的情况下加速仿真，提出了许多自组织算法。对于许多缺乏坚实理论基础的方案，通常仅根据先前的经验选择关键设计量。因此，这些方案可能在特定的情况下工作，但在一般情况下也可能执行得很差。这个研究项目有两个目标。一种是对现有方案的严格分析，这对于理解方案的功能及其局限性非常有用。第二个目标是在分析现有方法的基础上，开发性能优于现有方法的新方案。这项工作不仅适用于对罕见事件模拟感兴趣的理论家，也适用于将模拟作为其研究基本工具的大型实践者和科学家社区。