Abstract
The goal of multi-objective optimisation is to identify a collection ofpoints which describe the best possible trade-offs between the multipleobjectives. In order to solve this vector-valued optimisation problem,practitioners often appeal to the use of scalarisation functions in order totransform the multi-objective problem into a collection of single-objectiveproblems. This set of scalarised problems can then be solved using traditionalsingle-objective optimisation techniques. In this work, we formalise thisconvention into a general mathematical framework. We show how this strategyeffectively recasts the original multi-objective optimisation problem into asingle-objective optimisation problem defined over sets. An appropriate classof objective functions for this new problem are the R2 utilities, which areutility functions that are defined as a weighted integral over the scalarisedoptimisation problems. As part of our work, we show that these utilities aremonotone and submodular set functions which can be optimised effectively usinggreedy optimisation algorithms. We then analyse the performance of these greedyalgorithms both theoretically and empirically. Our analysis largely focusses onBayesian optimisation, which is a popular probabilistic framework for black-boxoptimisation.