Min-max representations of viscosity solutions of Hamilton-Jacobi equations and applications in rare-event simulation

Boualem Djehiche, Henrik Hult, Pierre NyquistarXiv 2014 · DOI · arXiv

Abstract

This paper derives a fundamental duality relation between the Mañé potential and Mather's action functional within the context of convex and state-dependent Hamiltonians. This duality is utilized to obtain min-max representations of viscosity solutions for first-order Hamilton-Jacobi (HJ) equations. These representations suggest a systematic class of subsolutions that arise in large deviation theory, which serve as robust candidates for designing efficient rare-event simulation algorithms, particularly in importance sampling and multi-level splitting frameworks.

Introduction

In critical infrastructure and financial systems, calculating the probability of "rare events"—such as a total power grid failure or a market collapse—is essential for risk management. However, standard Monte Carlo methods are computationally prohibitive for these scenarios; because the events occur so infrequently, an astronomical number of samples is required to achieve statistical significance.

To address this, researchers employ variance reduction techniques like importance sampling, which biases the simulation toward the rare event and corrects the result using weights. The efficiency of these techniques depends on finding an optimal "nudge" (change of measure), which Large Deviation Theory (LDT) links directly to the solutions of Hamilton-Jacobi (HJ) equations. While finding subsolutions to these equations is straightforward for simple systems, it becomes mathematically grueling for systems with state-dependent dynamics. This paper bridges that gap by providing a new theoretical framework for constructing these subsolutions.

Theoretical Framework: Duality and Min-Max Representations

The core of the paper’s contribution lies in connecting two concepts from dynamical systems theory:

  1. Mather’s Action Functional ($M$): Represents the minimum cost to transition from point A to point B in a fixed time $t$.
  2. Mañé Potential ($S^c$): Represents the minimum cost to transition between points over any duration, given a fixed energy level $c$.

Theorem 3.1: The Duality Relation

The authors prove that Mather’s action functional is essentially the Legendre transform of the Mañé potential: $$M(t, y; x) = \sup_{c > c_H} \{S^c(x, y) - ct\}$$ where $c_H$ is the Mañé critical value. This duality allows the authors to derive a min-max representation for viscosity solutions of time-dependent HJ equations. This formula generalizes the well-known Hopf-Lax-Oleinik formula. While the classical Hopf-Lax formula is restricted to Hamiltonians that are independent of position ($H(p)$), this new representation accommodates state-dependent Hamiltonians ($H(x, p)$), making it applicable to a much wider range of physical and stochastic systems.

Application to Rare-Event Simulation

The theoretical duality provides a "recipe" for constructing subsolutions to the HJ equation, which are necessary for efficient importance sampling. The suggested subsolution takes the form: $$U(t, x) = S^c(x, y) - c(T - t) - K$$

This approach offers several advantages:

  • Simplicity: It allows researchers to build time-dependent subsolutions from simpler, stationary potentials.
  • Robustness: A remarkable property of this construction is that the gradient of the subsolution—which dictates the simulation's bias—does not explicitly depend on the shape of the domain $\Omega$. This makes the algorithm highly effective for complex geometries.
  • Asymptotic Optimality: The authors demonstrate that if a saddle point exists for the min-max representation, the resulting simulation algorithm is asymptotically optimal, meaning the variance grows at the slowest possible rate as the event becomes rarer.

Numerical Validation

The authors tested their methodology on two classic stochastic models to evaluate numerical efficiency:

  1. Small-Noise Diffusions: Using a particle in a 1D double-well potential, the algorithm estimated a rare-event probability of $6.8 \times 10^{-17}$ with a relative error of just 0.033. For comparison, a standard Monte Carlo simulation would have required approximately $10^{18}$ samples to reach the same level of accuracy.
  2. Stochastic Epidemic Models: The method was applied to a Susceptible-Infectious-Susceptible (SIS) model to estimate the probability of an infection reaching a specific threshold before extinction, demonstrating the method's utility in birth-and-death processes.

Limitations and Future Directions

Despite the power of the min-max representation, some challenges remain:

  • Time Horizons: For very large time horizons ($T \to \infty$), the performance of these subsolutions may degrade as the optimal energy level $c$ nears the critical value $c_H$.
  • Computational Complexity: Calculating the Mañé potential $S^c(x, y)$ in high-dimensional spaces still requires solving stationary HJ equations, which remains a significant computational hurdle.
  • Saddle Point Assumptions: The proof for zero-loss performance assumes the existence of a saddle point, which may not be guaranteed for all boundary conditions or Hamiltonian types.

Conclusion

By establishing a formal duality between action functionals and stationary potentials, this work provides a systematic path for solving complex Hamilton-Jacobi equations. Beyond the theoretical contribution, the resulting subsolutions offer a powerful tool for the rare-event simulation community, enabling the accurate estimation of probabilities that were previously computationally unreachable.

Summary updated

Abstract

In this paper a duality relation between the Mañé potential and Mather's action functional is derived in the context of convex and state-dependent Hamiltonians. The duality relation is used to obtain min-max representations of viscosity solutions of first order Hamilton-Jacobi equations. These min-max representations naturally suggest class\-es of subsolutions of Hamilton-Jacobi equations that arise in the theory of large deviations. The subsolutions, in turn, are good candidates for designing efficient rare-event simulation algorithms.
BibTeX
@misc{djehiche2014min,
  author = {Boualem Djehiche and Henrik Hult and Pierre Nyquist},
  title = {{Min-max representations of viscosity solutions of Hamilton-Jacobi equations and applications in rare-event simulation}},
  year = {2014},
  eprint = {1406.3605},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1406.3605},
}
Figure