### Approximation quality of the hypervolume indicator

Abstract

In order to allow a comparison of (otherwise incomparable) sets, many evolutionary
multi-objective optimizers use indicator functions to guide the search and to evaluate
the performance of search algorithms. The most widely used indicator is the hypervolume
indicator. It measures the volume of the dominated portion of the objective space bounded
from below by a reference point.
Though the hypervolume indicator is very popular, it has not been shown that maximizing
the hypervolume indicator of sets of bounded size is indeed equivalent to the overall objective
of finding a good approximation of the Pareto front. To address this question, we compare the
optimal approximation ratio with the approximation ratio achieved by two-dimensional sets maximizing
the hypervolume indicator. We bound the optimal multiplicative approximation ratio of n points by
1 + Theta(1/n) for arbitrary Pareto fronts. Furthermore, we prove that the same asymptotic approximation
ratio is achieved by sets of n points that maximize the hypervolume indicator. However, there is a
provable gap between the two approximation ratios which is even exponential in the ratio between the
largest and the smallest value of the front.
We also examine the additive approximation ratio of the hypervolume indicator in two dimensions and
prove that it achieves the optimal additive approximation ratio apart from a small ratio <= n/(n - 2),
where n is the size of the population. Hence the hypervolume indicator can be used to achieve a good
additive but not a good multiplicative approximation of a Pareto front. This motivates the introduction
of a "logarithmic hypervolume indicator" which provably achieves a good multiplicative approximation ratio.