Efficient Computation of Expected Hypervolume Improvement Using Box Decomposition Algorithms

1 Introduction

• EHVI is widely used in MOBGO and leads to strong convergence to and coverage of the true Pareto front, but its repeated computation can be time-consuming.The optimizer computes the criterion many times while searching for a promising solution in each iteration.Source: §1 · p. 2
• Prior exact EHVI methods reduced complexity to O(n^2) in 2-D and O(n^3) in 3-D, while later methods reached Θ(n log n) in the bi-objective and 3-D cases.The 3-D result is attributed to Yang et al.; the bi-objective result is attributed to Emmerich et al..Source: §1 · pp. 2–3
• Monte Carlo integration was the first suggested EHVI calculation method, but its accuracy depends strongly on the number of iterations.The method was proposed by Emmerich.Source: §1 · p. 2
• A generalization of the slice-based Θ(n log n) methods beyond three objectives and empirical benchmarking of MOBGO algorithms were identified as missing.The 3-D slice-based algorithm is KMAC2.Source: §1 · p. 3
• The paper extends state-of-the-art EHVI calculation methods to higher dimensions and evaluates MOBGO algorithms on benchmarks in 6- and 18-dimensional search spaces.The introduction identifies these contributions and describes experiments on 10 scientific benchmarks.Source: §1 · p. 3

2.1 Notations

• A multi-objective optimization problem involves multiple objective functions; the notation distinguishes objective count d, search-space dimension m, objective functions, and integration slices.The section also lists notation for Kriging models, datasets, and related quantities.Source: §2 · p. 3, §2.1 · p. 4

2.2 Kriging

• Kriging is a Gaussian-process regression method fitted to evaluated points; its mean models global behavior, while its Gaussian-process component captures local variation and provides prediction uncertainty.The section describes a distance-decreasing correlation function and optimizes its parameters.Source: §2.2 · p. 4

2.3 Structure of MOBGO

• MOBGO initializes evaluated solutions and a non-dominated set, then repeatedly trains surrogate models, optimizes an infill criterion, evaluates the selected point, and updates the set until termination.The returned output is the Pareto-front approximation set.Source: §2.3 · pp. 5–6
• MOBGO assumes mutually independent objective functions, models each with a Kriging surrogate, and uses an optimizer to select a promising point from an infill criterion score.The selected point is evaluated using the true objectives, after which the dataset and Pareto-front approximation are updated.Source: §2.3 · pp. 5–6

Dominance and non-dominance

• Pareto dominance orders potential solutions by objective values, while non-dominance identifies points not dominated by another point in the set.The paper considers maximization and defines dominance through coordinate-wise comparison, with strict improvement in at least one coordinate.Source: §3 · pp. 6–7

Dominated and non-dominated spaces

• The dominated space contains points dominated by at least one member of P; the non-dominated space is bounded by a reference point and excludes points dominated by P.The paper notes that these spaces can also be defined for infinite sets.Source: §3 · p. 7

Hypervolume measures

• The Hypervolume Indicator measures the dominated subspace bounded by a reference point, which users provide and choose below the approximation set when seeking extreme points.The paper states that maximizing hypervolume leads to a high-quality and diverse Pareto-front approximation.Source: §3 · p. 7
• Hypervolume Improvement is illustrated as the area added in 2-D and the joint volume added in 3-D when a new objective vector is considered relative to P.The 2-D and 3-D examples are shown in Figure 1.Source: §3 · pp. 7–8, Figure 1 · p. 8

Improvement criteria

• Probability of Improvement uses a multivariate predictive distribution and counts outcomes in the non-dominated space; it is reference-free because its reference point is set to negative infinity.The paper describes PoI as an important MOBGO criterion.Source: §3 · pp. 8–9
• Expected Hypervolume Improvement is defined from the predictive distribution and Pareto-front approximation, and its 2-D illustration shows a sampled improvement region against the dominated subspace.Figure 2 depicts the bivariate Gaussian density and distinguishes the dominated subspace from the sampled improvement area.Source: §3 · p. 9, Figure 2 · p. 9

• The section presents an efficient non-dominated-space partitioning method and explains how the partition supports calculation of EHVI and PoI.Source: §4 · p. 10

4.1 Partitioning a non-dominated space

• Partitioning efficiency depends on the non-dominated search algorithm and slice count; the method minimizes slices and sums each slice's criterion contribution.Source: §4.1 · p. 10

4.1.1 The 2-D case

• In 2-D, lines parallel to the y2-axis divide the non-dominated region into n+1 disjoint slices, each described by lower and upper bounds.The method builds on the previously published 2-D approach.Source: §4.1.1 · pp. 10–11

4.1.2 The 3-D case

• In 3-D, an AVL-tree sweep processes points in descending y3 order, finding and removing points dominated in the y1y2-plane to create integration slices.The slice count is 2n+1 in general position and no more than 2n+1 otherwise.Source: §4.1.2 · pp. 11–12

