Abstract
Nondominated sorting is a discrete process that sorts points in Euclidean space according to the coordinatewise partial order and is used to rank feasible solutions to multiobjective optimization problems. It was previously shown that nondominated sorting of random points has a Hamilton-Jacobi equation continuum limit. We prove quantitative error estimates for the convergence of nondominated sorting to its continuum limit Hamilton-Jacobi equation. Our proof uses the maximum principle and viscosity solution machinery, along with new semiconvexity estimates for domains with corner singularities.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 872-911 |
| Number of pages | 40 |
| Journal | SIAM Journal on Mathematical Analysis |
| Volume | 54 |
| Issue number | 1 |
| DOIs | |
| State | Published - 2022 |
Bibliographical note
Funding Information:\ast Received by the editors August 11, 2020; accepted for publication (in revised form) September 7, 2021; published electronically February 7, 2022. https://doi.org/10.1137/20M1344901 Funding: The work of the authors was supported by National Science Foundation grant DMS-1713691 and a University of Minnesota Grant in Aid award. \dagger Mathematics, University of Minnesota, Minneapolis, MN 55455 USA (cookx932@umn.edu, jcalder@umn.edu).
Publisher Copyright:
© 2022 Society for Industrial and Applied Mathematics.
Keywords
- Hamilton-Jacobi equations
- applied probability
- nondominated sorting
- partial differential equations
- semiconvexity
- viscosity solutions