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

Nelder-Mead "单纯形“方法，首次发表于1965年，是世界上最流行的不使用导数的无约束非线性函数最小化技术之一; Nelder-Mead方法是成百上千个涉及优化的科学和工程应用的核心。Nelder-Mead方法的优点包括描述和实现简单，以及出色的“最佳情况”行为，特别是在用相对较少的函数值实现快速改进方面。 它的缺点包括停滞或失败，通常是缓慢和痛苦的。而且，尽管广泛使用了近40年，其基本性质仍然不清楚，甚至是神秘的。拟议的研究旨在提高对Nelder-Mead方法在理论和实践中的理解。直到1998年，才获得了原始Nelder-Mead方法的理论收敛结果，而它今天的已知理论是有限的（仅限于一维和二维），而且相对来说，也许是相当薄弱的。几乎令人尴尬的是，这个几乎无处不在的、极其简单的方法的数学和收敛特性还没有完全解决。 在试图产生所需的理论，拟议的研究将应用工具，如离散动力系统和几何性质的表征，这是非标准的分析无约束优化。由于非导数优化方法已在过去的15年中发展，拥有基本上完整的理论，人们可能会问，为什么它是不必要的，而研究Nelder-Mead方法。 原因是，尽管缺乏已知的理论基础，Nelder-Mead经常比它的竞争对手更快地产生一个足够好的答案。 但是Nelder-Mead并不总是工作得很好-它的性能有时很好，有时很糟糕-而且这种变化的原因还没有被详细研究。 研究的第二部分是探索在一个大的、精心挑选的测试问题集上该方法会发生什么（以及为什么）。 一个希望是，“类似Nelder-Mead”的方法将出现，保留原来的味道和可取的属性，但克服其最严重的缺陷。鉴于Nelder-Mead方法的流行，研究的结果应该是改进的非导数优化方法，能够可靠地解决各种科学和工程问题。首席研究员是第一个证明关于原始Nelder的理论结果的人之一，Mead方法，并将注意力集中在Nelder-Mead方法上，该方法多年来一直被主流优化社区所轻视或忽视。 在贝尔实验室工作期间，她通过在一个成功的产品（无线系统设计的“WISE”工具）中实施Nelder-Mead方法获得了实践经验。由于Nelder-Mead方法易于形象化和解释，它是一个基于网络的动画和解释材料传播的明显候选者，可以用于研究生和本科教育，以及科学，工程和医学的从业者。

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.