Nelder and Mead Algorithm

218 views (last 30 days)
Farah Shahpoor
Farah Shahpoor on 29 Nov 2019
Commented: Star Strider on 4 Dec 2019
Dear Community,
I want to find optimize coefficients of an equation to mininize a Langran function.
After searching in the internet I have found the Nelder Mead Algorithm. But I could not find a good explanation of it an an example for matlab.
Does any one know any example or good explanation?

Accepted Answer

Star Strider
Star Strider on 29 Nov 2019
According to the documentation section on the fminsearch Algorithm, the fminsearch function should do what you want.
  13 Comments
Farah Shahpoor
Farah Shahpoor on 4 Dec 2019
for this one :
function b = three_var(v)
x = v(1);
y = v(2);
z = v(3);
b = x.^2 + 2.5*sin(y) - z^2*x^2*y^2;
Now find a minimum for this function using x = -0.6, y = -1.2, and z = 0.135 as the starting values.
v = [-0.6,-1.2,0.135];
a = fminsearch(@three_var,v)
a =
0.0000 -1.5708 0.1803
Star Strider
Star Strider on 4 Dec 2019
The results depend on how you formulate the problem:
v = [-0.6,-1.2,0.135];
[a1,fv1] = fminsearch(@three_var,v)
[a2,fv2] = fminsearch(@(x)norm(three_var(x)),v)
producing:
a1 =
0.000020982252460 -1.570815942930068 0.180302592223391
fv1 =
-2.499999999114069
a2 =
-0.874045104467587 -0.309715028675296 0.161488717409484
fv2 =
7.568378373129557e-05
The first fminsearch call returns the minimum of the function, the second looks for the minimum that is greater than zero. It depends on what you want.

Sign in to comment.

More Answers (1)

John D'Errico
John D'Errico on 29 Nov 2019
Edited: John D'Errico on 29 Nov 2019
I'm trying to be retired from Answers, but having glanced in, I see this question, one which I am pretty well qualified to answer, despite not having written a Nelder-Mead code for perhaps 30 years. By the way, it is often called Nelder-Mead polytope, as opposed to the word simplex to distinguish it from the classical Simplex method for linear programming, which it is not.
It is implemented in MATLAB as fminsearch. I've also posted fminsearchbnd on the file exchange, which implements bound constraints in this contex, still using fminsearch.
Do you really need a complete explanation? Surely you can find that online. Wikipedia will have quite a good explanation I am sure...
The basic idea is trivial though. You maintain a set of points, thus n+1 points in n-dimensions. This is where the names simplex and polytope are derived.
Evaluate the objective at each vertex of the polytope. Pick the WORST point from that set, and discard it. This will leave you with an n-simplex in n dimensions. Given the point you have just discarded, reflect that point through the centroid of the remaining n points, to create a new full volume polytope. Evaluate the new point in your function. (Note that you don't want to move towards goodness, but move away from badness. The former tends to generate a polytope that becomes degenerate, thus one with zero volume. That is a generally a bad thing, and can cause the optimization to fail.).
Repeat the above steps. If the next point you will want to discard happens to be the last point you just created via reflection, then you need to contract your simplex, as otherwise an infinite loop will arise, with each point reflecting to the last point you saw. (There are several ways contraction can happen, as I recall.) Contraction is of course necessary when you get near the final objective. As well, there are circumstances where you want to enlarge the simplex. This helps the simplex to move faster towards the goal where necessary.
Convergence occurs when all points of a current polytope are close to each other in value, and when no progress is seen.
A common thing to do before termination is allowed is to create a new, simplex around the final best point. See if that simplex can move you further towards the goal. Known as a restart, this is an attempt to alleviate problems with degeneracy of the simplex.
That is the basic idea. There are various subtly different implementations of the general ideas above.
There are positive and negative aspects of Nelder-Mead, as you should expect. First, people tend to overuse it, on problems with far too many dimensions. As a search method, it simply is not efficient in a high number of dimensions (the curse of dimensionality.) High in this context is probably more than around 8-10 dimensions. If you are hoping to use Nelder-Mead on a problem with many dozens of unknowns, hundreds or more, you are just wasting your time and CPU cycles on it. There are far better methods aavilable for large problems. Find them in the optimization toolbox as a starting point. You might also look at the global optimization toolbox.
Single variable problms can be solved using Nelder-Mead, however, there are far better schemes available in MATLAB for the 1-d case, with fminbnd often being the method of choice.
Nelder-Mead is NOT a gradient based method. This can be a virtue, in that it does not require derivatives, or even a method to estimate the gradient using finite differences. That does not mean it will work on highly discontinuous or non-differentiable problems. It will probably fail there, as much as any other method. However the lack of a gradient can allow it to be a bit more robust to some simple problems. Nelder-Mead is NOT a method that can be used on integer problems.
Final convergence for Nelder-Mead tends to be slow, as it needs to contract the simplex to make it smaller, requiring multiple new function evals each time. The is distinguished from many better methods, where they tend to be quadratically convergent near the solution. That is not the case for Melder-Mead.
Nelder-mead is a REASONABLE scheme for small problems, in 2-5 (or so) dimensions. Keep it there, and you will often be happy with the results.

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!