Thread: need help with downhill simplex algorithm

hi,

can anyone pls kindly explain to me, in layman terms, what the nonlinear regression algorithm known as downhill simplex is, and how it works? i have read through the explanations found in Numerical Recipes in C (2nd ed) and a few other references, but they are all saying the same thing: create a simplex with N+1 vertices in an N-dimensional space, and then use procedures such as reflections, expansions, etc to home in on a minimum. sadly, i do not understand what the algorithm does.

specifically:

1. say, the merit function that i want to minimize is of the form y(x) = A exp (x^2) + B cos(Cx) + Dx^0.4, where A-D are the model parameters that i want to optimize. is this considered a multi-dimensional problem, or a single-dimensional problem with multiple variables? i cant find a distinct differentiation between multivariable and multidimensional in my references

2. for the same model function above, what kind of a simplex am i supposed to form? what would the simplex represent in this case?

thanks for any help!

ps: apologies if this is not a suitable forum to post this thread

Originally Posted by bobb

1. say, the merit function that i want to minimize is of the form y(x) = A exp (x^2) + B cos(Cx) + Dx^0.4, where A-D are the model parameters that i want to optimize. is this considered a multi-dimensional problem, or a single-dimensional problem with multiple variables? i cant find a distinct differentiation between multivariable and multidimensional in my references

That is too vague, what are you trying to fit to what?

2. for the same model function above, what kind of a simplex am i supposed to form? what would the simplex represent in this case?

You do not need to worry about that, all you need is an initial solution, and an initial size and tolerance for convergence.

CB

hi captainblack,

1. i have a set of 8 data pairs, (x1, y1)...(x8,y8). i have to fit a model to these data. the actual model is very complicated, so i posted a sample model function, which is y(x) = A exp (x^2) + B cos(Cx) + Dx^0.4. there is only 1 dimension, and that is x; but there are 4 model parameters that i have to vary and find the values that give the best fit to the data points. my question is, is this considered a single-dimension or multidimension problem? i cannot find a clear-cut distinction between multidimensional and multivariable.

2. my reason for asking this question is that i would like to get a conceptual understanding of how this algorithm works. how is it that a problem of determining the global extremum of a function can be solved by defining a geometrical shape, and then manipulating that simplex to home in on the extremum? a short example, if you could, would be really great!

Originally Posted by bobb

hi captainblack,

1. i have a set of 8 data pairs, (x1, y1)...(x8,y8). i have to fit a model to these data. the actual model is very complicated, so i posted a sample model function, which is y(x) = A exp (x^2) + B cos(Cx) + Dx^0.4. there is only 1 dimension, and that is x; but there are 4 model parameters that i have to vary and find the values that give the best fit to the data points. my question is, is this considered a single-dimension or multidimension problem? i cannot find a clear-cut distinction between multidimensional and multivariable.

2. my reason for asking this question is that i would like to get a conceptual understanding of how this algorithm works. how is it that a problem of determining the global extremum of a function can be solved by defining a geometrical shape, and then manipulating that simplex to home in on the extremum? a short example, if you could, would be really great!

The objective or merit function is:



and and are the variables that the optisation is over.

The Nelder-Mead algorithm (to avoid confusion with that other simplex algorithm) works by evaluating the objective at the vertices on a simplex in where n is the number of variables in the objective. Based on the values at the vertices a new simplex is generated using the rules in the algorithm that hopefully moves the centroid of the simplex in the direction of decreasing objective value. If the objective does not decline after a set of manouvres the size on the simplex is reduced and the process continues. When a move is successful the size of the simplex step may increase to move faster in the same direction.

Effectivly what is going on is that the shape of the response surface is being explored around the current estimate and the algorithm moves the simplex in a good direction.

CB

CB