The Nelder-Mead ``simplex'' method, first published in 1965, is one of the world's most popular techniques for unconstrained minimization of nonlinear functions without using derivatives; Nelder-Mead lies at the heart of hundreds, probably thousands, of scientific and engineering applications that involve optimization.
The virtues of the Nelder-Mead method include simplicity of description and implementation, and excellent ``best case'' behavior, especially in achieving rapid improvement with a relatively small number of function values. Its flaws include stagnation or failure, typically slow and painful. And, despite almost 40 years of widespread use, its fundamental nature remains unclear and even mysterious. The proposed research aims to improve understanding of the Nelder-Mead method in both theory and practice.
No theoretical convergence results for the original Nelder-Mead method were obtained until 1998, and its known theory today is limited (to dimensions one and two) as well as relatively, perhaps unavoidably, weak. It is almost embarrassing that the mathematical and convergence properties of this nearly ubiquitous, seemingly simple method are not fully settled. In attempting to produce the needed theory, the proposed research will apply tools like discrete dynamical systems and characterization of geometric properties, which are nonstandard in analysis of unconstrained optimization.
Since non-derivative optimization methods have been developed in the last 15 years that possess essentially complete theories, one might wonder why it is worthwhile to study the Nelder-Mead method. The reason is that, despite its lack of known theoretical underpinnings, Nelder-Mead very often produces a good enough answer more rapidly than its competitors. But Nelder-Mead does not consistently work well---its performance is sometimes excellent, sometimes terrible---and the reasons for this variation have not been examined in detail. A second part of the proposed research is to explore what happens (and why) to the method on a large, carefully selected set of test problems. A hope is that ``Nelder-Mead-like'' methods will emerge that retain the flavor and desirable properties of the original but overcome its worst flaws.
Given the popularity of the Nelder-Mead method, the result of the research should be improved non-derivative optimization methods that are capable of reliably solving a variety of scientific and engineering problems.
The principal investigator was one of the first to prove theoretical results about the original Nelder-Mead method and to focus attention on the Nelder-Mead method, which was scorned or ignored for many years by the mainstream optimization community. While at Bell Labs, she gained practical experience by implementing the Nelder-Mead method in a successful product (the ``WISE'' tool for wireless system design).
Because the Nelder-Mead method is easy to visualize and explain, it is an obvious candidate for Web-based dissemination of animations and explanatory material that can be used in graduate and undergraduate education, as well as by practitioners, in science, engineering, and medicine.
