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

DOI10.1016/J.NA.2016.03.023zbMATH Open1347.35080arXiv1508.01565OpenAlexW2963828685MaRDI QIDQ299237FDOQ299237

Jeff Calder

Publication date: 22 June 2016

Published in: Nonlinear Analysis. Theory, Methods \& Applications. Series A: Theory and Methods (Search for Journal in Brave)

Abstract: Nondominated sorting is a combinatorial algorithm that sorts points in Euclidean space into layers according to a partial order. It was recently shown that nondominated sorting of random points has a Hamilton-Jacobi equation continuum limit. The original proof relies on a continuum variational problem. In this paper, we give a new proof using a direct verification argument that completely avoids the variational interpretation. We believe this proof is new in the homogenization literature, and may be generalized to apply to other stochastic homogenization problems for which there is no obvious underlying variational principle.

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

Recommendations

• Rates of convergence for the continuum limit of nondominated sorting
• A Hamilton-Jacobi equation for the continuum limit of nondominated sorting
• Numerical schemes and rates of convergence for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• A PDE-based approach to nondominated sorting
• Anomaly Detection and Classification for Streaming Data using PDEs

zbMATH Keywords

stochastic homogenizationlongest chain problemnondominated sorting

Mathematics Subject Classification ID

Strong limit theorems (60F15) Combinatorial probability (60C05) Homogenization in context of PDEs; PDEs in media with periodic structure (35B27) Viscosity solutions to PDEs (35D40) Hamilton-Jacobi equations (35F21)

Cites Work

• Evolutionary Multi-Criterion Optimization
• Multivariate analysis by data depth: Descriptive statistics, graphics and inference. (With discussions and rejoinder)
• Optimal approximations by piecewise smooth functions and associated variational problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Homogenization of “Viscous” Hamilton–Jacobi Equations in Stationary Ergodic Media
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
• Continuum limit for some growth models.
• Multi-objective optimization using evolutionary algorithms
• Title not available (Why is that?)
• Stochastic homogenization of Hamilton-Jacobi and degenerate Bellman equations in unbounded environments
• Concentration of measure and isoperimetric inequalities in product spaces
• Active contours without edges
• Stochastic homogenization of Hamilton-Jacobi equations in stationary ergodic spatio-temporal media
• Correctors for the homogenization of Hamilton-Jacobi equations in the stationary ergodic setting
• Stochastic Homogenization of Level-Set Convex Hamilton–Jacobi Equations
• Title not available (Why is that?)
• A variational problem for random Young tableaux
• Title not available (Why is that?)
• Subadditive ergodic theory
• On the length of the longest monotone subsequence in a random permutation
• The height of a random partial order: Concentration of measure
• Numerical schemes and rates of convergence for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• Continuum limit for some growth models. II.
• Limiting curves for i.i.d. records
• Directed last passage percolation with discontinuous weights
• Gene discovery using Pareto depth sampling distributions
• A PDE-based Approach to Nondominated Sorting
• An Efficient Method for Multiobjective Optimal Control and Optimal Control Subject to Integral Constraints
• Stochastic homogenization of Hamilton-Jacobi-Bellman equations
• The Longest Chain Among Random Points in Euclidean Space
• Pareto-Depth for Multiple-Query Image Retrieval
• Title not available (Why is that?)
• Title not available (Why is that?)
• A growth model in multiple dimensions and the height of a random partial order
• Homogenization of Hamilton‐Jacobi‐Bellman equations with respect to time‐space shifts in a stationary ergodic medium
• A Hamilton--Jacobi Equation for the Continuum Limit of Nondominated Sorting
• Transfer of a passive additive in a turbulent boundary layer at very large Reynolds numbers
• Stochastic homogenization of Hamilon-Jacobi and ``viscous-Hamilton-Jacobi equations with convex nonlinearities -- revisited

Cited In (3)

• Hamilton-Jacobi scaling limits of Pareto peeling in 2D
• Rates of Convergence for the Continuum Limit of Nondominated Sorting
• Anomaly Detection and Classification for Streaming Data using PDEs

Uses Software

• MOCK

This page was built for publication: A direct verification argument for the Hamilton-Jacobi equation continuum limit of nondominated sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299237)