Preprint · 2018 · Open access

Fast Exact Computation of Expected HyperVolume Improvement

Guang Zhao, Raymundo Arróyave, Xiaoning Qian

arXiv (Cornell University) · Published 18 December 2018 · DOI 10.48550/arxiv.1812.07692

Open PDFView at the publisherCite this paper

In brief

“Fast Exact Computation of Expected HyperVolume Improvement” is a 2018 preprint by Guang Zhao and 2 co-authors, published in arXiv (Cornell University). OpenAlex counts 28 citations as of 19 November 2026. It is open access: the full text is free to read at arXiv (Cornell University).

Citations
28
Most cited in
2021 (5)
References
24
Authors
3

Abstract

In multi-objective Bayesian optimization and surrogate-based evolutionary algorithms, Expected HyperVolume Improvement (EHVI) is widely used as the acquisition function to guide the search approaching the Pareto front. This paper focuses on the exact calculation of EHVI given a nondominated set, for which the existing exact algorithms are complex and can be inefficient for problems with more than three objectives. Integrating with different decomposition algorithms, we propose a new method for calculating the integral in each decomposed high-dimensional box in constant time. We develop three new exact EHVI calculation algorithms based on three region decomposition methods. The first grid-based algorithm has a complexity of $O(m\cdot n^m)$ with $n$ denoting the size of the nondominated set and $m$ the number of objectives. The Walking Fish Group (WFG)-based algorithm has a worst-case complexity of $O(m\cdot 2^n)$ but has a better average performance. These two can be applied for problems with any $m$. The third CLM-based algorithm is only for $m=3$ and asymptotically optimal with complexity $Θ(n\log{n})$. Performance comparison results show that all our three algorithms are at least twice faster than the state-of-the-art algorithms with the same decomposition methods. When $m>3$, our WFG-based algorithm can be over $10^2$ faster than the corresponding existing algorithms. Our algorithm is demonstrated in an example involving efficient multi-objective material design with Bayesian optimization.

Cite this paper

Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.

APA 7

Zhao, G., Arróyave, R., & Qian, X. (2018). Fast Exact Computation of Expected HyperVolume Improvement. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1812.07692

MLA 9

Zhao, Guang, et al. “Fast Exact Computation of Expected HyperVolume Improvement.” arXiv (Cornell University), 2018. https://doi.org/10.48550/arxiv.1812.07692.

Chicago

Zhao, Guang, Raymundo Arróyave, and Xiaoning Qian. 2018. “Fast Exact Computation of Expected HyperVolume Improvement.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.1812.07692.

Harvard

Zhao, G., Arróyave, R. and Qian, X. (2018) ‘Fast Exact Computation of Expected HyperVolume Improvement’, arXiv (Cornell University). doi:10.48550/arxiv.1812.07692.

IEEE

G. Zhao, R. Arróyave, and X. Qian, “Fast Exact Computation of Expected HyperVolume Improvement,” arXiv (Cornell University), 2018, doi: 10.48550/arxiv.1812.07692.

BibTeX

@misc{zhao2018fast,
  title     = {{Fast Exact Computation of Expected HyperVolume Improvement}},
  author    = {Zhao, Guang and Arróyave, Raymundo and Qian, Xiaoning},
  howpublished = {arXiv (Cornell University)},
  year      = {2018},
  doi       = {10.48550/arxiv.1812.07692},
  url       = {https://doi.org/10.48550/arxiv.1812.07692}
}

Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)

Citations by year

YearCitationsShare of the best year
201922
202022
202155
202222
202322
202455
202555
202655

Topic and keywords

Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Multi-Objective Optimization Algorithms

  • expected hypervolume improvement
  • multi-objective Bayesian optimization
  • acquisition functions
  • region decomposition
  • non-dominated set
  • Pareto front
  • high-dimensional integration

Work with this paper

Most-cited papers in Computer Science

All highly cited Computer Science papers

Questions about this paper

How do I cite this paper in APA style?

Zhao, G., Arróyave, R., & Qian, X. (2018). Fast Exact Computation of Expected HyperVolume Improvement. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1812.07692

How many times has this paper been cited?

28 times, according to OpenAlex on 19 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.

Is this paper free to read?

Yes. It is open access at arXiv (Cornell University): sign in and open the PDF from this page.

Who wrote this paper?

Guang Zhao, Raymundo Arróyave, Xiaoning Qian.

What is the DOI of this paper?

10.48550/arxiv.1812.07692, permanently at https://doi.org/10.48550/arxiv.1812.07692. Sign in and open it from this page.

Bibliographic data from OpenAlex (CC0), last checked 19 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.