Hypervolume indicator

The hypervolume indicator is a performance indicator used in multi-objective optimization to measure the quality of a finite approximation of the Pareto front. It measures the Lebesgue measure of the region of objective space that is dominated by an approximation set and bounded by a specified reference point.

In earlier multi-objective optimization literature, the same set-quality quantity was described using terms such as the Lebesgue measure, S-metric, and dominated hypervolume. These terms are now largely historical; the term hypervolume indicator has become the standard terminology in the literature. It is widely used both for comparing Pareto-front approximation sets and as an optimization criterion within multi-objective optimization algorithms.

A distinguishing property of the hypervolume indicator is its strict Pareto compliance, also described as strict monotonicity with respect to set dominance. If one approximation set is strictly better than another according to Pareto dominance, then, under the same suitable reference point, it has a strictly larger hypervolume value.

Definition

Consider a minimization problem with $m$ objective functions, and let

$A=\{\mathbf {a} ^{(1)},\ldots ,\mathbf {a} ^{(n)}\}\subset \mathbb {R} ^{m}$

be a finite approximation set in objective space. Let $\mathbf {r} \in \mathbb {R} ^{m}$ be a reference point that is worse than the objective vectors of interest, so that

$a_{i}\leq r_{i}$

for the relevant points and objectives.

For each $\mathbf {a} \in A$, define the axis-aligned box

$[\mathbf {a} ,\mathbf {r} ]=[a_{1},r_{1}]\times \cdots \times [a_{m},r_{m}].$

The hypervolume indicator of $A$ with respect to $\mathbf {r}$ is

$HV(A;\mathbf {r} )=\lambda _{m}\left(\bigcup _{\mathbf {a} \in A}[\mathbf {a} ,\mathbf {r} ]\right),$

where $\lambda _{m}$ denotes the $m$-dimensional Lebesgue measure.

Thus, in two objective dimensions the hypervolume corresponds to an area, in three dimensions to a volume, and in higher dimensions to the corresponding multidimensional volume.

Only the non-dominated points of an approximation set can contribute to its hypervolume. A point that is dominated by another point in the same set does not enlarge the dominated region.

Properties

Strict Pareto compliance

The hypervolume indicator is strictly Pareto-compliant. In terms of set dominance, if an approximation set $A$ is strictly better than an approximation set $B$, then

$HV(A;\mathbf {r} )>HV(B;\mathbf {r} )$

when both sets are evaluated using the same suitable reference point.

This strict monotonicity with respect to set dominance distinguishes the hypervolume indicator from many other unary quality indicators used in multi-objective optimization.

Convergence and distribution

The hypervolume simultaneously reflects convergence toward the Pareto front and the distribution of points across objective space. Maximizing hypervolume for a fixed number of points therefore defines a set-optimization problem rather than a collection of independent single-point optimization problems.

The value of the indicator depends on the choice of the reference point. The reference point also affects which finite distributions of points maximize hypervolume, particularly near extreme parts of the Pareto front.

Hypervolume-optimal distributions

For a fixed cardinality $\mu$, a hypervolume-optimal $\mu$-distribution is a set of $\mu$ points on a Pareto front that maximizes the hypervolume indicator. Such optimal distributions are not necessarily uniform. Their density depends on the geometry of the Pareto front and on the reference point.

In three objectives, Shang et al. showed that hypervolume-optimal $\mu$-distributions can be non-uniform even for simple line- and plane-based Pareto-front geometries. Depending on the front geometry and reference-point location, hypervolume maximization may give relatively large contributions to boundary or extreme solutions and may place more solutions in regions with strong trade-offs, including knee regions.

Hypervolume contribution

The hypervolume contribution of a point $\mathbf {a} \in A$ is the reduction in hypervolume caused by removing that point from the approximation set:

$\Delta HV(\mathbf {a} ,A)=HV(A;\mathbf {r} )-HV(A\setminus \{\mathbf {a} \};\mathbf {r} ).$

Hypervolume contributions quantify the portion of the hypervolume that is lost when an individual point is removed. Their computation and efficient updating form a distinct family of computational problems associated with the hypervolume indicator.

