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

Michael T. M. Emmerich

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

Sep 17, 2026cs.LG

Expected Hypervolume Maximization for Multiobjective Optimization under Uncertainties

The problem of multiobjective optimization under uncertainties is often approached by taking the expectation of each objective. In this work, we propose instead to formulate this as a Bayesian decision problem and to rely on the expected value of the hypervolume, which is to be maximized with respect to a finite set of input points. We show that this can be performed using methods based on gradients in a stochastic optimization framework, provided that care is taken with respect to dominated points. Moreover, in the absence of readily available differentiable code, we propose to use Gaussian Processes as differentiable surrogate models, in order to perform the optimization. An additional contribution in this work are some active learning strategies, through acquisition functions which helps construct a surrogate model well-designed for the multiobjective optimization problem at stake. These strategies are compared on simple analytical problems to assess their performances.

Victor Trappler

Multi-Objective Optimization Stochastic Optimization Bayesian

Ask PDF

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

(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

N

objectives, this gives an output-sensitive overhead

O(2^N M)

for an

M

-box decomposition, or

O(M)

for fixed

N

. Using existing box-decomposition approaches, the integral R2 can be computed in

O(n \log n)

for

N=2,3

, in

O(n^2)

for

N=4

, and in

O\left(n^{\lfloor (N-1)/2\rfloor+1}\right)

for

N\geq4

, with

n

denoting the size of the approximation set. On the lower-bound side, exact value computation has an

Ω(n\log n)

lower bound in the algebraic decision-tree model already in two objectives, this bound lifts to every fixed

N\geq2

, and exact computation is

\#P

-hard when

N

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

Integral Bounding Box Computational Cost Multi-Objective Optimization Density Ratio Estimation Volume

Ask PDF

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)

-fraction of the maximum possible R2 gap between a fixed dominated anchor value and the best cardinality-

k

value. We also give a tested greedy implementation that evaluates exact integral R2 values by subdivision, with worst-case running time

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

(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 Maximization Multi-Objective Optimization Np-Hard Integral

Ask PDF