Talk:Nelder–Mead method

Engineers use optimization to build bridges...

The second paragraph in the overview reads: "For example, a suspension bridge engineer has to choose how thick each strut, cable, and pier must be. These elements are interdependent, but it is not easy to visualize the impact of changing any specific element. The engineer can use the Nelder–Mead method to generate trial designs which are then tested on a large computer model. As each run of the simulation is expensive, it is important to make good decisions about where to look."

I would suggest this paragraph be removed or moved to the article on general optimization. It seems a broad and somewhat trivial observation about why engineers use optimization as you would find in a child's science book. It has nothing to do with Nelder-Mead (you can replace the term Nelder-Mead with any optimization technique in this paragraph). — Preceding unsigned comment added by 24.6.87.223 (talk) 01:24, 18 April 2013 (UTC)

I think this analogy is actually pretty good, the Nelder-Mead method only requires about 2 function evaluations per iteration which is why it was chosen. Many of the other optimization methods require a large number of function evaluations. This paragraph is most likely referring to this particular property. Though I agree that this is not immediately clear that this is what they are attempting to indicate. I've made some changes to it, tell me what you think. KillerGardevoir (talk) 06:31, 5 July 2014 (UTC)

At least it is short. I was more concerned with the implication that the NM method was efficient.nashjc (talk) 20:45, 3 November 2017 (UTC)

Formal algorithm summary needs double-checking

 I did a fairly quick check against the original NM paper and it seems more or less OK. I will try to give a more thorough check in next week or so. References added. nashjc (talk) 20:18, 3 November 2017 (UTC)

The description under "One possible variation of the NM algorithm" needs some rework I think. It should be checked against the algorithm description in Nelder and Mead's original paper or if that's not to hand against McKinnon's paper. I'm not convinced the current description is correct.

The notation $f({\textbf {x}}_{i})$ is clumsy. It would be clearer to introduce something like $f_{i}$.

Step 5, "shrink step", has an incoherent description

The section should then be retitled to reflect the aim as a definitive formal statement.

The structure of the algorithm is not as clearly spelled out as it could be. —Preceding unsigned comment added by 212.13.197.229 (talk) 11:42, 30 December 2007 (UTC)

I am implementing (2008.01.25) this summary in LabVIEW. So far I've noticed :

1. There is no definition on what if f(xr) == f(x1)

2. What does it mean to "compute new simplex with x" ? Does it mean replacing worst vertex with x ? Or computing new simplex using x as a "starting" vertex ?

—Preceding unsigned comment added by Kupsztal (talk) 10:05, 25 January 2008 (GMT)

The "One possible variation" section is obviously incorrect. With the suggested alpha value of 1.0, step 2 (reflection) would always yield points at the center of mass. This section should be marked incorrect/suspect to avoid confusion by readers. —Preceding unsigned comment added by Joshaller (talk • contribs) 23:51, 21 February 2008 (UTC)

It is adding coordinates (centroid - highest) to centroid, is it not, which reflects highest through centroid?nashjc (talk) 20:50, 3 November 2017 (UTC)

reflected through the remaining N points considered as a plane

"The simplest step is to replace the worst point with a point reflected through the remaining N points considered as a plane."

I think this might be misleading or wrong. All implementations of this I've seen so far do reflect the worst point at the center of the remaining N points and not at the (hyper-)plane. Reflecting at the center is like New=Center-(Worst-Center), while reflecting at the plane would be like moving it along the plane's normal. But since I'm no expert in this field, I don't want to correct this myself. --88.73.211.225 23:33, 8 March 2007 (UTC)

Thanks. I'm no expert either, but the web pages and articles I consulted agree. So I made the correction. -- Jitse Niesen (talk) 11:49, 10 March 2007 (UTC)

Parameter choice

If gamma = 1/2 then the expansion step is shorter than the reflection step. Should not gamma be greater than 1 with the current formulation of the algorithm? It seems rho and gamma should be switched in the algorithm. —Preceding unsigned comment added by 129.240.228.53 (talk) 12:09, 25 June 2008 (UTC)

Description of the Algorithm

A terse description of the algorithm might be:

Have initial simpex

Loop

Identify best, second worst, worst point of current simplex

Calculate reflected point

if best <= reflected < second worst then

replace worst by reflected

else if reflected < best then

calculate expanded point

if expanded < reflected then

replace worst by expanded

else

replace worst by reflected

else

calculate contracted point

if contracted < reflected then

replace worst by contracted

else

shrink all but best towards best

until algorithm converged

-- Schewek (talk) 14:41, 24 March 2009 (UTC)

