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

Nelder-Mead 单纯形法：理论、性能、背景和应用

• 批准号: 0430205
• 负责人: Margaret Wright
• 金额: --
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-15 至 2006-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430205&HistoricalAwards=false
• 关键词: Nelder; Mead; Simplex; Method; Theory

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.

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