Nelder-Mead Method
  
    The Nelder-Mead method is a simplex method for finding a local minimum of a function of several variables.  It's discovery is attributed to J. A. Nelder and R. Mead.  For two variables, a simplex is a triangle, and the method is a pattern search that compares function values at the three vertices of a triangle.  The worst vertex, where is largest, is rejected and replaced with a new vertex.  A new triangle is formed and the search is continued.  The process generates a sequence of triangles (which might have different shapes), for which the function values at the vertices get smaller and smaller.  The size of the triangles is reduced and the coordinates of the minimum point are found.  
    The algorithm is stated using the term simplex (a generalized triangle in n dimensions) and will find the minimum of a function of n variables.  It is effective and computationally compact.

Initial Triangle  

    Let be the function that is to be minimized.  To start, we are given three vertices of a triangle:  ,  for  .  The function is then evaluated at each of the three points:  ,  for  .  The subscripts are then reordered so that  .  We use the notation  

(1)        ,  ,  and  .  

to help remember that is the best vertex, is good (next to best), and is the worst vertex.  

Midpoint of the Good Side

    The construction process uses the midpoint of the line segment joining and .  It is found by averaging the coordinates:  

(2)        .  

Reflection Using the Point  

    The function decreases as we move along the side of the triangle from to , and it decreases as we move along the side from to.  Hence it is feasible that takes on smaller values at points that lie away from on the opposite side of the line between and.  We choose a test point that is obtained by “reflecting” the triangle through the side . To determine , we first find the midpoint of the side .  Then draw the line segment from to and call its length d.  This last segment is extended a distance d through to locate the point .  The vector formula for is  

(3)        .  

Expansion Using the Point  

    If the function value at is smaller than the function value at , then we have moved in the correct direction toward the minimum.  Perhaps the minimum is just a bit farther than the point .  So we extend the line segment through and to the point .  This forms an expanded triangle .  The point is found by moving an additional distance d along the line joining and .  If the function value at is less than the function value at , then we have found a better vertex than .  The vector formula for is  
    
(4)        .    

Contraction Using the Point

    If the function values at and are the same, another point must be tested.  Perhaps the function is smaller at , but we cannot replace with because we must have a triangle.  Consider the two midpoints and of the line segments and , respectively.  The point with the smaller function value is called , and the new triangle is .  
Note:  The choice between and might seem inappropriate for the two-dimensional case, but it is important in higher dimensions.  

Shrink Toward  

    If the function value at is not less than the value at , the points and must be shrunk toward .  The point is replaced with , and is replaced with , which is the midpoint of the line segment joining with .

Logical Decisions for Each Step

A computationally efficient algorithm should perform function evaluations only if needed.  In each step, a new vertex is found, which replaces . As soon as it is found, further investigation is not needed, and the iteration step is completed.  The logical details for two-dimensional cases are given in the proof.  

Proof  Nelder-Mead Search  Nelder-Mead Search  

Algorithm (Nelder-Mead Search for a Minimum).  To approximate a local minimum of  ,  where    is a continuous function of  n  real variables, and given the    initial starting points    for  .  
Remark.  This is also known as the polytope method.  

Computer Programs  Nelder-Mead Search  Nelder-Mead Search  

Mathematica Subroutine (Nelder-Mead Search for a Minimum).  To approximate a local minimum of  ,  where    is a continuous function of  2  real variables, and given the initial starting points    for  .

Example 1.  Use the Nelder-Mead method to find the minimum of   .  
Solution 1.

A more efficient subroutine

The following subroutine stores the function values in the variables    and the convergence criterion is used to terminate the algorithm when

        .

Example 2.  Use the Nelder-Mead method to find the minimum of   ,
This example is referred to as Rosenbrock's parabolic valley, circa 1960.
Solution 2.

Exercise 3.  Graph the function  .  
Looking at your graphs, estimate the location of the local minima.  
Solution 3.

Various Scenarios and Animations for the Nelder-Mead Method.

Program (Nelder-Mead's minimization method).  Including graphics commands to draw the vertices and triangles used in finding the solution.

Example 4.  Use the Nelder-Mead method to find the minimum of   .  
Use the modified program listed above that includes graphics commands to draw the vertices and triangles used in finding the solution.
Solution 4.

Animations (Nelder-Mead Search  Nelder-Mead Search).  Internet hyperlinks to animations.  

Research Experience for Undergraduates

Nelder-Mead Search  Nelder-Mead Search  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Nelder-Mead Search

(c) John H. Mathews 2004