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.

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