For low-dimensional problems, dedicated algorithms avoid recomputing the complete hypervolume after removing each point. Emmerich and Fonseca proved that computing all individual hypervolume contributions has tight time complexity $\Theta (n\log n)$ for both two and three objectives. They also presented a dimension-sweep algorithm that computes all contributions in three objectives in $O(n\log n)$ time and $O(n)$ space.

Hypervolume contributions are particularly useful in selection and archiving procedures. For example, in SMS-EMOA the individual with the smallest hypervolume contribution in the worst-ranked non-dominated front is removed during environmental selection.

Computation

Computing the hypervolume amounts to finding the measure of a union of axis-aligned boxes and is related to Klee's measure problem.

For unsorted input, exact hypervolume computation has tight comparison complexity $\Theta (n\log n)$ in both two and three objective dimensions. In two dimensions, sorting the non-dominated points by one objective followed by a linear sweep gives an $O(n\log n)$ algorithm. Beume et al. proved an $\Omega (n\log n)$ lower bound for every fixed dimension greater than one and gave a matching $O(n\log n)$ algorithm for the three-dimensional case.

Fonseca, Paquete and López-Ibáñez incorporated the three-dimensional base case into a recursive dimension-sweep algorithm with worst-case complexity $O(n^{d-2}\log n)$ for $d>2$.

When the number of objectives is part of the input rather than fixed, exact hypervolume computation is #P-hard.

Chan developed an algorithm for Klee's measure problem that gives an $O(n^{d/3}\operatorname {polylog} n)$ running time for the special case of orthants or unit hypercubes in fixed dimension $d$. This special case includes the hypervolume indicator problem.

Exact and approximate algorithms for the hypervolume itself, hypervolume contributions, and related computational problems are surveyed by Guerreiro, Fonseca and Paquete.

Hypervolume subset selection

A related problem is the hypervolume subset selection problem. Given a finite set of candidate points and a desired cardinality $k$, the task is to select the subset of $k$ points with maximum hypervolume. The problem is polynomially solvable in two dimensions, but is NP-hard already in three dimensions.

Bringmann, Cabello and Emmerich also gave an $n^{O({\sqrt {k}})}$ exact algorithm for the three-dimensional case and a polynomial-time approximation scheme for every fixed dimension.

Hypervolume gradient and Hessian

When the objective functions are differentiable, derivatives of the hypervolume indicator can be used to optimize an entire approximation set. Emmerich and Deutz studied the hypervolume indicator gradient field and described how its gradient can be computed from objective values and partial derivatives of the underlying objective functions.

The hypervolume gradient is defined with respect to the coordinates of the points representing the approximation set. Through the chain rule, it can be related to gradients of the objective functions with respect to the decision variables, providing search directions for deterministic set-based optimization.

Second-order information is provided by the hypervolume indicator Hessian. Deutz, Emmerich and Wang derived an analytical expression for the Hessian matrix of the hypervolume indicator for a vectorized fixed-cardinality set and analyzed its computational complexity and sparsity.

The sparsity structure of the Hessian can be exploited in second-order numerical methods and is particularly relevant to Newton-type hypervolume maximization.

Software

Implementations of the hypervolume indicator and related computations are available in optimization software packages. The open-source moocore project provides implementations of multi-objective quality indicators for R and Python, including exact hypervolume computation and hypervolume contributions.

Use in multi-objective optimization

The hypervolume indicator was initially used primarily as a quality measure for comparing approximation sets produced by multi-objective optimization algorithms. It was subsequently also used directly as an objective for optimizing sets of solutions.

Early hypervolume maximization and bounded archiving

Early work on direct hypervolume maximization used terminology that predates the now-standard term hypervolume indicator. Fleischer described a set function mapping a set of Pareto-optimal points to a scalar hypervolume based on the Lebesgue measure and investigated maximization of this quantity for finite multi-objective optimization problems.

Knowles, Corne and Fleischer used the same set-quality measure for maintaining a bounded-size archive of non-dominated solutions. Their bounded archiver locally maximizes the hypervolume represented by the archive when deciding which non-dominated solutions to retain. The use of Lebesgue measure in the title reflects terminology used in early work for the set-quality quantity that is now generally called the hypervolume indicator.

