The Nelder-Mead Simplex Method: Theory, Performance, Context, and Applications

点击翻译按钮获取中文摘要

The Nelder-Mead ``simplex'' method, first published in 1965,is one of the world's most popular techniques for unconstrainedminimization of nonlinear functions without using derivatives;Nelder-Mead lies at the heart of hundreds, probably thousands,of scientific and engineering applications that involveoptimization.The virtues of the Nelder-Mead method include simplicity ofdescription and implementation, and excellent ``best case''behavior, especially in achieving rapid improvement witha relatively small number of function values. Its flawsinclude stagnation or failure, typically slow and painful.And, despite almost 40 years of widespread use, itsfundamental nature remains unclear and even mysterious.The proposed research aims to improve understanding ofthe Nelder-Mead method in both theory and practice.No theoretical convergence results for the originalNelder-Mead method were obtained until 1998, and itsknown theory today is limited (to dimensions one andtwo) as well as relatively, perhaps unavoidably, weak.It is almost embarrassing that the mathematical andconvergence properties of this nearly ubiquitous, seeminglysimple method are not fully settled. In attempting toproduce the needed theory, the proposed research will applytools like discrete dynamical systems and characterization ofgeometric properties, which are nonstandard in analysis ofunconstrained optimization.Since non-derivative optimization methods have beendeveloped in the last 15 years that possess essentiallycomplete theories, one might wonder why it is worthwhileto study the Nelder-Mead method. The reason is that,despite its lack of known theoretical underpinnings,Nelder-Mead very often produces a good enough answermore rapidly than its competitors. But Nelder-Mead doesnot consistently work well---its performance is sometimesexcellent, sometimes terrible---and the reasons for thisvariation have not been examined in detail. A second partof the proposed research is to explore what happens (andwhy) to the method on a large, carefully selected set oftest problems. A hope is that ``Nelder-Mead-like'' methodswill emerge that retain the flavor and desirable propertiesof the original but overcome its worst flaws.Given the popularity of the Nelder-Mead method, the resultof the research should be improved non-derivative optimizationmethods that are capable of reliably solving a variety ofscientific and engineering problems.The principal investigator was one of the first to provetheoretical results about the original Nelder-Mead methodand to focus attention on the Nelder-Mead method, whichwas scorned or ignored for many years by the mainstreamoptimization community. While at Bell Labs, she gainedpractical experience by implementing the Nelder-Meadmethod in a successful product (the ``WISE'' tool forwireless system design).Because the Nelder-Mead method is easy to visualize andexplain, it is an obvious candidate for Web-based disseminationof animations and explanatory material that can be used ingraduate and undergraduate education, as well as bypractitioners, in science, engineering, and medicine.