How to efficiently compute the pareto front in a >2 dimensional multi-objective case?

Question

I'm currently working on an optimization problem with 4 different objective functions and need an algorithm to compute the pareto frontier from several "solutions" to that problem.

I already found algorithms that compute the pareto frontier for 2 objective functions (like cost & value) very efficiently but are (i.m.o.) not that easy to generalize to work with n objectives.

So what i basically want is an algorithm, that takes a set of 4-dimensional vectors and sorts out all the ones, that are dominated.

Of course it can be done with brute-force by checking any vector against every other one, but that would have exponential complexity and wouldn't be applicable with realistic problems since it would take forever to terminate.

I think, that there has to be an algorithm which works in (at least) O(n^m), with m = number of objective functions.

I really appreciate any suggestions/ideas.

Answer 1

Check out Kung's algorithm. Given $n$ vectors in $\mathbb{R}^d$, it computes the non-dominated front for $d=2,3$ in $O(n \log n)$ time and for $d > 3$ in $O\left ( n (\log n)^{d-2}\right)$. I believe it has been implemented in the paretoset function on FEX.

Answer 2

If your data tends to have a relatively low number of nondominated points, then a simple $O(n^2)$ Bubblesort-like algorithm will typically perform quite well. First, sort your data on the linear weighted sum of your objectives, so the top point on your list is guaranteed to be nondominated. This point will also probably be the most dominant, in that it dominates the most number of other points. Use this to sweep through the remaining data, removing dominated points. At this point you will have a decimated data set, and can continue with the next point and so on.

The Kung algorithm does well when a higher percentage of the points are nondominated. Better asymptotic complexity, but a higher base cost.