A Hamilton-Jacobi equation for the continuum limit of nondominated sorting

DOI10.1137/13092842XzbMATH Open1288.35190arXiv1302.5828MaRDI QIDQ5415071FDOQ5415071

Authors: Jeff Calder, Selim Esedoḡlu, Alfred O. III Hero 

Publication date: 9 May 2014

Published in: SIAM Journal on Mathematical Analysis (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1302.5828

Recommendations

• Rates of convergence for the continuum limit of nondominated sorting
• A PDE-based approach to nondominated sorting
• Numerical schemes and rates of convergence for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• A direct verification argument for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• Anomaly Detection and Classification for Streaming Data using PDEs

zbMATH Keywords

optimal controlPareto-optimalitynondominated sortinglongest chain in Euclidean space

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial probability (60C05) Combinatorics of partially ordered sets (06A07) Viscosity solutions to PDEs (35D40) Hamilton-Jacobi equations (35F21) PDEs in connection with control and optimization (35Q93)

Cited In (16)

• Rates of convergence for the continuum limit of nondominated sorting
• Hamilton-Jacobi scaling limits of Pareto peeling in 2D
• Analysis of \(p\)-Laplacian regularization in semisupervised learning
• A direct verification argument for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• Boundary estimation from point clouds: algorithms, guarantees and applications
• Eikonal depth: an optimal control approach to statistical depths
• Tukey depths and Hamilton-Jacobi differential equations
• Analysis and algorithms for \(\ell_p\)-based semi-supervised learning on graphs
• On a toy network of neurons interacting through their dendrites
• Numerical schemes and rates of convergence for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• A PDE-based approach to nondominated sorting
• Monotone discretizations of levelset convex geometric PDEs
• Directed last passage percolation with discontinuous weights
• Anomaly Detection and Classification for Streaming Data using PDEs
• A PDE-based method for shape registration
• A continuum limit for the PageRank algorithm

This page was built for publication: A Hamilton-Jacobi equation for the continuum limit of nondominated sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415071)