# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 2 Two Versions of the Nelder-Mead Method  
We first define the original Nelder-Mead simplex method in the following form (see [1; 6; 22]). The simplex of iteration \(k\) is denoted by \(S^{(k)}=\left[x_{1}^{(k)},\ldots,x_{n+1}^{(k)}\right]\in\mathbb{R}^{n\times(n+ 1)}\), where \(x_{i}^{(k)}\) denotes vertex \(i\) of iteration \(k\). The function values at the vertices are denoted by \(f_{i}^{(k)}=f\Big{(}x_{i}^{(k)}\Big{)}\) (\(i=1,\ldots,n+1\)). We define the index of the worst vertex (\(h_{k}\)), the best vertex (\(\ell_{k}\)) and the second worst vertex (\(m_{k}\)) as follows:  
\[h_{k}:f_{h_{k}}^{(k)}=\max_{1\leq i\leq n+1}f\Big{(}x_{i}^{(k)}\Big{)},\quad \ell_{k}:f_{\ell_{k}}^{(k)}=\min_{1\leq i\leq n+1}f\Big{(}x_{i}^{(k)}\Big{)},\]  
\[m_{k}:f_{m_{k}}^{(k)}=\max_{1\leq i\leq n+1,\ i\
eq h_{k}}f\Big{(}x_{i}^{(k)} \Big{)}.\]  
Note that \(1\leq\ell_{k},m_{k},h_{k}\leq n+1\), and they are not necessarily unique. Define the center \(x_{c}^{(k)}\) and straight line \(x^{(k)}(\alpha)\) as follows:  
\[x_{c}^{(k)}=\frac{1}{n}\sum_{i=1,\ i\
eq h_{k}}^{n+1}x_{i}^{(k)},\quad x^{(k)} (\alpha)=(1+\alpha)x_{c}^{(k)}-\alpha x_{h_{k}}^{(k)},\]  
The reflection, expansion, outside and inside contraction points of simplex \(S^{(k)}\) are defined as  
\[x_{r}^{(k)}=x^{(k)}(1),\quad x_{e}^{(k)}=x^{(k)}(2),\quad x_{oc}^{(k)}=x^{(k) }\bigg{(}\frac{1}{2}\bigg{)},\quad x_{ic}^{(k)}=x^{(k)}\bigg{(}-\frac{1}{2} \bigg{)}.\]The corresponding function values are denoted by \(f_{r}^{(k)}=f\Big{(}x_{r}^{(k)}\Big{)}\), \(f_{e}^{(k)}=f\Big{(}x_{e}^{(k)}\Big{)}\), \(f_{oc}^{(k)}=f\Big{(}x_{oc}^{(k)}\Big{)}\) and \(f_{ic}^{(k)}=f\Big{(}x_{ic}^{(k)}\Big{)}\), respectively. The original Nelder-Mead simplex method is given by Algorithm 1. ```
Input: Set \(S^{(0)}\in\mathbb{R}^{n\times(n+1)}\) and \(k=0\). while\(k\geq 0\), do  Determine \(x_{h_{k}}^{(k)}\), \(x_{\ell_{k}}^{(k)}\), \(x_{m_{k}}^{(k)}\), \(f_{h_{k}}^{(k)}\), \(f_{\ell_{k}}^{(k)}\) and \(f_{m_{k}}^{(k)}\); /* 1 */ if\(f_{\ell_{k}}^{(k)}\leq f_{r}^{(k)}<f_{m_{k}}^{(k)}\)then /* Reflect */ \(x_{h_{k}}^{(k)}\gets x_{r}^{(k)}\), \(k=k+1\) and go to \(1\). if\(f_{r}^{(k)}<f_{\ell_{k}}^{(k)}\) and \(f_{e}^{(k)}<f_{r}^{(k)}\)then /* Expand */ \(x_{h_{k}}^{(k)}\gets x_{e}^{(k)}\), \(k=k+1\) and go to \(1\). ; else if\(f_{r}^{(k)}<f_{\ell_{k}}^{(k)}\) and \(f_{e}^{(k)}\geq f_{r}^{(k)}\)then /* Expand */ \(x_{h_{k}}^{(k)}\gets x_{r}^{(k)}\), \(k=k+1\) and go to \(1\). if\(f_{m_{k}}^{(k)}\leq f_{r}^{(k)}<f_{h_{k}}^{(k)}\) and \(f_{oc}^{(k)}\leq f_{r}^{(k)}\)then /* Contract outside */ \(x_{h_{k}}^{(k)}\gets x_{oc}^{(k)}\), \(k=k+1\) and go to \(1\). if\(f_{r}^{(k)}\geq f_{h_{k}}^{(k)}\) and \(f_{ic}^{(k)}<f_{h_{k}}^{(k)}\)then /* Contract inside */ \(x_{h_{k}}^{(k)}\gets x_{ic}^{(k)}\), \(k=k+1\) and go to \(1\). Evaluate \(f\) at the points /* Shrink */ \(x_{i}^{(k+1)}:=\Big{(}x_{i}^{(k)}+x_{\ell_{k}}^{(k)}\Big{)}/2\), \(i=1,2,\ldots,n+1\), \(k=k+1\);
```  
**Algorithm 1**Original Nelder-Mead algorithm. The \"decision boundaries\" are the same as in the ordered Nelder-Mead method of [PERSON] et al. (1998), which is given in Algorithm 2. Suppose that  
\[f\Big{(}x_{1}^{(0)}\Big{)}\leq f\Big{(}x_{2}^{(0)}\Big{)}\leq\cdots\leq f \Big{(}x_{n+1}^{(0)}\Big{)} \tag{1}\]  
holds for the initial simplex vertices and that this ordering is kept during the subsequent iterations. Here, \(\ell_{k}=1\), \(m_{k}=n\) and \(h_{k}=n+1\) for all \(k\). There are two rules of reindexing after each iteration. For a nonshrink step, \(x_{n+1}^{(k)}\) is replaced by a new point \(v\in\Big{\{}x_{r}^{(k)},x_{e}^{(k)},x_{oc}^{(k)},x_{ic}^{(k)}\Big{\}}\). The following cases are possible: \(f(v)<f_{1}^{(k)},f_{1}^{(k)}\leq f(v)<f_{n}^{(k)}\) and \(f_{n}^{(k)}\leq f(v)<f_{n+1}^{(k)}\). Define  
\[j^{(k)}=\left\{ \begin{array}{ll}1,&\text{if }f(v)<f_{1}^{(k)}\\ \Big{\{}j:f_{j-1}^{(k)}\leq f(v)<f_{j}^{(k)},2\leq j\leq n+1\Big{\}},&\text{ otherwise}\end{array} \right.. \tag{2}\]  
Then, the new simplex vertices are  
\[x_{i}^{(k+1)}=\left\{