The article is rather vague on the criteria for contraction and shrink so the talk above is a welcome clarification. However the preceding condition "if best <= reflected < second worst then" seems strange why second worst and not worst? If the reflected point is best the expanded point should be calculculated, if the reflected point is better than the worst it should be kept. — Preceding unsigned comment added by 150.227.15.253 (talk) 10:21, 28 August 2019 (UTC)

The algorithm above does not express the one I use and published in Compact Numerical Methods in 1979. In the case reflected < second worst, we want to contract on the "reflection" side of the centroid, while otherwise the contraction is on the "worst" side of the centroid. The expression above does not have the contraction operation following the replacement of worst by reflected in this case. However, at this moment, I am reluctant to try an edit that will not be carefully checked and tested. nashjc (talk) 12:35, 28 August 2019 (UTC)

General Comments

1. Sometimes, this is a "downhill" method and sometimes, we're talking about the "steepest ascent".
2. This might be easier to read if the original Nelder-Mead method were discussed in full first, then variants were discussed (perhaps even on a separate page).

-- Confluente (talk) 20:07, 17 October 2009 (UTC)

NM modified to handle constrained optimization

1. Initialization. An initial N + 1 vertex points are randomly generated in their respective search range or space. Evaluate fitness of the objective function and the constraint fitness at each vertex point of the simplex. 2. Reflection. Determine Xhigh and Xlow, vertices with the highest and the lowest function values, respectively. Let fhigh, flow and Cfhigh, Cflow represent the corresponding observed function values and constraint function values, respectively. Find xcent, the center of the simplex without xhigh in the minimization case. Generate a new vertex xrefl by reflecting the worst point according to the following equation: equation(9) xrefl=(1+α)xcent-αxhigh(α>0)xrefl=(1+α)xcent-αxhigh(α>0) Nelder and Mead suggested that α = 1. If Cfrefl < 1 and Cfrefl > Cflow or Cfrefl = 1 and frefl < flow then proceed with expansion; otherwise proceed with contraction. 3. Expansion. After reflection, two possible expansion cases need to be considered, as described below: 3.1 If Cfrefl < 1 and Cfrefl > Cflow, the simplex is expanded in order to extend the search space in the same direction and the expansion point is calculated by the following equation: equation(10) xexp=γxrefl+(1-γ)xcent(γ>1)xexp=γxrefl+(1-γ)xcent(γ>1) Nelder and Mead suggested γ=2. If Cfexp > Cflow or Cfexp = 1, the expansion is accepted by replacing xhigh with xexp; otherwise, xrefl replaces xhigh. 3.2 If Cfrefl = 1 and frefl < flow, the expansion point is calculated by Eq. (10). If Cfexp = 1 and fexp < flow, the expansion is accepted by replacing xhigh with xexp; otherwise, xrefl replaces xhigh. 3.3 Exit the algorithm if the stopping criteria are satisfied; otherwise go to step 2. 4. Contraction. After reflection, there are two possible contraction cases to consider: 4.1 If Cfrefl < 1 and Cfrefl ⩽ Cflow, the contraction vertex is calculated by the following equation: equation(11) xcont=βxhigh+(1-β)xcent(0<β<1)xcont=βxhigh+(1-β)xcent(0<β<1) Nelder and Mead suggested β = 0.5. If Cfcont > Cflow or Cfcont = 1, the contraction is accepted by replacing xhigh with xcont; otherwise do shrinking in step 5.1. 4.2 If Cfrefl = 1 and frefl ⩾ flow, and if frefl ⩽ fhigh, then xrefl replaces xhigh and contraction by Eq. (11) is carried out. If frefl > fhigh, then direct contraction without the replacement of xhigh by xrefl is performed. If Cfcont = 1 and fcont < flow, the contraction is accepted by replacing xhigh with xcont; otherwise do shrinking in step 5.2. 4.3 Exit the algorithm if the stopping criteria are satisfied; otherwise go to step 2. 5. Shrinkage. 5.1 Following step 4.1 in which Cfcont ⩽ Cflow and contraction has failed, shrinkage attempts to all points except xlow by the following equation: equation(12)

xi←δxi+(1-δ)xlow(0<δ<1) Nelder and Mead suggested δ = 0.5. 5.2 Contraction has failed in step 4.2 where Cfcont < 1 or Cfcont = 1 but fcont ⩾ flow. Shrink the entire simplex except xlow by Eq. (12). 5.3 Exit the algorithm if the stopping criteria are satisfied; otherwise go to step 2. — Preceding unsigned comment added by 123.15.57.226 (talk) 15:27, 17 August 2013 (UTC)