The Hypervolume Indicator

Guerreiro, Fonseca & Paquete, "The Hypervolume Indicator: Computational Problems and Algorithms" — ACM Computing Surveys 54(6), 2021 (arXiv:2005.00515). Answers the spoke's open question about what "best optimizer" means once the objective stops being a single scalar — the case algorithmsbook names but nothing else in the corpus scores.

The problem it solves

Every ranking in this wiki — Dik's suite, coco-bbob — scores one number per run because every problem so far has one objective. A multi-objective run instead returns a Pareto front: a set of solutions where none dominates another (better on one objective, worse on another), so there is no total order to rank against directly.

The hypervolume indicator turns a front back into a single comparable number: the volume of objective space a solution set dominates, measured against a fixed reference point. Two properties make it the field's default:

• Strictly monotonic with respect to Pareto dominance — a set that dominates another always scores strictly higher. No other hypervolume-style indicator has this property, which is why it survived as the standard rather than one option among several.
• Rewards both convergence (closeness to the true front) and diversity (spread across it) in one number, so it can be optimized directly inside an algorithm (as a selection criterion) as well as used to score algorithms after the fact.

What the paper covers

A computational-complexity survey, not a benchmark run: it maps the known problems built on the indicator (compute the value; compute each point's marginal contribution; find the subset of k points maximizing it) to their algorithms and asymptotic costs, and states the hardness result that exact computation is #P-hard in the number of objectives — the reason practical use above ~4–5 objectives switches to Monte Carlo approximation.

What this does and doesn't close

Closes the instrument gap: the corpus now has the T1 citation for the standard tool a multi-objective re-run of this wiki's algorithms would be scored with. Does not close the edge itself — no page here runs a multi-objective benchmark; EMA, BSA, CMA-ES, DOS and the rest are all still scored on scalar test functions. The successor question is unchanged: does swarm/evolutionary ranking behavior (no dominant optimizer, per no-free-lunch-theorem) hold up once hypervolume replaces a single fitness number, or does the picture change because some algorithms are built for diversity and others aren't?

Related

algorithmsbook · coco-bbob · no-free-lunch-theorem · test-functions-for-optimization