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

DOI10.1137/13092842XMaRDI QIDQ5415071zbMATH OpenFDO

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)

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

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)

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.

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

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
• Analysis and algorithms for \(\ell_p\)-based semi-supervised learning on graphs
• Eikonal depth: an optimal control approach to statistical depths
• On a toy network of neurons interacting through their dendrites
• Tukey depths and Hamilton-Jacobi differential equations
• 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)