math.OCMay 27, 2026

Preference-Shaped Expected Hypervolume and R2 Improvement: Exact Computation and Monotonicity

Authors: Michael T. M. Emmerich

Organizations: Faculty of Information Technology, University of Jyväskylä, Finland

Abstract

This paper studies preference-shaped expected improvement criteria for Bayesian multiobjective optimization. We consider two indicator families which are often used for similar algorithmic purposes, but which are geometrically different. The hypervolume indicator is based on a dystopian reference point and measures dominated volume in objective space. The R2 indicator is based on a utopian point and evaluates approximation sets through weighted Tchebycheff scalarization envelopes. The purpose of the paper is to make precise which preference transformations preserve exact computation, Pareto compatibility, and monotonicity properties, and which transformations change the underlying geometry. On the hypervolume side, we revisit canonical EHVI through the Deng representation, formulate product-density weighted EHVI in desirability coordinates, discuss cone-based EHVI as ordinary EHVI after a linear cone transformation, and separate these cases from truncated EHVI, where variance monotonicity may fail. On the R2 side, we prove that exact integral R2 improvement is not, in general, an ordinary objective-space weighted hypervolume. The obstruction is lower-dimensional: Lebesgue-density hypervolume cannot see certain boundary contributions that Tchebycheff scalarizations still detect. We then show that exact integral R2 improvement is exactly a scalarization-space volume, namely the measure of the Tchebycheff shadow between the incumbent scalarization envelope and the reference envelope. This representation yields finite-sum ER2I algorithms for discrete R2, quadrature methods for exact integral R2, and an achievement-space Gaussian surrogate formulation in which ER2I is an integral of scalar Gaussian expected improvements.

Explore similar work

CardsList
Jun 29, 2026cs.CG

Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition

The continuous integral R2 indicator is a Pareto-compliant refinement of the classical finite-weight-vector R2 indicator, used in performance assessment, bounded archiving for a-posteriori multi-objective optimization, and skyline selection in databases. This work introduces a bidirectional perspective mapping between continuous integral R2 computation and integration over unions of anchored axis-aligned boxes. After translating the ideal point of a minimization problem to the origin, approximation points become strictly positive loss vectors, and the subgraph of the lower weighted Tchebycheff envelope over the weight simplex maps to the complement of an anchored-box union in reciprocal objective space. The Jacobian gives an absolute R2 formula as a weighted complement volume with density (x1+⋯+xN)−(N+1)(x_1+\cdots+x_N)^{-(N+1)}, while differences of R2 values become finite weighted hypervolume differences. Hence, hypervolume algorithms that emit box decompositions can be reused by replacing ordinary box volumes with closed-form weighted box integrals. For NN objectives, this gives an output-sensitive overhead O(2NM)O(2^N M) for an MM-box decomposition, or O(M)O(M) for fixed NN. Using existing box-decomposition approaches, the integral R2 can be computed in O(nlog⁡n)O(n \log n) for N=2,3N=2,3, in O(n2)O(n^2) for N=4N=4, and in O(n⌊(N−1)/2⌋+1)O\left(n^{\lfloor (N-1)/2\rfloor+1}\right) for N≥4N\geq4, with nn denoting the size of the approximation set. On the lower-bound side, exact value computation has an Ω(nlog⁡n)Ω(n\log n) lower bound in the algebraic decision-tree model already in two objectives, this bound lifts to every fixed N≥2N\geq2, and exact computation is #P\#P-hard when NN is part of the input. Together, the proposed perspective mapping provides a powerful tool for transferring algorithmic and structural results between anchored-box union and hypervolume theory and integral R2 computation.
Michael T. M. Emmerich
Numerical DispersionMulti-Objective OptimizationBounding BoxComputational CostVolumePerspective
AskPDF
Jun 25, 2026math.OC

Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation

Selecting a fixed number of representative points from a finite Pareto-front approximation is a fundamental post-processing task in multiobjective optimization. This paper studies this problem for the integral R2 indicator in three objectives, where the indicator is defined as the integral of the lower envelope of weighted Tchebycheff scalarizations over the two-dimensional weight simplex. We provide two complementary algorithmic results. On the positive side, we show that the integral R2 improvement with respect to any fixed baseline is a monotone submodular set function. For the usual ideal-point based R2 indicator, with the ideal point fixed, this yields a direct gap-reduction guarantee: greedy selection closes at least a (1−1/e)(1-1/e)-fraction of the maximum possible R2 gap between a fixed dominated anchor value and the best cardinality-kk value. We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision, with worst-case running time O(n6)O(n^6). On the negative side, we prove that exact fixed-cardinality subset selection is NP-hard already in three objectives. The hardness proof uses a perspective transformation that maps Tchebycheff-shadow improvements to a weighted anchored-box union problem with density (x1+x2+x3)−4(x_1+x_2+x_3)^{-4}, and then adapts the three-dimensional anchored-box construction of Bringmann, Cabello, and Emmerich. Together, these results separate the tractable two-objective case from the three-objective case while identifying a principled approximation route based on submodular optimization.
Michael T. M. Emmerich
Submodular MaximizationMulti-Objective OptimizationNumerical Dispersion
AskPDF
Jun 15, 2026cs.NE

Effects of Objective Normalization on Regions of Interest in Preference-Based Evolutionary Multi-Objective Optimization

Preference-based evolutionary multi-objective optimization (PBEMO) aims to approximate a region of interest (ROI) defined by the preference information from a decision maker (DM). Although objective functions in real-world applications typically have different scales, the issue of how to define the ROI in such problems has been overlooked in the literature. In fact, it has not been standardized in the EMO community whether the ROI should be defined in the unnormalized objective space or in the normalized objective space. In this context, this paper investigates the effects of objective normalization on ROIs. First, this paper shows that two ROIs defined in the unnormalized and normalized objective spaces can differ significantly for problems with differently scaled objectives. Then, we demonstrate that ROIs defined in the normalized objective space are highly difficult to approximate even on problems with equally scaled objectives because of poor approximations of the ideal and nadir points. In contrast, we show that ROIs defined in the unnormalized objective space are much easier to approximate than those defined in the normalized objective space.
Ryuichi Mogami, Ryoji Tanabe
Multi-Objective Evolutionary AlgorithmObjective FunctionsNormalizationSemantic RegionEffect
AskPDF