Description of the simplex method
Downhill simplex optimization is based on the Nelder-Mead method, otherwise known as the Nelder–Mead method, simplex method, amoeba method, or polytope method. It determines the minimum of a non-linear function of many variables without using derivatives. Thus, it can be used for non-differentiable functions. It was first described by Nelder and Mead (1965).
1. In the first step, we define n + 1 n-dimensional points (x0 , ... , xn), where n is the size of the parameter space of the optimized function f(x), such that the vectors x1 − x0, … , xn − x0, are linearly independent, and
f(x0) ≥ f(x1) ≥ ... ≥ f(xn).
The set of points is vectors is an n-dimensional simplex.
2. Then we define three points:
u = (Σ xi) / n
v = (1+α) u +α x0
w = (1-γ) v + γ u
where α > 0 and 1 > γ < 0 are Simplex parameters. Based on the values of f(u), f(v), and f(w), a new simplex is calculated according to the following rules:
- when f(v) < f(xn), then if f(w) < f(xn) then x0 = w, otherwise x0 = v,
- when f(v) ≥ f(xn) and f(v) ≤ f(x1), then x0 = v,
- when f(v) > f(x1), then if f(v) ≤ f(x1) x0 = v, furthermore w = βx0 + (1-β)u i and if f(w) ≤ f(x1), then x0 = w otherwise for i = 0, ..., n-1 xi = (xi+xn)/2..
Finally, we sort the points so that they satisfy f(x0) ≥ f(x1) ≥ ... ≥ f(xn), and we go to point 2. We finish the calculations when the difference f(x0) - f(xn) < tolerance or reached there will be an iteration limit.
Configuration
Configuration requires entering the simplex change coefficients, i.e. three parameters α, β, and γ, tolerance, maximum number of iterations, and a range of values for each coordinate. The following window is used to define parameters:
