# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 6 Convergence of the Simplex Sequences
Since both \(\tilde{\mathcal{T}}\) and \(\mathcal{T}\) are finite sets, there exist two constants \(\gamma_{b},\gamma_{C}>0\) such that \(\left\|b(T)\right\|\leq\gamma_{b}\) and \(\left\|C(T)\right\|\leq\gamma_{C}\) for all \(T\in\tilde{\mathcal{T}}\) or \(T\in\mathcal{T}\). For \(T_{j}(\alpha)\in\tilde{\mathcal{T}}\), the corresponding \(C\left(T_{j}(\alpha)\right)\) has \(n-1\) eigenvalues of \(\lambda=1\) and \(\left\|C\left(T_{j}(\alpha)\right)\right\|\geq 1\). For \(T(\alpha)P_{j}\in\mathcal{T}\) (\(j>2\)), \(\left\|C\left(T(\alpha)P_{j}\right)\right\|\geq 1\). However, for \(T(\alpha)P_{j}\in\mathcal{T}\) with \(\left|\alpha\right|<1\) and \(j=1,2\), the corresponding \(C\left(T(\alpha)P_{j}\right)\)s have all their eigenvalues in the open unit disk (see Theorem 1). Hence, they can be elements of an RCP set. If  
\[A_{i}=\left[ \begin{array}{cc}1&0\\ b_{i}&C_{i}\end{array} \right]\in\mathbb{R}^{(n+1)\times(n+1)}\quad(C_{i}\in \mathbb{R}^{n\times n},\;i\geq 1), \tag{25}\]  
then  
\[L_{k}=\prod_{i=1}^{k}A_{i}=\left[ \begin{array}{cc}1&0\\ \sum_{i=1}^{k}\left(\prod_{j=1}^{i-1}C_{j}\right)b_{i}&\prod_{i=1}^{k}C_{i} \end{array} \right]=\left[ \begin{array}{cc}1&0\\ x_{k}&\prod_{j=1}^{k}C_{i}\end{array} \right]. \tag{26}\]  
If the infinite matrix product \(\prod_{i=1}^{\infty}T_{i}\) (\(T_{i}\in\mathcal{T}\) (\(i\geq 1\)) or \(T\in\widetilde{\mathcal{T}}\) (\(i\geq 1\))) converges to a rank-one matrix of the form \(we^{T}\), that is, if \(\prod_{i=1}^{k}T_{i}\to we^{T}\) (\(w^{T}=\left[w_{1},\widehat{w}^{T}\right]\), \(\widehat{w}\in\mathbb{R}^{n}\)), then it follows that  
\[\prod_{i=1}^{k}\left[ \begin{array}{cc}1&0\\ b(T_{i})&C(T_{i})\end{array} \right]\to F^{-1}we^{T}F=\left[ \begin{array}{ cc}e^{T}w&0\\ \widehat{w}&0_{n\times n}\end{array} \right]. \tag{27}\]  
For the convergence of the simplex sequence to a common point, it is necessary and sufficient that both  
\[\prod_{i=1}^{k}C(T_{i})\to 0\quad(k\to\infty) \tag{28}\]  
and  
\[\sum_{i=1}^{k}\left(\prod_{j=1}^{i-1}C(T_{j})\right)b(T_{i})\to\widetilde{x} \quad(k\to\infty) \tag{29}\]  
hold for some vector \(\widetilde{x}\). It is clear that the infinite products of \(\mathcal{M}_{1}\) or \(\mathcal{M}_{2}\) satisfy these conditions. We recall the following simple result. [[14; 15; 16]] Assume that \(\left\|\prod_{j=1}^{k}C_{j}\right\|\leq c_{k}\), \(\sum_{k=1}^{\infty}c_{k}\) is convergent (\(<\infty\)) and that \(\left\|b_{k}\right\|\leq\gamma\) for all \(k\). Then, \(L_{k}=\prod_{j=1}^{k}A_{j}\) converges and  
\[\lim_{k\to\infty}L_{k}=\left[ \begin{array}{cc}1&0\\ \widetilde{x}&0\end{array} \right] \tag{30}\]  
for some \(\widetilde{x}\). If \(\left\|C_{i}\right\|\leq q<1\) for all \(i\), then the speed of convergence is linear (geometric). This follows from \(\left\|\prod_{i=1}^{k}C_{i}\right\|\leq q^{k}\) and the inequality  
\[\left\|\widetilde{x}-x_{k}\right\|\leq\gamma\sum_{i=k+1}^{m}\left\|\prod_{j=1} ^{i-1}C_{i}\right\|\leq\gamma\frac{q^{k}}{1-q}\quad(m>k)\]  
with \(m\to\infty\). We recall the following result (see [PERSON] [31], Corollary 6.4, [PERSON] and [PERSON] [34]). Let \(\mathcal{M}\) be a compact matrix set. Then, every infinite product, taken from \(\mathcal{M}\), converges to \(0\) if there is a norm \(\left\|\cdot\right\|\) such that \(\left\|A\right\|\leq q\), \(q<1\), for all \(A\in\mathcal{M}\). Hence, there must be a norm \(\left\|\cdot\right\|\) such that \(\left\|C_{i}\right\|\leq q<1\), for all \(T_{str}P_{j}\) (or \(T_{j}^{str}\)). Note that Lemma 4.2 is not constructive. However, for the convergence of \(\prod_{i=1}^{\infty}T_{i}\to we^{T}\) (for all \(T_{i}\in\mathcal{M}\)), the condition \(\left\|C(T_{i})\right\|\leq q<1\) (\(T_{i}\in\mathcal{M}\)) is necessary and sufficient. For Algorithm 1, \(\mathcal{M}_{1}\) is the only subset that satisfies this requirement.