3 ms·
For low dimensions, it might be useful to look at the convex properties of the Pareto front. If a point P is on Pareto front, it is not in the interior of the c
by cochleari_major 6y ago
For low dimensions, it might be useful to look at the convex properties of the Pareto front. If a point P is on Pareto front, it is not in the interior of the convex hull of undominated points. In two dimensions, one can compute the convex hull of N points in O(N log N) time. This typically allows for faster Pareto front computation, but not in the worst case.
- Jargerhaben 6y ago> If a point P is on Pareto front, it is not in the interior of the convex hull of undominated points. Can you elaborate on what you mean by this? Is this under the assumption of a convex Pareto front? I may be misunderstanding.
- hansvm 6y agoI bet they're referring to the objective space, not the input space. It's easy to come up with pathological examples where that strategy doesn't help. E.g., if your objectives lie in the boundary of the unit square then the Pareto Front will have at most two points in it (near a corner -- which corner depends on whether you're looking at maxima or minima in each coordinate), but the entire set will be in the convex hull. For a uniform sample it's more beneficial. Most points aren't in the hull (as the cardinality increases the hull density drops to 0), and in 2D the Pareto Front will be around 25% of the hull. I'm not sure you can compute the hull any more quickly than this library in the first place, at least asymptotically, but there already exist some highly optimized solvers, so that might tip the scales a bit.
- contravariant 6y agoYeah I'm not sure this works. As far as I can tell the Pareto front doesn't have to be convex and can therefore contain points that are in the interior of the convex hull. Of course if you accept convex combinations of options then the pareto front is part of the convex hull.