# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 6 Convergence of the Simplex Sequences
Hence, we must seek for subsets \(\mathcal{M}\) of \(\widetilde{\mathcal{T}}\) or \(\mathcal{T}\), which are RCPs. However, [PERSON] and [PERSON] [33] proved that the product boundedness of a finite matrix set \(\mathcal{M}\) is algorithmically undecidable and it remains undecidable even in the special case, when \(\mathcal{M}\) consists of only two matrices. Since product boundedness is a weaker property than the RCP from which it follows, and although it is algorithmically undecidable, it seems difficult to decide the RCP property in general. This might answer question (e) of [PERSON]. However, it is relatively easy to identify one particular RCP set. For both algorithms, the corresponding shrinking matrices form an RCP set. **Lemma 14**. : _Both \(\mathcal{M}_{1}=\left\{T_{j}^{shr}:1\leq j\leq n+1\right\}\) and \(\mathcal{M}_{2}=\left\{T_{shr}P:P\in\mathcal{P}_{n+1}\right\}\) are RCP sets._  
Proof. : By using induction on \(k\), we can prove that for \(k\geq 1\),  
\[\prod_{i=1}^{k}T_{j_{i}}^{shr}=\prod_{i=1}^{k}\left(\frac{1}{2}I+\frac{1}{2}e_{ j_{i}}e^{T}\right)=\frac{1}{2^{k}}I+\sum_{i=1}^{k}\frac{1}{2^{i}}e_{j_{i}}e^{T}\]  
and  
\[\prod_{i=1}^{k}T_{shr}P^{(j_{i})}=\prod_{i=1}^{k}\left(\frac{1}{2}I+\frac{1}{2 }e_{1}e^{T}\right)P^{(j_{i})}=\frac{1}{2^{k}}\prod_{i=1}^{k}P^{(j_{i})}+\sum_{ i=1}^{k}\frac{1}{2^{i}}e_{i_{i}}e^{T}\quad(\ell_{1}=1).\]  
For the last formula, note that if \(P\) is a permutation matrix, then \(e_{i}^{T}P=e^{T}\) and \(Pe_{i}=e_{j}\) for some \(j\). In element-wise partial ordering, \(T_{j}^{shr}\geq 0\) holds for \(j=1,\ldots,n+1\) and  
\[0\leq\prod_{i=1}^{k}T_{j_{i}}^{shr}=\frac{1}{2^{k}}I+\sum_{i=1}^{k}\frac{1}{2^ {i}}e_{j_{i}}e^{T}\leq ee^{T}.\]  
Here, \(\frac{1}{2^{k}}I\to 0\) as \(k\to\infty\), and the sequence \(\left\{\sum_{i=1}^{k}\frac{1}{2^{e}}e_{i}e^{T}\right\}_{k=1}^{\infty}\) is monotone increasing in component-wise partial ordering. Hence, \(\prod_{i=1}^{\infty}T_{j_{i}}^{shr}\) is convergent. We also have that \(0\leq\prod_{i=1}^{k}T_{shr}P^{(j_{i})}\leq ee^{T}\), \(\frac{1}{2^{k}}\prod_{i=1}^{k}P^{(j_{i})}\to 0\) as \(k\to\infty\), and \(\left\{\sum_{i=1}^{k}\frac{1}{2^{e}}e_{i}e^{T}\right\}_{k=1}^{\infty}\) is monotone increasing in partial ordering. Hence, \(\prod_{i=1}^{\infty}T_{shr}P^{(j_{i})}\) is convergent. **Remark 2**. : _Corollary 2 implies that \(E_{1}(T_{shr}P)=\left\{\lambda e^{T}:\lambda\in\mathbb{R}\right\}\) for all \(P\in\mathcal{P}_{n+1}\). If matrices \(T_{shr}P^{(j_{i})}\) (\(i=1,\ldots,m\)) occur infinitely often in the product \(\prod_{i=1}^{\infty}T_{shr}P^{(j_{i})}\) and \(\prod_{i=1}^{k}T_{shr}P^{(j_{i})}\to B^{\infty}\) (\(k\to\infty\)), then the nonzero rows of \(B^{\infty}\) belong to \(\cap_{i=1}^{m}E_{1}\left(T_{shr}P^{(j_{i})}\right)=\left\{\lambda e^{T}: \lambda\in\mathbb{R}\right\}\). Hence, \(\prod_{i=1}^{k}T_{shr}P^{(j_{i})}\to we^{T}\) for some \(w\). Lemma 1 implies that \(E_{1}\left(T_{j}^{shr}\right)=\left\{\lambda e^{T}:\lambda\in\mathbb{R}\right\}\) for all \(j=1,\ldots,n+1\). It also follows from the previous argument that \(\prod_{i=1}^{k}T_{j_{i}}^{shr}\to we^{T}\) for some \(w\)._  
The \(S^{(k)}\to\tilde{x}e^{T}\) for the infinitely repeated shrinking process also follows from [PERSON]'s intersection theorem. **Lemma 15**. : _Define the matrix_  
\[F=\left[ \begin{array}{cc}1&-e^{T}\\ 0&I_{n}\end{array} \right]\quad\left(F^{-1}=\left[ \begin{array}{cc}1&e^{T}\\ 0&I_{n}\end{array} \right]\right). \tag{23}\]  
_Then, for all \(T\in\mathbb{T}\) (\(\mathbb{T}=\mathcal{T}\) or \(\mathbb{T}=\tilde{\mathcal{T}}\)), the matrix \(F^{-1}TF\) has the common block lower triangular form_  
\[F^{-1}TF=\left[ \begin{array}{cc}1&0\\ b(T)&C(T)\end{array} \right], \tag{24}\]  
_where \(b(T)\in\mathbb{R}^{n}\) and \(C(T)\in\mathbb{R}^{n\times n}\)._  
The result was proved for \(T\in\mathcal{T}\) in [14,15]. The proof of case \(\tilde{\mathcal{T}}\) is similar.