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.

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