A Hamilton-Jacobi equation for the continuum limit of non-dominated\n sorting

2013/02/23 by Jeff Calder, Calder, Jeff, Selim Esedoḡlu +3
Mathematics · Computer Science · #Stochastic processes and statistical mechanics #Random Matrices and Applications #Bayesian Methods and Mixture Models

paper · pdf · doi:10.48550/arxiv.1302.5828

Abstract

We show that non-dominated sorting of a sequence of i.i.d. random variables\nin Euclidean space has a continuum limit that corresponds to solving a\nHamilton-Jacobi equation involving the probability density function of the\nrandom variables. Non-dominated sorting is a fundamental problem in\nmulti-objective optimization, and is equivalent to finding the canonical\nantichain partition and to problems involving the longest chain among Euclidean\npoints. As an application of this result, we show that non-dominated sorting is\nasymptotically stable under random perturbations in the data. We give a\nnumerical scheme for computing the viscosity solution of this Hamilton-Jacobi\nequation and present some numerical simulations for various density functions.\n

Citations

• Optimal approximations by piecewise smooth functions and associated variational problems

Related

• Numerical schemes and rates of convergence for the Hamilton-Jacobi\n equation continuum limit of nondominated sorting
• A direct verification argument for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• A PDE-based approach to non-dominated sorting
• High-order filtered schemes for the Hamilton-Jacobi continuum limit of\n nondominated sorting
• Hamilton-Jacobi scaling limits of Pareto peeling in 2D