skip to main content


Title: High-order Filtered Schemes for the Hamilton-Jacobi Continuum Limit of Nondominated Sorting
We investigate high-order finite difference schemes for the Hamilton-Jacobi equation continuum limit of nondominated sorting. Nondominated sorting is an algorithm for sorting points in Euclidean space into layers by repeatedly removing minimal elements. It is widely used in multi-objective optimization, which finds applications in many scientific and engineering contexts, including machine learning. In this paper, we show how to construct filtered schemes, which combine high order possibly unstable schemes with first order monotone schemes in a way that guarantees stability and convergence while enjoying the additional accuracy of the higher order scheme in regions where the solution is smooth. We prove that our filtered schemes are stable and converge to the viscosity solution of the Hamilton-Jacobi equation, and we provide numerical simulations to investigate the rate of convergence of the new schemes.  more » « less
Award ID(s):
1713691
NSF-PAR ID:
10059997
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Journal of Mathematics Research
Volume:
10
Issue:
1
ISSN:
1916-9795
Page Range / eLocation ID:
90
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    For hyperbolic systems of conservation laws, uniqueness of solutions is still largely open. We aim to expand the theory of uniqueness for systems of conservation laws. One difficulty is that many systems have only one entropy. This contrasts with scalar conservation laws, where many entropies exist. It took until 1994 to show that one entropy is enough to ensure uniqueness of solutions for the scalar conservation laws (see [E. Yu. Panov, Uniqueness of the solution of the Cauchy problem for a first order quasilinear equation with one admissible strictly convex entropy, Mat. Z. 55(5) (1994) 116–129 (in Russian), Math. Notes 55(5) (1994) 517–525]. This single entropy result was proven again by De Lellis, Otto and Westdickenberg about 10 years later [Minimal entropy conditions for Burgers equation, Quart. Appl. Math. 62(4) (2004) 687–700]. These two proofs both rely on the special connection between Hamilton–Jacobi equations and scalar conservation laws in one space dimension. However, this special connection does not extend to systems. In this paper, we prove the single entropy result for scalar conservation laws without using Hamilton–Jacobi. Our proof lays out new techniques that are promising for showing uniqueness of solutions in the systems case. 
    more » « less
  2. We propose a new iterative scheme to compute the numerical solution to an over-determined boundary value problem for a general quasilinear elliptic PDE. The main idea is to repeatedly solve its linearization by using the quasi-reversibility method with a suitable Carleman weight function. The presence of the Carleman weight function allows us to employ a Carleman estimate to prove the convergence of the sequence generated by the iterative scheme above to the desired solution. The convergence of the iteration is fast at an exponential rate without the need of an initial good guess. We apply this method to compute solutions to some general quasilinear elliptic equations and a large class of first-order Hamilton-Jacobi equations. Numerical results are presented. 
    more » « less
  3. null (Ed.)
    We study the effect of small random advection in two models in turbulent combustion. Assuming that the velocity field decorrelates sufficiently fast, we (i) identify the order of the fluctuations of the front with respect to the size of the advection; and (ii) characterize them by the solution of a Hamilton–Jacobi equation forced by white noise. In the simplest case, the result yields, for both models, a front with Brownian fluctuations of the same scale as the size of the advection. That the fluctuations are the same for both models is somewhat surprising, in view of known differences between the two models. 
    more » « less
  4. Mean field games (MFG) and mean field control (MFC) are critical classes of multiagent models for the efficient analysis of massive populations of interacting agents. Their areas of application span topics in economics, finance, game theory, industrial engineering, crowd motion, and more. In this paper, we provide a flexible machine learning framework for the numerical solution of potential MFG and MFC models. State-of-the-art numerical methods for solving such problems utilize spatial discretization that leads to a curse of dimensionality. We approximately solve high-dimensional problems by combining Lagrangian and Eulerian viewpoints and leveraging recent advances from machine learning. More precisely, we work with a Lagrangian formulation of the problem and enforce the underlying Hamilton–Jacobi–Bellman (HJB) equation that is derived from the Eulerian formulation. Finally, a tailored neural network parameterization of the MFG/MFC solution helps us avoid any spatial discretization. Our numerical results include the approximate solution of 100-dimensional instances of optimal transport and crowd motion problems on a standard work station and a validation using a Eulerian solver in two dimensions. These results open the door to much-anticipated applications of MFG and MFC models that are beyond reach with existing numerical methods.

     
    more » « less
  5. We study a toy model of linear-quadratic mean field game with delay. We “lift" the delayed dynamic into an infinite dimensional space, and recast the mean field game system which is made of a forward Kolmogorov equation and a backward Hamilton-Jacobi-Bellman equation. We identify the corresponding master equation. A solution to this master equation is computed, and we show that it provides an approximation to a Nash equilibrium of the finite player game. 
    more » « less