Problem

Sometimes the multidimensional function is so difficult to evaluate that even expressing the derivative for gradient-based methods of finding optimum becomes an impossible task. In this case, we can only rely on the values of the function at each point. Or, in other words, on the order oracle calls.

Let’s take, for instance, Mishra’s Bird function:

This function is usually subjected to the domain , but for the sake of picture beauty we will mainly use domain .

Algorithm

  • – polytope with the least possible number of vertices in -dimensional space. (So, it’s -polytope.) In our case it will be triangle.
  • – vertex of the simplex, function value in which is the smallest among all vertices.
  • – vertex of the simplex, function value in which is the largest among all vertices.
  • – vertices of the simplex, ordered in such way that . This implies that are best points in relation to and are worst points in relation to .
  • – center of mass in the polytope. In Nelder-Mead the centroid is calculated for the polytope, constituted by best vertices. In our case it will be the center of the triangle side, which contains best points .

Main idea

The algorithm maintains the set of test points in the form of simplex. For each point the function value is calculated and points are ordered accordingly. Depending on those values, the simplex exchanges the worst point of the set for the new one, which is closer to the local minimum. In some sense, the simplex is crawling to the minimal value in the domain.

The simplex movements finish when its sides become too small (termination condition by sides) or its area becomes too small (termination condition by area). I prefer the second condition, because it takes into account cases when simplex becomes degenerate (three or more vertices on one axis).

Steps of the algorithm

1. Ordering

Order vertices according to values in them:

Check the termination condition. Possible exit with solution .

2. Centroid calculation

3. Reflection

Calculate the reflected point :

where – reflection coefficient, . (If , reflected point will not overlap the centroid)

The next step is figured out according to the value of in dependency to values in points (best) and (second worst):

  • : Go to step .
  • : new simplex with . Go to step .
  • : Go to step .

4. Expansion

Calculate the expanded point :

where – expansion coefficient, . (If , expanded point will be contracted towards centroid, if : )

The next step is figured out according to the ratio between and :

  • : new simplex with . Go to step .
  • : new simplex with . Go to step .

5. Contraction

Calculate the contracted point :

where – contraction coefficient, . (If , contraction is insufficient, if , contracted point overlaps the centroid)

The next step is figured out according to the ratio between and :

  • : new simplex with . Go to step .
  • : Go to step .

6. Shrinkage

Replace all points of simplex with new ones, except for the best point :

where – shrinkage coefficient, . (If , shrinked point overlaps the best point , if , shrinked point becomes extended)

Go to step .

Examples

This algorithm, as any method in global optimization, is highly dependable on the initial coonditions. For instance, if we use different initial simplex or different set of parameters the resulting optimal point will differ.

Some random initial simplex and default set of parameters

Different initial simplex and same set of parameters

Same initial simplex and different set of parameters

Round domain

Examples with all sets of simplexes

Code

Open In Colab