The Hypervolume Indicator Hessian Matrix: Analytical Expression, Computational Time Complexity, and Sparsity

André H. Deutz, Michael Emmerich, Hao WangEMO 2022 · DOI · OpenReview

Abstract

The problem of approximating the Pareto front of a multiobjective optimization problem can be reformulated as the problem of finding a set that maximizes the hypervolume indicator. This paper establishes the analytical expression of the Hessian matrix of the mapping from a (fixed size) collection of $n$ points in the $d$-dimensional decision space (or $m$ dimensional objective space) to the scalar hypervolume indicator value. To define the Hessian matrix, the input set is vectorized, and the matrix is derived by analytical differentiation of the mapping from a vectorized set to the hypervolume indicator. The Hessian matrix plays a crucial role in second-order methods, such as the Newton-Raphson optimization method, and it can be used for the verification of local optimal sets. So far, the full analytical expression was only established and analyzed for the relatively simple bi-objective case. This paper will derive the full expression for arbitrary dimensions ($m\geq2$ objective functions). For the practically important three-dimensional case, we also provide an asymptotically efficient algorithm with time complexity in $O(n\log n)$ for the exact computation of the Hessian Matrix' non-zero entries. We establish a sharp bound of $12m-6$ for the number of non-zero entries. Also, for the general $m$-dimensional case, a compact recursive analytical expression is established, and its algorithmic implementation is discussed. Also, for the general case, some sparsity results can be established; these results are implied by the recursive expression. To validate and illustrate the analytically derived algorithms and results, we provide a few numerical examples using Python and Mathematica implementations. Open-source implementations of the algorithms and testing data are made available as a supplement to this paper.

Introduction

In multi-objective optimization (MOP), the goal is to find a Pareto front—a set of points representing optimal trade-offs between conflicting objectives. To evaluate the quality of an approximation set, researchers rely on the Hypervolume Indicator (HVI), which measures the size of the objective space dominated by the points. Maximizing this volume is a central task in evolutionary and mathematical optimization.

While the gradient (first derivative) of the HVI has been well-understood, the Hessian matrix (second derivative) remained an enigma for problems with more than two objectives. Without the Hessian, practitioners could not leverage high-performance second-order optimization tools like the Newton-Raphson method, which offers faster convergence than standard gradient descent.

Mathematical Framework and Notation

The authors treat a collection of $n$ points as a single vectorized input to apply multivariate calculus. The table below summarizes the key symbols and domains used throughout the derivation.

Table of symbols and signatures used in the HVI Hessian derivation.

Methodology

The paper bridges the gap between geometric intuition and analytical calculus through several key steps:

  1. Vectorization: Treating $n$ points in $d$-dimensional space as a single long vector allows for standard Hessian construction.
  2. 3D Dimension Sweep: For three-objective cases, the authors developed an algorithm that "sweeps" a plane through the objective space, identifying that Hessian components correspond to the lengths of the edges where facets of the dominated region meet.
  3. Recursive Analytical Expression: For the general $m$-dimensional case, a recursive formula was derived. It shows that the second derivative of the $m$-dimensional HVI can be calculated using the $(m-2)$-dimensional Lebesgue measure of specific point projections.
  4. Chain Rule Construction: A framework is provided to translate the Hessian from the objective space back to the decision space, making it applicable to real-world engineering variables.

Geometric Insights and Sparsity

A major contribution of this work is the geometric interpretation of the Hessian in 3D. While the HVI gradient relates to the area of the facets of the dominated region, the Hessian entries relate to the lengths of the lines (edges) where those facets intersect.

Geometric interpretation of HVI derivatives in 3D space, showing the relationship between partial derivatives and boundary segments.

This geometric perspective led to the discovery of extreme sparsity. In 3D, the number of non-zero entries is at most $12n - 6$. This linear growth means that adding more points does not cause a computational explosion in second-order optimization. Furthermore, the authors proved that the second partial derivative with respect to the same coordinate of the same point is always zero, as moving a point along one axis doesn't change the rate of volume change along that same axis.

Key Results

  • Computational Efficiency: The authors established an asymptotically optimal time complexity of $O(n \log n)$ for computing the Hessian in 3D.
  • Generalization: The work provides the first compact, recursive analytical expression for the Hessian in arbitrary $m$-dimensions ($m \ge 2$).
  • Validation: Formulas were validated using synthetic numerical examples ($m=3, 4$) and cross-validated against numerical approximations and symbolic computations.
  • Open Source: Python and Mathematica implementations have been released to facilitate the integration of second-order methods into existing optimization pipelines.

Conclusion and Future Work

While the 3D case is highly efficient, the exact complexity for $m > 4$ objectives remains an open question, likely growing exponentially with $m$. Future research will focus on the numerical stability of the Hessian when points are degenerate or highly clustered. Additionally, the vectorization approach used here may be applicable to other quality indicators, such as the Inverted Generational Distance (IGD), potentially leading to a new family of second-order multi-objective optimization techniques.

Summary updated

Abstract

The problem of approximating the Pareto front of a multiobjective optimization problem can be reformulated as the problem of finding a set that maximizes the hypervolume indicator. This paper establishes the analytical expression of the Hessian matrix of the mapping from a (fixed size) collection of n points in the d-dimensional decision space (or m dimensional objective space) to the scalar hypervolume indicator value. To define the Hessian matrix, the input set is vectorized, and the matrix is derived by analytical differentiation of the mapping from a vectorized set to the hypervolume indicator. The Hessian matrix plays a crucial role in second-order methods, such as the Newton-Raphson optimization method, and it can be used for the verification of local optimal sets. So far, the full analytical expression was only established and analyzed for the relatively simple bi-objective case. This paper will derive the full expression for arbitrary dimensions ( $$m\ge 2$$ objective functions). For the practically important three-dimensional case, we also provide an asymptotically efficient algorithm with time complexity in $$O(n\log n)$$ for the exact computation of the Hessian Matrix’ non-zero entries. We establish a sharp bound of $$12m-6$$ for the number of non-zero entries. Also, for the general m-dimensional case, a compact recursive analytical expression is established, and its algorithmic implementation is discussed. Also, for the general case, some sparsity results can be established; these results are implied by the recursive expression. To validate and illustrate the analytically derived algorithms and results, we provide a few numerical examples using Python and Mathematica implementations. Open-source implementations of the algorithms and testing data are made available as a supplement to this paper.
BibTeX
@inproceedings{deutz2022hypervolume,
  author = {André H. Deutz and Michael Emmerich and Hao Wang},
  title = {{The Hypervolume Indicator Hessian Matrix: Analytical Expression, Computational Time Complexity, and Sparsity}},
  booktitle = {EMO},
  year = {2022},
  doi = {10.1007/978-3-031-27250-9\_29},
}
Figure