Evolutionary optimization

In evolutionary multi-objective optimization, hypervolume-based algorithms use the hypervolume indicator or individual hypervolume contributions during environmental selection.

An example is SMS-EMOA, which combines non-dominated sorting with selection based on hypervolume contribution. After non-dominated sorting, the point with the smallest hypervolume contribution in the worst-ranked front is removed, so that the selection mechanism aims to retain a population with large hypervolume.

Another example is HypE, a hypervolume-based evolutionary algorithm designed for many-objective optimization. HypE uses Monte Carlo sampling to estimate hypervolume values and contributions, allowing the accuracy of hypervolume-based selection to be traded against computational cost.

Because exact hypervolume computation becomes increasingly expensive with the number of objectives, algorithms for many-objective optimization may instead estimate the hypervolume or hypervolume contributions by sampling.

Set-based numerical optimization

The hypervolume indicator can also be treated directly as a differentiable set-quality objective when the underlying objective functions satisfy appropriate smoothness assumptions. This leads to deterministic numerical methods that simultaneously move a fixed set of decision vectors so as to increase the hypervolume of their approximation set.

The mathematical structure and computation of the hypervolume indicator gradient were studied by Emmerich and Deutz. Gradient-ascent methods subsequently used these derivatives directly for set-based multi-objective optimization.

The Set-Based Hypervolume Newton Method applies Newton-type optimization to a fixed-cardinality set of decision vectors and uses first- and second-order derivatives of the hypervolume indicator to optimize a finite Pareto-front approximation.

The analytical description of the hypervolume Hessian and its sparsity provides additional computational structure for such second-order methods.

The Hypervolume Newton Method was subsequently extended by Wang et al. to constrained multi-objective optimization problems. This extension formulates constrained multi-objective optimization as deterministic numerical optimization of fixed-cardinality approximation sets while incorporating feasibility constraints into the Hypervolume Newton framework.

Bayesian optimization

The hypervolume indicator is also used in Bayesian optimization for expensive multi-objective optimization problems. A prominent acquisition function is the expected hypervolume improvement (EHVI), which evaluates a candidate solution according to the expected increase in hypervolume obtained after evaluating that candidate.

Emmerich, Deutz and Klinkenberg analyzed hypervolume-based expected improvement and derived exact computation methods for EHVI.

A later treatment by Emmerich et al. presented expected hypervolume improvement as a multicriteria generalization of Bayesian global optimization and discussed its properties and computation.

EHVI generalizes the expected-improvement principle of single-objective Bayesian global optimization by defining improvement through the increase in hypervolume relative to the current Pareto-front approximation.

Limitations and considerations

Although the hypervolume indicator is strictly Pareto-compliant, its numerical value and the distribution of hypervolume-optimal approximation sets depend on the chosen reference point, the geometry of the Pareto front, and the scaling of the objective space.

Hypervolume maximization therefore does not in general imply a uniform distribution of solutions along the Pareto front. Depending on the Pareto-front geometry and reference point, hypervolume-optimal distributions may emphasize boundary or extreme solutions and regions with strong trade-offs, including knee regions. These effects are relevant when the hypervolume indicator is used not only for performance assessment but also directly as a selection or set-optimization criterion.

Computational cost is another limitation. For two and three objectives the hypervolume indicator can be computed in optimal $\Theta (n\log n)$ time for unsorted input, but exact hypervolume computation becomes #P-hard when the number of objectives is variable. Exact fixed-cardinality hypervolume subset selection is NP-hard already in three dimensions. Specialized low-dimensional algorithms, contribution-update methods, approximation algorithms and sampling methods are therefore used when the number of objectives or the approximation-set size becomes large.

See also

• Multi-objective optimization
• Pareto efficiency
• Pareto front
• Evolutionary multi-objective optimization
• Bayesian optimization
• Performance indicator
• Lebesgue measure
• Klee's measure problem

External links

• moocore — implementations of multi-objective quality indicators, including the hypervolume indicator and hypervolume contributions