Repository: secondmind-labs/trieste

Issue:
Pareto set: hypervolume
As a user, I want functionality available to calculate the hypervolume of a Pareto front given the cell bounds, so that I can easily find the hypervolume when defining multi-objective acquisition functionality

Discussion:

Patch:
diff --git a/trieste/utils/pareto.py b/trieste/utils/pareto.py
index 42493d76..85cfc628 100644
--- a/trieste/utils/pareto.py
+++ b/trieste/utils/pareto.py
@@ -105,3 +105,46 @@ class Pareto:
         upper = tf.concat([range_ + 1, pf_ext_idx[::-1, 1:][: pf_ext_idx[-1, 0]]], axis=-1)
 
         return BoundedVolumes(lower, upper)
+
+    def hypervolume_indicator(self, reference: TensorType) -> TensorType:
+        """
+        Calculate the hypervolume indicator
+        The hypervolume indicator is the volume of the dominated region.
+
+        :param reference: a reference point to use, with shape [D].
+            Defines the upper bound of the hypervolume.
+            Should be equal or bigger than the anti-ideal point of the Pareto set.
+            For comparing results across runs, the same reference point must be used.
+        :return: hypervolume indicator
+        :raise ValueError (or `tf.errors.InvalidArgumentError`): If ``reference`` has an invalid
+            shape.
+        :raise `tf.errors.InvalidArgumentError`: If ``reference`` is less than the anti-ideal point
+            in any dimension.
+        """
+        tf.debugging.assert_greater_equal(reference, self.front)
+
+        tf.debugging.assert_shapes(
+            [
+                (self.bounds.lower_idx, ["N", "D"]),
+                (self.bounds.upper_idx, ["N", "D"]),
+                (self.front, ["M", "D"]),
+                (reference, ["D"]),
+            ]
+        )
+
+        min_pfront = tf.reduce_min(self.front, 0, keepdims=True)
+        pseudo_pfront = tf.concat((min_pfront, self.front, reference[None]), 0)
+        N, D = tf.shape(self.bounds.upper_idx)
+
+        idx = tf.tile(tf.expand_dims(tf.range(D), -1), [1, N])
+        upper_idx = tf.reshape(
+            tf.stack([tf.transpose(self.bounds.upper_idx), idx], axis=2), [N * D, 2]
+        )
+        lower_idx = tf.reshape(
+            tf.stack([tf.transpose(self.bounds.lower_idx), idx], axis=2), [N * D, 2]
+        )
+        upper = tf.reshape(tf.gather_nd(pseudo_pfront, upper_idx), [D, N])
+        lower = tf.reshape(tf.gather_nd(pseudo_pfront, lower_idx), [D, N])
+        hypervolume = tf.reduce_sum(tf.reduce_prod(upper - lower, 0))
+
+        return tf.reduce_prod(reference[None] - min_pfront) - hypervolume


Test patch:
diff --git a/tests/unit/test_pareto.py b/tests/unit/test_pareto.py
index 9964f4db..d43dabc8 100644
--- a/tests/unit/test_pareto.py
+++ b/tests/unit/test_pareto.py
@@ -11,11 +11,13 @@
 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 # See the License for the specific language governing permissions and
 # limitations under the License.
+from __future__ import annotations
 
 import numpy.testing as npt
 import pytest
 import tensorflow as tf
 
+from tests.util.misc import TF_DEBUGGING_ERROR_TYPES, NList
 from trieste.utils.pareto import Pareto, non_dominated
 
 
@@ -111,3 +113,42 @@ def test_pareto_2d_bounds() -> None:
     npt.assert_allclose(
         pareto_2d.front, tf.constant([[0.1419, 0.9340], [0.1576, 0.7922], [0.4854, 0.0357]])
     )
+
+
+@pytest.mark.parametrize("reference", [0.0, [0.0], [[0.0]]])
+def test_pareto_hypervolume_indicator_raises_for_reference_with_invalid_shape(
+    reference: NList[float],
+) -> None:
+    pareto = Pareto(tf.constant([[-1.0, -0.6], [-0.8, -0.7], [-0.6, -1.1]]))
+
+    with pytest.raises(TF_DEBUGGING_ERROR_TYPES):
+        pareto.hypervolume_indicator(tf.constant(reference))
+
+
+@pytest.mark.parametrize("reference", [[0.1, -0.65], [-0.7, -0.1]])
+def test_pareto_hypervolume_indicator_raises_for_reference_below_anti_ideal_point(
+    reference: list[float],
+) -> None:
+    pareto = Pareto(tf.constant([[-1.0, -0.6], [-0.8, -0.7], [-0.6, -1.1]]))
+
+    with pytest.raises(tf.errors.InvalidArgumentError):
+        pareto.hypervolume_indicator(tf.constant(reference))
+
+
+@pytest.mark.parametrize(
+    "objectives, reference, expected",
+    [
+        ([[1.0, 0.5]], [2.3, 2.0], 1.95),
+        ([[-1.0, -0.6], [-0.8, -0.7], [-0.6, -1.1]], [0.1, -0.1], 0.92),
+        (  # reference point is equal to one pareto point in one dimension
+            [[-1.0, -0.6], [-0.8, -0.7], [-0.6, -1.1]],
+            [0.1, -0.6],
+            0.37,
+        ),
+    ],
+)
+def test_pareto_hypervolume_indicator(
+    objectives: list[list[float]], reference: list[float], expected: float
+) -> None:
+    pareto = Pareto(tf.constant(objectives))
+    npt.assert_allclose(pareto.hypervolume_indicator(tf.constant(reference)), expected)