Talk:Nelder-Mead algorithm

From Scholarpedia
Jump to: navigation, search



    I have changed the ndashs in the text (as in Nelder-Mead) by hyphens. I believe the ndash is only appropriate in intervals (such as in page numbers in the articles)... -- Nwerneck 22:02, 5 April 2008 (EDT)

    Vector notation

    Can I change the vectors to \(\vec{x}_n\) or \(\hat{x}_n\) instead of just \(x_n\)? I believe there might be some confusion, specially because there are also scalar quantities in the text (\(f_n\)). -- Nwerneck 22:02, 5 April 2008 (EDT)

    Reply: Rather not, \(x_n\) is actually a point, not a vector. A full explanation is given below in the next section. This notation is so common, including \(f_n\), that any change might cause even more confusion. If you really think a change is required, then use \(\hat{x}_n\).--Singersasa 15:00, 15 February 2009 (EST)

    User 1 (Assistant Editor): simplex definition

    The article defines a simplex as the convex hull of a number of vertices. Shouldn't it be the hull of a number of linearly independent vectors? (that end up being the vertices...) -- Nwerneck 21:41, 4 May 2008 (EDT)

    Reply: No. This is the difference between affine and vector spaces. An affine spaces contains both points and vectors. A pair of points determines a vector. The usual \({\mathbb R}^n\) can be viewed in both ways. In this case, the difference of points is a vector. So, you need 3 points (in general position) to determine a plane. These 3 point define only 2 linearly independent vectors (one point is taken as an origin). Generally, you need \(n + 1\) points, that define/determine \(n\) vectors, say \(x_1 - x_0, \ldots, x_n - x_0\), if \(x_0\) is taken as an origin. --Singersasa 14:52, 15 February 2009 (EST)

    Reviewer A

    In general this is a clear and correct article, but I have some changes to suggest.

    1. In the first sentence of the article, it should be stated explicitly that this method should not be confused with Dantzig's simplex method for linear programming, which is completely different.

    2. The line "like many other direct search methods" (near the beginning of the article) is not really accurate any more, since modern GPS-like methods do not use a simplex, but rather rely on a positive spanning set of directions. Hence I would omit the first clause and simply say "The Nelder-Mead method is...". It's true that early direct search methods tended to be based on simplices, but no longer.

    3. Just above the heading "The Nelder-Mead simplex algorithm" (on page 3) I would change the statement that Nelder-Mead is still the most popular direct search method in practice, unless there is some evidence for this. Matlab now includes GPS and MADS in its optimization toolbox, and they may well have become more popular. (I don't know.) I think it's unarguable that Nelder-Mead is *among* the most popular.

    4. In the third line following the heading "The Nelder-Mead simplex algorithm" (page 3), I suggest replacing the word "break" by "end".

    5. In the 4th line from the bottom of page 3, I think $h_k$ should be described as "a" stepsize rather than "the".

    6. Under "termination tests" (page 5), it seems misleading to say the the method *must* terminate, when it can generate an infinite sequence. I suggest saying "A practical implementation of the Nelder-Mead method must include a test that ensures termination in a finite amount of time. The termination test is often composed of three..."

    7. Right after "efficient implementation", it is confusing to say "slow shrink transformations", which seems to imply that there are fast shrink transformations. I would omit "slow".

     Also, it should be "there is overwhelming evidence" (remove "an").

    8. In the paragraph starting "a fairly simple efficiency analysis...", the third sentence also mentions "simple" and "efficient". I suggest starting with "An analysis of a single Nelder-Mead iteration by..." and leaving the third sentence as is.

    9. Soon after the heading "convergence", I think the phrase "simplex-based direct search methods" should be replaced by "direct search methods" for the reasons given above in point 2.

     In mentioning these convergence results, you should probably

    cite one of the recent papers by Audet and Dennis that have appeared in the SIAM Journal on Optimization.

    10. Starting in the sixth line from the bottom of page 6, the word "deliberately" should be omitted, since you are already saying "by design".

    11. Just before the first bullet on page 7, I would tone down the statement about "substantially faster", and say something like

     "For such problems, the method is often faster than other methods,

    especially those that require at least $n$ function evaluations per iteration".

     Popular implementations of GPS and MADS tend to be opportunistic,

    which means that in general they do not require $n$ function evaluations per iteration (which is relatively uncommon these days).

    12. The first bullet on page 7, the statement that the Nelder-Mead method beats most of its competitors in best-case performance similarly needs to be toned down significantly. I suggest something like "In many numerical tests, the Nelder-Mead method succeeds in obtaining a good reduction in the function value using a relatively small number of function evaluations".

    13. Once again, the statement near the end about "other simplex-based direct search methods" should refer simply to "direct search methods". It would be good to include a citation to one of the Audet-Dennis papers and one of the papers by Coope and Price.

    Reply: I hope that I have addressed all the points. I also added two new paragraphs, based on John Nelder's comments on the article. The first one is located after the shrink transformation and contains a quote from the original paper. The second one is subsection 3.4. Thank you for your comments.--Singersasa 14:31, 21 February 2009 (EST)

    Personal tools

    Focal areas