Nelder and Mead Algorithm

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?

Answer 1

[Star Strider]

According to the documentation section on the fminsearch Algorithm, the fminsearch function should do what you want.

[Farah Shahpoor]

Thanks for your quick answer. I have checked the fminsearch Algorithm and could understand how it works. The diffference to my case is, that I have more equations depending on each other. I will show here:

delta_pi and delta_x are the coeffients of the function it to optimize.

The function that needs to be minimzed is the follwing:

I dont knwo how to connect that all.

[Star Strider]

My pleasure.

These are difference equations. The fminsearch function (and most other optimisation routines) simply require that the objective (or loss) function return a scalar result. So the number of equations is not relevant, however coding the loss function correctly is important.

They also require that the optimisation is with respect to a given set of parameters. I have no idea what those parameters are in your system.

I do not understand what you want to do. If ‘var’ refers to the statistical variance, and you want to minimise it, that may simply mean iterating until your system of equations converges on some value defined by minimal change from one iteration to the next. That likely does not require fminsearch, only an interation loop.

[Farah Shahpoor]

Thanks for your reply.

The parameters in my system are delta_pi and delta_x, because I want to optimize them. If its that what you asked.

I want to minimize the loss function with the optimized parameters delta_pi and delta_x.

[Farah Shahpoor]

you say the number of equations are not relevat just the coding of the loss function. So, thats what Iam thinking:

To try fminsearch, create a function two_var of two variables, delta_pi and delta_x

function L = two_var(v)

delta_pi = v(1);

delta_x = v(2);

L = var(\pi) + \frac{1}{2} var(x) + var(i);

Now find a minimum for this function using delta_pi= 1.5, y = 0.5 as the starting values.

v = [1,5,1];

a = fminsearch(@two_var,v)

Maybe this is completely wrong but I tried to adjust it to my case.

My question is: delta_pi and delta_x are not directly in L. They are just paramters of i. How does it work?

[Star Strider]

I do not understand what you are doing.

The ‘L’ assignment is not valid MATLAB code.

[Farah Shahpoor]

oh ok. I will change it to b then as in the example. I tried to do it as the example:

To try fminsearch, create a function three_var of three variables, x, y, and z.

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]

Your code is correct.

Are you having problems?

[Farah Shahpoor]

the second code I posted from mathworks I just wanted to say that I adjusted my code to the example from mathworks.

[Star Strider]

O.K. I was just wondering.

So apparently your code now works?

[Farah Shahpoor]

I tried both codes. I get the error message for both codes:

Not enough input arguments.

Error in fmin (line 11)

x = v(1);

[Star Strider]

What codes?

[Farah Shahpoor]

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]

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.

Answer 2

[John D'Errico]

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...

https://en.wikipedia.org/wiki/Nelder–Mead_method

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.