# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 6 Convergence of the Simplex Sequences
For \(0<q<1\), define the sets  
\[\mathbb{T}_{q}^{\ell}=\Big{\{}T_{i_{1}}\cdots T_{i_{\ell}}\in\mathbb{T}^{\ell} :\left\|C\big{(}T_{i_{1}}\cdots T_{i_{\ell}}\big{)}\right\|\leq q\Big{\}}, \quad\mathbb{T}_{Q}^{\ell}=\mathbb{T}^{\ell}\setminus\mathbb{T}_{q}^{\ell}. \tag{34}\]For any \(\widehat{T}_{j}\in\mathbb{T}_{q}^{\ell}\), we have the estimates \(\left\|\widehat{b}_{j}\right\|\leq\widehat{\gamma}_{\widehat{b}}\) and \(\left\|\widehat{c}_{j}\right\|\leq q<1\). Hence, by Lemma 17, the set \(\mathbb{T}_{q}^{\ell}\) is an RCP set, and the limits of the infinite products \(\prod_{j=1}^{\infty}\widehat{T}_{j}\) are of the form \(we^{T}\). Now, consider the product  
\[\prod_{j=1}^{k}T_{i_{j}}=\prod_{j=1}^{m\ell+r}T_{i_{j}}=\left(\prod_{j=1}^{m \ell}T_{i_{j}}\right)\left(\prod_{\tau=m\ell+1}^{m\ell+r}T_{i_{\tau}}\right)= \left(\prod_{j=1}^{m}\widehat{T}_{j}\right)\left(\prod_{\tau=m\ell+1}^{m\ell+ r}T_{i_{\tau}}\right)\]  
where \(\widehat{T}_{j}\in\mathbb{T}_{q}^{\ell}\) (\(j=1,\ldots,m\)), \(T_{i_{\tau}}\in\mathbb{T}\) (\(\tau=m\ell+1,\ldots m\ell+r\)) and \(0\leq r<\ell\) are fixed (\(\ell\geq 1\)). The corresponding reduced form is  
\[F^{-1}\left(\prod_{j=1}^{k}T_{i_{j}}\right)F=\left[ \begin{array}{cc}1&0\\ x_{k}&\left(\prod_{j=1}^{m}\widehat{C}_{j}\right)\left(\prod_{\tau=m\ell+1}^{m \ell+r}C_{i_{\tau}}\right)\end{array} \right]\]  
Consider the product \(\prod_{j=1}^{n}\widehat{T}_{j}\) (\(\widehat{T}_{j}\in\mathbb{T}^{\ell}\)), where the number of factors \(\widehat{T}_{j}\) that belong to \(\mathbb{T}_{q}^{\ell}\) is \(r_{1}(m)\). Clearly, \(0\leq r_{1}(m)\leq m\). There exists a \(\kappa\in\mathbb{N}\) such that \(\frac{1}{q^{\ell-1}}\leq\widehat{\gamma}_{\mathbb{C}}\leq\frac{1}{q^{\ell}}\). Assume that there is a number \(\mu\in(0,1]\) such that \((1+\kappa)r_{1}(m)-\kappa m\geq\mu m\). Then,  
\[\left\|\left(\prod_{j=1}^{m}\widehat{C}_{j}\right)\left(\prod_{ \tau=m\ell+1}^{m\ell+r}C_{i_{\tau}}\right)\right\| \leq q^{r_{1}(m)}\hat{\gamma}_{\mathbb{C}}^{m-r_{1}(m)}\gamma_{ \mathbb{C}}^{r}\] \[\leq\gamma_{\mathbb{C}}^{\ell-1}q^{r_{1}(m)-\kappa(m-r_{1}(m))}= \gamma_{\mathbb{C}}^{\ell-1}q^{(1+\kappa)r_{1}(m)-\kappa m}\] \[\leq\gamma_{\mathbb{C}}^{\ell-1}q^{\mu m}\leq\gamma_{\mathbb{C}}^ {\ell-1}q^{\mu\left(\frac{k}{\ell}-1\right)}=\frac{1}{q}\gamma_{\mathbb{C}}^{ \ell-1}\Big{(}q^{\frac{\mu}{\ell}}\Big{)}^{k}.\]  
Since \(\widehat{q}=q^{\frac{\mu}{\ell}}<1\) and the conditions of Lemma 17 hold, we proved the following result. Theorem 5: _Assume that \(n\geq 2\), \(S^{(0)}\) is non-degenerate, \(\ell\geq 1\) is fixed and \(\mathbb{T}_{q}^{\ell}\) is not empty. Let \(r_{1}\Big{(}\left\lfloor\frac{k}{\ell}\right\rfloor\Big{)}\) be the number of \(\ell\) products that belong to \(\mathbb{T}_{q}^{\ell}\) during the first k iterations of the Nelder-Mead method (Algorithm 2). Moreover, assume that for an integer \(\kappa\in\mathbb{N}\), \(\frac{1}{q^{\kappa-1}}\leq\widehat{\gamma}_{\mathbb{C}}\leq\frac{1}{q^{\ell}}\) and for some \(\mu\in(0,1]\), \(r_{1}\Big{(}\left\lfloor\frac{k}{\ell}\right\rfloor\Big{)}\geq\frac{\mu+ \kappa}{1+\kappa}\left\lfloor\frac{k}{\ell}\right\rfloor\). Then, the Nelder-Mead method (Algorithm 2) converges in the sense that_  
\[\lim_{k\to\infty}x_{j}^{(k)}=\widehat{x}\quad(j=1,2,\ldots,n+1) \tag{35}\]  
_with a convergence speed proportional to \(Q\bigg{(}\Big{(}q^{\frac{\mu}{\ell}}\Big{)}^{k}\bigg{)}\)._  
Note that assumption \(r_{1}(m)\geq\frac{\mu+\kappa}{1+\kappa}m\), which is a density condition, yields an infinite number of factors from the set \(\mathbb{T}_{Q}^{\ell}\) as \(m\to\infty\). The larger the ratio \(\left|\mathbb{T}_{q}^{\ell}\right|/\left|\mathbb{T}^{\ell}\right|\), the wider the convergence set. Theorem 5 is clearly true for any pair of subsets \(\mathcal{W}^{\ell}\) and \(\mathcal{W}_{q}^{\ell}\) such that \(\emptyset\
eq\mathcal{W}_{q}^{\ell}\subset\mathcal{W}^{\ell}\) and \(\mathcal{W}\subseteq\mathbb{T}\).