IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v220y2012i3p684-694.html
   My bibliography  Save this article

Stochastic Nelder–Mead simplex method – A new globally convergent direct search method for simulation optimization

Author

Listed:
  • Chang, Kuo-Hao

Abstract

Nelder–Mead simplex method (NM), originally developed in deterministic optimization, is an efficient direct search method that optimizes the response function merely by comparing function values. While successful in deterministic settings, the application of NM to simulation optimization suffers from two problems: (1) It lacks an effective sample size scheme for controlling noise; consequently the algorithm can be misled to the wrong direction because of noise, and (2) it is a heuristic algorithm; the quality of estimated optimal solution cannot be quantified. We propose a new variant, called Stochastic Nelder–Mead simplex method (SNM), that employs an effective sample size scheme and a specially-designed global and local search framework to address these two problems. Without the use of gradient information, SNM can handle problems where the response functions are nonsmooth or gradient does not exist. This is complementary to the existing gradient-based approaches. We prove that SNM can converge to the true global optima with probability one. An extensive numerical study also shows that the performance SNM is promising and is worthy of further investigation.

Suggested Citation

  • Chang, Kuo-Hao, 2012. "Stochastic Nelder–Mead simplex method – A new globally convergent direct search method for simulation optimization," European Journal of Operational Research, Elsevier, vol. 220(3), pages 684-694.
  • Handle: RePEc:eee:ejores:v:220:y:2012:i:3:p:684-694
    DOI: 10.1016/j.ejor.2012.02.028
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712001609
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2012.02.028?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. David G. Humphrey & James R. Wilson, 2000. "A Revised Simplex Search Procedure for Stochastic Simulation Response Surface Optimization," INFORMS Journal on Computing, INFORMS, vol. 12(4), pages 272-283, November.
    2. Russell R. Barton & John S. Ivey, Jr., 1996. "Nelder-Mead Simplex Modifications for Simulation Optimization," Management Science, INFORMS, vol. 42(7), pages 954-973, July.
    3. Andrieu, Laetitia & Cohen, Guy & Vázquez-Abad, Felisa J., 2011. "Gradient-based simulation optimization under probability constraints," European Journal of Operational Research, Elsevier, vol. 212(2), pages 345-351, July.
    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. Neshat, Mehdi & Nezhad, Meysam Majidi & Sergiienko, Nataliia Y. & Mirjalili, Seyedali & Piras, Giuseppe & Garcia, Davide Astiaso, 2022. "Wave power forecasting using an effective decomposition-based convolutional Bi-directional model with equilibrium Nelder-Mead optimiser," Energy, Elsevier, vol. 256(C).
    2. Charles Audet & Kwassi Joseph Dzahini & Michael Kokkolaras & Sébastien Le Digabel, 2021. "Stochastic mesh adaptive direct search for blackbox optimization using probabilistic estimates," Computational Optimization and Applications, Springer, vol. 79(1), pages 1-34, May.
    3. Chang, Kuo-Hao, 2015. "A direct search method for unconstrained quantile-based simulation optimization," European Journal of Operational Research, Elsevier, vol. 246(2), pages 487-495.
    4. Chang, Kuo-Hao & Cuckler, Robert & Lee, Song-Lin & Lee, Loo Hay, 2022. "Discrete conditional-expectation-based simulation optimization: Methodology and applications," European Journal of Operational Research, Elsevier, vol. 298(1), pages 213-228.
    5. Chang, Kuo-Hao & Kuo, Po-Yi, 2018. "An efficient simulation optimization method for the generalized redundancy allocation problem," European Journal of Operational Research, Elsevier, vol. 265(3), pages 1094-1101.
    6. Chang, Kuo-Hao & Chen, Tzu-Li & Yang, Fu-Hao & Chang, Tzu-Yin, 2023. "Simulation optimization for stochastic casualty collection point location and resource allocation problem in a mass casualty incident," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1237-1262.
    7. Lux, Thomas, 2018. "Estimation of agent-based models using sequential Monte Carlo methods," Journal of Economic Dynamics and Control, Elsevier, vol. 91(C), pages 391-408.
    8. Javier Cano & Cesar Alfaro & Javier Gomez & Abraham Duarte, 2022. "Out of the Niche: Using Direct Search Methods to Find Multiple Global Optima," Mathematics, MDPI, vol. 10(9), pages 1-20, April.
    9. Neshat, Mehdi & Nezhad, Meysam Majidi & Abbasnejad, Ehsan & Mirjalili, Seyedali & Groppi, Daniele & Heydari, Azim & Tjernberg, Lina Bertling & Astiaso Garcia, Davide & Alexander, Bradley & Shi, Qinfen, 2021. "Wind turbine power output prediction using a new hybrid neuro-evolutionary method," Energy, Elsevier, vol. 229(C).
    10. Lux, Thomas, 2017. "Estimation of agent-based models using sequential Monte Carlo methods," Economics Working Papers 2017-07, Christian-Albrechts-University of Kiel, Department of Economics.
    11. Charles Audet & Christophe Tribes, 2018. "Mesh-based Nelder–Mead algorithm for inequality constrained optimization," Computational Optimization and Applications, Springer, vol. 71(2), pages 331-352, November.
    12. Chang, Kuo-Hao & Wu, Ying-Zheng & Su, Wen-Ray & Lin, Lee-Yaw, 2024. "A simulation evacuation framework for effective disaster preparedness strategies and response decision making," European Journal of Operational Research, Elsevier, vol. 313(2), pages 733-746.
    13. 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.

    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. Chang, Kuo-Hao, 2015. "A direct search method for unconstrained quantile-based simulation optimization," European Journal of Operational Research, Elsevier, vol. 246(2), pages 487-495.
    2. M Laguna & J Molina & F Pérez & R Caballero & A G Hernández-Díaz, 2010. "The challenge of optimizing expensive black boxes: a scatter search/rough set theory approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 53-67, January.
    3. 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.
    4. Alkhamis, Talal M. & Ahmed, Mohamed A., 2006. "A modified Hooke and Jeeves algorithm with likelihood ratio performance extrapolation for simulation optimization," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1802-1815, November.
    5. W. Liu & Y. H. Dai, 2001. "Minimization Algorithms Based on Supervisor and Searcher Cooperation," Journal of Optimization Theory and Applications, Springer, vol. 111(2), pages 359-379, November.
    6. Sudarshan Kumar & Tiziana Di Matteo & Anindya S. Chakrabarti, 2020. "Disentangling shock diffusion on complex networks: Identification through graph planarity," Papers 2001.01518, arXiv.org.
    7. David G. Humphrey & James R. Wilson, 2000. "A Revised Simplex Search Procedure for Stochastic Simulation Response Surface Optimization," INFORMS Journal on Computing, INFORMS, vol. 12(4), pages 272-283, November.
    8. Fan, Shu-Kai S. & Zahara, Erwie, 2007. "A hybrid simplex search and particle swarm optimization for unconstrained optimization," European Journal of Operational Research, Elsevier, vol. 181(2), pages 527-548, September.
    9. Hachicha, Wafik & Ammeri, Ahmed & Masmoudi, Faouzi & Chachoub, Habib, 2010. "A comprehensive literature classification of simulation optimisation methods," MPRA Paper 27652, University Library of Munich, Germany.
    10. Galip Altinay, 2003. "Estimating growth rate in the presence of serially correlated errors," Applied Economics Letters, Taylor & Francis Journals, vol. 10(15), pages 967-970.
    11. Kao, Chiang & Chen, Shih-Pin, 2006. "A stochastic quasi-Newton method for simulation response optimization," European Journal of Operational Research, Elsevier, vol. 173(1), pages 30-46, August.
    12. Arsham H., 1998. "Techniques for Monte Carlo Optimizing," Monte Carlo Methods and Applications, De Gruyter, vol. 4(3), pages 181-230, December.
    13. Pinto, Roberto, 2016. "Stock rationing under a profit satisficing objective," Omega, Elsevier, vol. 65(C), pages 55-68.
    14. Frazier, David T. & Oka, Tatsushi & Zhu, Dan, 2019. "Indirect inference with a non-smooth criterion function," Journal of Econometrics, Elsevier, vol. 212(2), pages 623-645.
    15. David J. Eckman & Shane G. Henderson & Sara Shashaani, 2023. "Diagnostic Tools for Evaluating and Comparing Simulation-Optimization Algorithms," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 350-367, March.
    16. Rosen, Scott L. & Harmonosky, Catherine M. & Traband, Mark T., 2007. "A simulation optimization method that considers uncertainty and multiple performance measures," European Journal of Operational Research, Elsevier, vol. 181(1), pages 315-330, August.
    17. Ozden, Mufit & Ho, Yu-Chi, 2003. "A probabilistic solution-generator for simulation," European Journal of Operational Research, Elsevier, vol. 146(1), pages 35-51, April.
    18. Wilson, Amy D. & King, Russell E. & Wilson, James R., 2004. "Case study on statistically estimating minimum makespan for flow line scheduling problems," European Journal of Operational Research, Elsevier, vol. 155(2), pages 439-454, June.
    19. Neddermeijer, H.G. & Piersma, N. & van Oortmarssen, G.J. & Habbema, J.D.F. & Dekker, R., 1999. "Comparison of response surface methodology and the Nelder and Mead simplex method for optimization in microsimulation models," Econometric Institute Research Papers EI 9924-/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    20. Kuo-Hao Chang & L. Jeff Hong & Hong Wan, 2013. "Stochastic Trust-Region Response-Surface Method (STRONG)---A New Response-Surface Framework for Simulation Optimization," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 230-243, May.

    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:eee:ejores:v:220:y:2012:i:3:p:684-694. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.