A HAMILTON-JACOBI EQUATION FOR THE CONTINUUM LIMIT OF NONDOMINATED SORTING

作者：Calder Jeff^*; Esedoglu Selim; Hero Alfred O

来源：SIAM Journal on Mathematical Analysis, 2014, 46(1): 603-638.

DOI：10.1137/13092842X

• Hamilton-Jacobi equations
• viscosity solutions
• optimal control
• longest chain in Euclidean space
• nondominated sorting
• Pareto-optimality

We show that nondominated sorting of a sequence X-1, ... , X-n of independent and identically distributed random variables in R-d has a continuum limit that corresponds to solving a Hamilton-Jacobi equation involving the probability density function f of X-i. Nondominated sorting is a fundamental problem in multiobjective 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 nondominated sorting is asymptotically stable under bounded random perturbations in X-1, ... , X-n. We give a numerical scheme for computing the viscosity solution of this Hamilton-Jacobi equation and present some numerical simulations for various density functions.

• 出版日期2014