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.

该研究项目涉及开发有效的蒙特卡洛算法，以进行罕见的事件模拟和相关的大偏差理论。我们考虑了两种广泛的问题，罕见事件要么是直接兴趣或蒙特卡洛计划表现的决定因素。对于第一类问题，重要的采样和粒子分支方法已被证明是强大的工具。设计这些类型方案的一种统一方法是利用精心设计的方案与相关的汉密尔顿 - 雅各比 - 贝尔曼方程之间的重要联系。该方法已成功应用于分段同质动态（例如排队网络）。该研究项目旨在考虑更复杂的模型，例如动态完全非线性的快速振荡组件的小噪声扩散。 关于第二类问题，一个特别重要的主题是通过相关的马尔可夫过程的占用度量，对具有多个亚稳态状态的系统的不变分布近似。从一个亚稳态到另一个状态是罕见的事件，其处理是高效蒙特卡洛计划设计的关键问题。有许多临时算法可用。 但是，这些算法并不总是很好地工作，并且必须谨慎使用。该研究项目将严格分析一些现有算法，并设计具有更好性能的新算法。对于此问题特别感兴趣的两类快速模拟方案是平行的回火和重要性采样。在许多科学分支中，例如生物学，化学，物理和工程学，对罕见事件或发生的罕见事件的研究通常是核心利益。例如，在蛋白质或生物分子的研究中，采用基于物理的模型来研究原子或分子的相互作用。由于模型的复杂性，分析计算是不可能的，而分析的主要工具是模拟，它为系统的动态演变提供了宝贵的见解。但是，模拟可能需要非常长时间的时间才能将系统从一种配置移动到另一种配置（罕见事件）。 在高度可靠和安全的系统的背景下，罕见的事件是避免的，而准确的评估是设计目的的关键工具。为了在重要罕见事件的情况下加速模拟，已经提出了许多临时算法。对于许多缺乏牢固理论基础的计划，通常仅根据先前的经验选择关键设计数量。 结果，这些方案可能在专业情况下起作用，但总体上的表现也很差。该研究项目有两个目标。一个是对现有方案的严格分析，这对于理解方案的力量及其局限性非常有用。 第二个目标是基于对现有方法的分析，其绩效比现有方案更好的新方案。这项工作将不仅用于对罕见事件模拟感兴趣的理论家使用，而且还将用于将模拟作为研究基本工具的大型从业者和科学家社区。