IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v78y2020i3d10.1007_s10898-020-00923-x.html
   My bibliography  Save this article

Expected improvement for expensive optimization: a review

Author

Listed:
  • Dawei Zhan

    (Southwest Jiaotong University)

  • Huanlai Xing

    (Southwest Jiaotong University)

Abstract

The expected improvement (EI) algorithm is a very popular method for expensive optimization problems. In the past twenty years, the EI criterion has been extended to deal with a wide range of expensive optimization problems. This paper gives a comprehensive review of the EI extensions designed for parallel optimization, multiobjective optimization, constrained optimization, noisy optimization, multi-fidelity optimization and high-dimensional optimization. The main challenges of extending the EI approach to solve these complex optimization problems are pointed out, and the ideas proposed in literature to tackle these challenges are highlighted. For each reviewed algorithm, the surrogate modeling method, the computation of the infill criterion and the internal optimization of the infill criterion are carefully studied and compared. In addition, the monotonicity properties of the multiobjective EI criteria and constrained EI criteria are analyzed in detail. Through this review, we give an organized summary about the EI developments in the past twenty years and show a clear picture about how the EI approach has advanced. In the end of this paper, several interesting problems and future research topics about the EI developments are given.

Suggested Citation

  • Dawei Zhan & Huanlai Xing, 2020. "Expected improvement for expensive optimization: a review," Journal of Global Optimization, Springer, vol. 78(3), pages 507-544, November.
  • Handle: RePEc:spr:jglopt:v:78:y:2020:i:3:d:10.1007_s10898-020-00923-x
    DOI: 10.1007/s10898-020-00923-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-020-00923-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10898-020-00923-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Jalali, Hamed & Van Nieuwenhuyse, Inneke & Picheny, Victor, 2017. "Comparison of Kriging-based algorithms for simulation optimization with heterogeneous noise," European Journal of Operational Research, Elsevier, vol. 261(1), pages 279-301.
    2. Ivo Couckuyt & Dirk Deschrijver & Tom Dhaene, 2014. "Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization," Journal of Global Optimization, Springer, vol. 60(3), pages 575-594, November.
    3. Zhiwei Feng & Qingbin Zhang & Qingfu Zhang & Qiangang Tang & Tao Yang & Yang Ma, 2015. "A multiobjective optimization based framework to balance the global exploration and local exploitation in expensive optimization," Journal of Global Optimization, Springer, vol. 61(4), pages 677-694, April.
    4. Felipe Viana & Raphael Haftka & Layne Watson, 2013. "Efficient global optimization algorithm assisted by multiple surrogate techniques," Journal of Global Optimization, Springer, vol. 56(2), pages 669-689, June.
    5. Jack Kleijnen & Wim Beers & Inneke Nieuwenhuyse, 2012. "Expected improvement in efficient global optimization through bootstrapped kriging," Journal of Global Optimization, Springer, vol. 54(1), pages 59-73, September.
    6. Cédric Durantin & Julien Marzat & Mathieu Balesdent, 2016. "Analysis of multi-objective Kriging-based methods for constrained global optimization," Computational Optimization and Applications, Springer, vol. 63(3), pages 903-926, April.
    7. Kleijnen, Jack P.C., 2009. "Kriging metamodeling in simulation: A review," European Journal of Operational Research, Elsevier, vol. 192(3), pages 707-716, February.
    8. Zan Yang & Haobo Qiu & Liang Gao & Chen Jiang & Jinhao Zhang, 2019. "Two-layer adaptive surrogate-assisted evolutionary algorithm for high-dimensional computationally expensive problems," Journal of Global Optimization, Springer, vol. 74(2), pages 327-359, June.
    9. Paul Feliot & Julien Bect & Emmanuel Vazquez, 2017. "A Bayesian approach to constrained single- and multi-objective optimization," Journal of Global Optimization, Springer, vol. 67(1), pages 97-133, January.
    10. Xiao, Manyu & Zhang, Guohua & Breitkopf, Piotr & Villon, Pierre & Zhang, Weihong, 2018. "Extended Co-Kriging interpolation method based on multi-fidelity data," Applied Mathematics and Computation, Elsevier, vol. 323(C), pages 120-131.
    11. Ilya O. Ryzhov, 2016. "On the Convergence Rates of Expected Improvement Methods," Operations Research, INFORMS, vol. 64(6), pages 1515-1528, December.
    12. Dmitry Yarotsky, 2013. "Examples of inconsistency in optimization by expected improvement," Journal of Global Optimization, Springer, vol. 56(4), pages 1773-1790, August.
    13. Dawei Zhan & Jiachang Qian & Yuansheng Cheng, 2017. "Pseudo expected improvement criterion for parallel EGO algorithm," Journal of Global Optimization, Springer, vol. 68(3), pages 641-662, July.
    14. Mickaël Binois & David Ginsbourger & Olivier Roustant, 2020. "On the choice of the low-dimensional domain for global optimization via random embeddings," Journal of Global Optimization, Springer, vol. 76(1), pages 69-90, January.
    15. D. Huang & T. Allen & W. Notz & N. Zeng, 2006. "Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models," Journal of Global Optimization, Springer, vol. 34(3), pages 441-466, March.
    16. Julien Pelamatti & Loïc Brevault & Mathieu Balesdent & El-Ghazali Talbi & Yannick Guerin, 2019. "Efficient global optimization of constrained mixed variable problems," Journal of Global Optimization, Springer, vol. 73(3), pages 583-613, March.
    17. Gneiting, Tilmann, 2002. "Compactly Supported Correlation Functions," Journal of Multivariate Analysis, Elsevier, vol. 83(2), pages 493-508, November.
    18. Michael Emmerich & Kaifeng Yang & André Deutz & Hao Wang & Carlos M. Fonseca, 2016. "A Multicriteria Generalization of Bayesian Global Optimization," Springer Optimization and Its Applications, in: Panos M. Pardalos & Anatoly Zhigljavsky & Julius Žilinskas (ed.), Advances in Stochastic and Deterministic Global Optimization, pages 229-242, Springer.
    19. Rommel Regis & Christine Shoemaker, 2005. "Constrained Global Optimization of Expensive Black Box Functions Using Radial Basis Functions," Journal of Global Optimization, Springer, vol. 31(1), pages 153-171, January.
    20. Dawei Zhan & Jiachang Qian & Yuansheng Cheng, 2017. "Balancing global and local search in parallel efficient global optimization algorithms," Journal of Global Optimization, Springer, vol. 67(4), pages 873-892, April.
    21. Binois, M. & Ginsbourger, D. & Roustant, O., 2015. "Quantifying uncertainty on Pareto fronts with Gaussian process conditional simulations," European Journal of Operational Research, Elsevier, vol. 243(2), pages 386-394.
    22. Shengguan Xu & Hongquan Chen, 2018. "Nash game based efficient global optimization for large-scale design problems," Journal of Global Optimization, Springer, vol. 71(2), pages 361-381, June.
    23. Peter Frazier & Warren Powell & Savas Dayanik, 2009. "The Knowledge-Gradient Policy for Correlated Normal Beliefs," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 599-613, November.
    24. Svenson, Joshua & Santner, Thomas, 2016. "Multiobjective optimization of expensive-to-evaluate deterministic computer simulator models," Computational Statistics & Data Analysis, Elsevier, vol. 94(C), pages 250-264.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Jamie A. Manson & Thomas W. Chamberlain & Richard A. Bourne, 2021. "MVMOO: Mixed variable multi-objective optimisation," Journal of Global Optimization, Springer, vol. 80(4), pages 865-886, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dawei Zhan & Jiachang Qian & Yuansheng Cheng, 2017. "Balancing global and local search in parallel efficient global optimization algorithms," Journal of Global Optimization, Springer, vol. 67(4), pages 873-892, April.
    2. Jesús Martínez-Frutos & David Herrero-Pérez, 2016. "Kriging-based infill sampling criterion for constraint handling in multi-objective optimization," Journal of Global Optimization, Springer, vol. 64(1), pages 97-115, January.
    3. Dawei Zhan & Jiachang Qian & Yuansheng Cheng, 2017. "Pseudo expected improvement criterion for parallel EGO algorithm," Journal of Global Optimization, Springer, vol. 68(3), pages 641-662, July.
    4. Satyajith Amaran & Nikolaos V. Sahinidis & Bikram Sharda & Scott J. Bury, 2016. "Simulation optimization: a review of algorithms and applications," Annals of Operations Research, Springer, vol. 240(1), pages 351-380, May.
    5. Jalali, Hamed & Van Nieuwenhuyse, Inneke & Picheny, Victor, 2017. "Comparison of Kriging-based algorithms for simulation optimization with heterogeneous noise," European Journal of Operational Research, Elsevier, vol. 261(1), pages 279-301.
    6. Qun Meng & Songhao Wang & Szu Hui Ng, 2022. "Combined Global and Local Search for Optimization with Gaussian Process Models," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 622-637, January.
    7. Shengguan Xu & Hongquan Chen, 2018. "Nash game based efficient global optimization for large-scale design problems," Journal of Global Optimization, Springer, vol. 71(2), pages 361-381, June.
    8. Mehdad, E. & Kleijnen, Jack P.C., 2014. "Classic Kriging versus Kriging with Bootstrapping or Conditional Simulation : Classic Kriging's Robust Confidence Intervals and Optimization (Revised version of CentER DP 2013-038)," Discussion Paper 2014-076, Tilburg University, Center for Economic Research.
    9. Kleijnen, Jack P.C., 2013. "Simulation-Optimization via Kriging and Bootstrapping : A Survey (Revision of CentER DP 2011-064)," Discussion Paper 2013-064, Tilburg University, Center for Economic Research.
    10. Fani Boukouvala & M. M. Faruque Hasan & Christodoulos A. Floudas, 2017. "Global optimization of general constrained grey-box models: new method and its application to constrained PDEs for pressure swing adsorption," Journal of Global Optimization, Springer, vol. 67(1), pages 3-42, January.
    11. Songhao Wang & Szu Hui Ng & William Benjamin Haskell, 2022. "A Multilevel Simulation Optimization Approach for Quantile Functions," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 569-585, January.
    12. Morales-Enciso, Sergio & Branke, Juergen, 2015. "Tracking global optima in dynamic environments with efficient global optimization," European Journal of Operational Research, Elsevier, vol. 242(3), pages 744-755.
    13. Zilong Wang & Marianthi Ierapetritou, 2018. "Surrogate-based feasibility analysis for black-box stochastic simulations with heteroscedastic noise," Journal of Global Optimization, Springer, vol. 71(4), pages 957-985, August.
    14. Pedrielli, Giulia & Wang, Songhao & Ng, Szu Hui, 2020. "An extended Two-Stage Sequential Optimization approach: Properties and performance," European Journal of Operational Research, Elsevier, vol. 287(3), pages 929-945.
    15. Mehdad, E. & Kleijnen, Jack P.C., 2014. "Global Optimization for Black-box Simulation via Sequential Intrinsic Kriging," Other publications TiSEM 8fa8d96f-a086-4c4b-88ab-9, Tilburg University, School of Economics and Management.
    16. Emre Barut & Warren Powell, 2014. "Optimal learning for sequential sampling with non-parametric beliefs," Journal of Global Optimization, Springer, vol. 58(3), pages 517-543, March.
    17. Krityakierne, Tipaluck & Baowan, Duangkamon, 2020. "Aggregated GP-based Optimization for Contaminant Source Localization," Operations Research Perspectives, Elsevier, vol. 7(C).
    18. Diana M. Negoescu & Peter I. Frazier & Warren B. Powell, 2011. "The Knowledge-Gradient Algorithm for Sequencing Experiments in Drug Discovery," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 346-363, August.
    19. Kleijnen, Jack P.C. & Mehdad, E., 2013. "Conditional simulation for efficient global optimization," Other publications TiSEM 52e4860d-9887-4a63-b19a-7, Tilburg University, School of Economics and Management.
    20. Zan Yang & Haobo Qiu & Liang Gao & Chen Jiang & Jinhao Zhang, 2019. "Two-layer adaptive surrogate-assisted evolutionary algorithm for high-dimensional computationally expensive problems," Journal of Global Optimization, Springer, vol. 74(2), pages 327-359, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:78:y:2020:i:3:d:10.1007_s10898-020-00923-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.