A PDE-Based Approach to Non-Dominated Sorting

Non-dominated sorting is a fundamental problem in multi- objective optimization. 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 partial differential equation (specifically, a Hamilton-Jacobi equation) involving the probability density function of the random variables. We give an efficient numerical scheme for computing the viscosity solution of this Hamilton-Jacobi equation, and show how it can be used to design a fast algorithm for approximate non-dominated sorting. We demonstrate the advantages of this approach on a large scale real data application of anomaly detection in pedestrian trajectories captured from an overhead camera. Joint work with Jeff Calder and Alfred Hero (Ph.D. thesis work of Jeff Calder).