Nelder-Mead Simplex Modifications for Simulation Optimization

Abstract

When the Nelder-Mead method is used to optimize the expected response of a stochastic system (e.g., an output of a discrete-event simulation model), the simplex-resizing steps of the method introduce risks of inappropriate termination. We give analytical and empirical results describing the performance of Nelder-Mead when it is applied to a response function that incorporates an additive white-noise error, and we use these results to develop new modifications of Nelder-Mead that yield improved estimates of the optimal expected response. Compared to Nelder-Mead, the best performance was obtained by a modified method, RS + S9, in which (a) the best point in the simplex is reevaluated at each shrink, step and (b) the simplex is reduced by 10% (rather than 50%) at each shrink step. In a suite of 18 test problems that were adapted from the MINPACK collection of NETLIB, the expected response at the estimated optimal point obtained by RS + S9 had errors that averaged 15% less than at the original method's estimated optimal point, at an average cost of three times as many function evaluations. Two well-known existing modifications for stochastic responses, the (n + 3)-rule and the next-to-worst rule, were found to be inferior to the new modification RS + S9.