The Nelder-Mead Algorithm

What is the Nelder-Mead algorithm?

Different from random and grid search, the Nelder-Mead algorithm is a heuristic-based optimization that uses several heuristics to minimize the number of iterations required to reach the optimal solution. The algorithm has several names, like the downhill simplex method, amoeba method, and polytope. It is based on a simplex, which is a shape with $n+1$ vertices in an $n$-dimensional space—for example, a triangle represents a simplex in 2D space and a tetrahedron represents a simplex in 3D space.

At any point in time, the Nelder-Mead algorithm maintains a set of $n+1$ points in an $n$-dimensional space, i.e., a simplex. It then evaluates the objective on each of the vertices of the simplex (polytope) and updates the worst vertex with a newer one, resulting in a shrunk simplex. This process is repeated until some desired bound is obtained.

Let’s take searching for a house as an example, where the objective function $f(x)$ returns the price of a candidate house $x$ in a town. The task is to find the most competitive house (in terms of pricing) in the whole town. The Nelder-Mead algorithm will start with the three initial points (or house candidates) $u$, $v$, and $w$, forming a simplex in a 2D space. Here are the steps to complete this process:

1. Ordering the points: We order $u$, $v$, and $w$ according to their objective values (house prices). For example, if $f(u) \leq f(v) \leq f(w)$, we will call $u$ as the best point, $v$ as the second-best point, and $w$ as the worst point. In other words, the method evaluates the cost function at each house and orders them from the lowest to the highest cost. The house with the lowest cost is called the best point, and the house with the highest cost is called the worst point.

2. Calculating the centroid: We then calculate $c$, which represents the midpoint or centroid of the line segment connecting $u$ ...