A perspective map converts continuous integral R2 into weighted anchored-box integrals, yielding O(n log n) exact algorithms for 2–3 objectives, higher-D polynomial bounds, and #P-hardness when dimension is variable.
Preference-Shaped Expected Hypervolume and R2 Improvement: Exact Computation and Monotonicity
3 Pith papers cite this work. Polarity classification is still indexing.
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.
years
2026 3representative citing papers
Proves NP-hardness of exact 3-objective integral R2 subset selection and shows the improvement function is monotone submodular for greedy approximation.
Exact O(kn) algorithm for fixed-cardinality subset selection under the continuous integral bi-objective R2 indicator via adjacent-neighbor decomposition and Monge matrix search.
citing papers explorer
-
Computing the Integral R2 Indicator by Perspective Mapping and Box Decomposition
A perspective map converts continuous integral R2 into weighted anchored-box integrals, yielding O(n log n) exact algorithms for 2–3 objectives, higher-D polynomial bounds, and #P-hardness when dimension is variable.
-
Three-Objective Integral R2 Subset Selection: NP-Hardness and Submodular Approximation
Proves NP-hardness of exact 3-objective integral R2 subset selection and shows the improvement function is monotone submodular for greedy approximation.
-
Exact and Fast Subset Selection Algorithms for the Bi-objective Integral R2 Indicator
Exact O(kn) algorithm for fixed-cardinality subset selection under the continuous integral bi-objective R2 indicator via adjacent-neighbor decomposition and Monge matrix search.