4.1.3 Higher dimensional cases

• For d ≥ 4, the method converts non-dominated-space partitioning into dominated-space partitioning using an intermediate Pareto-front approximation, then obtains hyperbox bounds.It combines DKLV17 for local lower bounds with LKF17 for dominated-space partitioning and boundary information.Source: §4.1.3 · pp. 13–14

4.2.1 2-D EHVI calculation

• In 2-D, exact EHVI takes O(n log n), or Θ(n) when the Pareto set P is already sorted.The calculation evaluates the slice terms n + 1 times, with O(1) computation per evaluation.Source: §4.2.1 · p. 18

4.2.2 3-D EHVI calculation

• In 3-D, maintaining non-dominated projections in an AVL tree yields total EHVI computation of O(n log n).Neighbor identification takes O(log n), while each slice’s EHVI calculation takes O(1).Source: §4.2.2 · p. 19

4.2.3 Higher dimensional EHVI

• For higher dimensions, the method divides each of the first d−1 coordinate intervals into two parts, producing 2^(d−1) terms per hyperbox.The final coordinate uses one expression; the total EHVI sums the contributions of all partitioned non-dominated hyperboxes.Source: §4.2.3 · pp. 19, 23
• For fixed dimension d ≥ 4, the algorithm has complexity Θ(n^⌊d/2⌋), with an additional exponential factor in d that limits usefulness to moderate dimensions.Each hyperbox requires O(2^(d−1)) computation steps.Source: §4.2.3 · p. 23

4.3 Probability of Improvement (PoI)

• PoI can be calculated using the paper’s integration-slice partitioning method.The reference point r = {−∞}^d is used to obtain boundary information, not as part of the indicator itself.Source: §4.3 · pp. 23–24
• The number of slices is N2 = n + 1 in 2-D and N3 = 2n + 1 in 3-D.Source: §4.3 · p. 24
• Because PoI is reference-free, r = {−∞}^d is used only to obtain the correct boundary information.Source: §4.3 · p. 24

5.1 Speed Comparison

• The speed experiment compared CDD13 and KMAC on randomly generated Pareto-front sets based on CONVEXSPHERICAL and CONCAVESPHERICAL functions.For KMAC, the comparison included its 2-D and 3-D algorithms and the higher-dimensional extension for d ≥ 4.Source: §5.1 · p. 24
• KMAC was much faster than CDD13, especially as Pareto-front size increased; in 5-D, CDD13 could not finish within 30 minutes when |P| exceeded 30.Figure 7 compares speed using concave (above) and convex (below) random Pareto-front sets.Source: §5.1 · p. 24, Figure 7 · p. 25

5.2 Benchmark Performance

• The benchmark comparison covered five algorithms on ten problems with m = 6 or 18, using 300 function evaluations for MOBGO-based methods and ten repetitions.The five methods were EHVI-MOBGO, PoI-MOBGO, NSGA-II, NSGA-III, and SMS-EMOA.Source: §5.2 · p. 24
• At 300 evaluations, EHVI-MOBGO or PoI-MOBGO yielded the best Hypervolume result on each of ten benchmarks in 6- and 18-dimensional search spaces.Final Pareto fronts were evaluated using the Hypervolume indicator.Source: §5.2 · p. 24, Table 4 · p. 26
• On DTLZ7 and MaF13, EHVI-MOBGO still outperformed EMOAs in both search spaces even when their evaluation budget rose to 2000.EHVI-MOBGO outperformed PoI-MOBGO in most cases, while PoI-MOBGO was better on two problems at m = 6 and three at m = 18.Source: §5.2 · pp. 25–26

6 Conclusions and Outlook

• For random non-dominated sets with n ≤ 1000, the new algorithm was many orders of magnitude faster and generalized exact EHVI calculation to d ≥ 4.It uses fast box decomposition to partition the non-dominated space into Θ(n⌊d/2⌋) hyperboxes and scales linearly with the number of hyperboxes, avoiding full grids of Θ(n^d) boxes.Source: §6 · p. 27
• With budgets up to 300 evaluations, MOBGO-based methods achieved higher HV values than EMOAs across ten test problems in both 6- and 18-dimensional spaces.EHVI-MOBGO was better than PoI-MOBGO in most cases, but PoI-MOBGO was better on up to three problems in each space.Source: §6 · p. 27
• PoI can indicate improvement throughout the non-dominated space, whereas EHVI indicates improvement only within the region bounded by a reference point.A large or dynamic reference point is suggested as a possible remedy, but an excessively large point can make EHVI values similar or identical because of insufficient numerical stability.Source: §6 · p. 27
• Reference-free EHVI computation remains a future research direction, and fast EHVI calculation for larger objective counts remains an open question.The worst-case complexity is conjectured to grow superpolynomially with the number of objectives.Source: §6 · p. 27