Pareto front sounds like an interesting way to optimize, but it suffers from the curse of dimensionality just like anything else.
As the number of objectives (dimensions) increases, the number of samples you need to cover the frontier increases exponentially. You will very rarely find solutions that actually dominate other solutions in many practical optimization scenarios. With 2 dimensions you have a 25% chance of domination. With 10 dimensions it's a .098% chance.
The most useful cases I've seen tend to occur where we just optimize for two things at once. The chances of domination are high, it's easy to visualize and very efficient to implement. As we get into higher dimensional spaces, things get weird really fast.
has a truly weird property not covered by the computational complexity discussion on that page. It says there's an algorithm achieving O(n log(n)^(d-3) log log n), which is true and also a lie. The algorithm that achieves that asymptotic form is a galactic algorithm; and not an ordinary one in the sense of "has a large constant multiplicative factor", but one with this property (I've never found any other algorithm which exhibits it):
The runtime is within a bounded constant factor of n^2, for all n up to some critical N whose size is exponential in d (I think it was exactly 2^d or something).
I.e. the runtime has "two shapes": it's purely quadratic up to a galactically-large constant, and thereafter has a transition into to a slower function. The asymptotic version in the textbooks isn't achievable in the real world (for all but very small dimension).
There's an elementary proof using generating functions.
edit to add: If anyone's curious about it, a simplified version of the recurrence relation that's enough to exhibit this behavior (you can instantly see it if you graph this numerically) is
bob1029 · · focus · HN ↗
As the number of objectives (dimensions) increases, the number of samples you need to cover the frontier increases exponentially. You will very rarely find solutions that actually dominate other solutions in many practical optimization scenarios. With 2 dimensions you have a 25% chance of domination. With 10 dimensions it's a .098% chance.
The most useful cases I've seen tend to occur where we just optimize for two things at once. The chances of domination are high, it's easy to visualize and very efficient to implement. As we get into higher dimensional spaces, things get weird really fast.
peri-cl · · focus · HN ↗
The geometric problem of computing a d-dimensional Pareto set of cardinality n
<a href="https://en.wikipedia.org/wiki/Maxima_of_a_point_set" rel="nofollow">https://en.wikipedia.org/wiki/Maxima_of_a_point_set
has a truly weird property not covered by the computational complexity discussion on that page. It says there's an algorithm achieving O(n log(n)^(d-3) log log n), which is true and also a lie. The algorithm that achieves that asymptotic form is a galactic algorithm; and not an ordinary one in the sense of "has a large constant multiplicative factor", but one with this property (I've never found any other algorithm which exhibits it):
The runtime is within a bounded constant factor of n^2, for all n up to some critical N whose size is exponential in d (I think it was exactly 2^d or something).
I.e. the runtime has "two shapes": it's purely quadratic up to a galactically-large constant, and thereafter has a transition into to a slower function. The asymptotic version in the textbooks isn't achievable in the real world (for all but very small dimension).
There's an elementary proof using generating functions.
edit to add: If anyone's curious about it, a simplified version of the recurrence relation that's enough to exhibit this behavior (you can instantly see it if you graph this numerically) is