Nelder Mead - 2-D Minimization

Background

Nelder Mead method, also called the amoeba or downhill simplex method, is a widely used numerical analysis method used to find the minimum or maximum of a given objective function. It is referred to as a direct search method since it is based on function comparison, and is often applied to nonlinear optimization problems.

The goal of this project was to develop in R a Nelder Mead 2-D Minimization algorithm

This project was required for one of my undergraduate courses.

Method

Inputs:

  1. f - function of two variables that you are trying to minimize

  2. P - a point in the plane

  3. Q - a second point in the plane

  4. R - a third point in the plane

  5. t - a user-defined tolerance

Outputs:

  1. X - a point in the plane that represents the approximate minimizer of the function

  2. Z - the approximation of the minimum of the function, Z = f(X)

The function, f, is a function of two variables, x and y. Also, there are three initial points: P, Q, and R, which are ordered pairs. We initialize the algorithm by labeling the initial points P, Q, and R as B, for “Best”; G, for “Good”; and W, for “Worst.” These labels satisfy the inequalities f(B)<= f(G) <= f(W).

Since the initial points are now labeled, we can now describe one iteration of the algorithm.

Algorithm

  1. Midpoint: Calculate the midpoint, M = (B+G) / 2

  2. Reflection: Calculate the reflection point R = 2M - W

  3. Expansion: If f(R) < f(B) (that is if R is better than B), calculate the expansion point E = 2R - M

  4. Acceptance: If f(B) <= f(R) < f(G) (that is, R is better than G but is not as good as B), the new triangle is given by the points B, G, and R. Relabel these.

  5. Outside Contraction: If f(G) < f(R) < f(W) (that is, R is better than W but is not as good as G), calculate the Outside Contraction Point C = M+R / 2 .

  6. Inside Contraction: If f(W) < f(R) (that is, R is worse than the worst point W), calculate the Inside Contraction Point CC = W+M / 2 .

When should we quit? We will stop the algorithm when the length of the longest side of the triangle is less than the user-defined tolerance. That is, Steps 1 through 6 above are inside a while loop. The function repeats this process until the exiting criterion is satisfied.

Program Demonstration