RATES OF CONVERGENCE FOR THE CONTINUUM LIMIT OF NONDOMINATED SORTING

Brendan B Cook, Jeff Calder

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish (US)
Pages (from-to)872-911
Number of pages40
JournalSIAM Journal on Mathematical Analysis
Volume54
Issue number1
DOIs
StatePublished - 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

  • applied probability
  • Hamilton-Jacobi equations
  • nondominated sorting
  • partial differential equations
  • semiconvexity
  • viscosity solutions

Fingerprint

Dive into the research topics of 'RATES OF CONVERGENCE FOR THE CONTINUUM LIMIT OF NONDOMINATED SORTING'. Together they form a unique fingerprint.

Cite this