Results 1 to 4 of 4

Math Help - need help with downhill simplex algorithm

  1. #1
    Newbie
    Joined
    Aug 2010
    From
    sweden
    Posts
    9

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by bobb View Post

    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2010
    From
    sweden
    Posts
    9
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by bobb View Post
    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:

    Ob(A,B,C,D)=\sum_i (y_i-f_{A,B,C,D}(x_i))^2

    and  A, B, C and  D 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  \mathbb{R}^n 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
    Last edited by CaptainBlack; September 2nd 2010 at 01:19 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simplex Algorithm help
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 5th 2010, 05:01 PM
  2. Simplex Algorithm problem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: May 15th 2010, 08:01 AM
  3. simplex algorithm
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: July 23rd 2008, 04:57 PM
  4. Simplex Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 3rd 2008, 11:40 AM
  5. Simplex Algorithm
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: April 29th 2008, 09:49 PM

Search Tags


/mathhelpforum @mathhelpforum