# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 6 Convergence of the Simplex Sequences  
Here, we study the convergence of the simplex sequence \(\left\{S^{(k)}\right\}\) generated by both Nelder-Mead methods. If \(S^{(k)}\to S^{\infty}=\left[x^{*}_{1},\ldots,x^{*}_{n+1}\right]\), then (provided that \(f\) is continuous)\(f_{i}^{(k)}\to f\big{(}x_{i}^{*}\big{)}\) for \(i=1,\ldots,n+1\) as \(k\to\infty\). The limit vertices \(x_{i}^{*}\) can be different (see, e.g., Examples 1 and 2 of [20]). Ideally, \(S^{(k)}\) should converge to some limit of the form \(S^{\infty}=[x^{*},\ldots,x^{*}]=x^{*}e^{T}\), where \(x^{*}\in\mathbb{R}^{n}\) is a stationary point of \(f\). [PERSON]'s example [19] and Example 3 of [15] show that \(x^{*}\) is not always a stationary point. If \(B_{k}\) converges to a rank one matrix of the form \(B^{\infty}=we^{T}\) (\(w\in\mathbb{R}^{n+1}\)), then \(S^{(k)}=S^{(0)}B_{k}\to S^{(0)}we^{T}=\widehat{x}e^{T}\) and diameter \(\left(S^{(k)}\right)\to 0\). There are several examples (see, e.g., [14; 15; 20; 21]), where the simplex sequence \(\left\{S^{(k)}\right\}\) converges to a limit \(S^{\infty}\) with diameter \(\left(S^{\infty}\right)>0\) and rank \(\left(S^{\infty}\right)\), rank\(\left(B^{\infty}\right)\geq 2\). The following necessary and sufficient result holds for both algorithms. Lemma 10: _Assume that \(S^{(0)}\) is non-degenerate (affinely independent). Then, \(\left\{S^{(k)}\right\}\) (generated by Algorithm 1 or 2) converges to some \(S^{\infty}\in\mathbb{R}^{n\times(n+1)}\) if and only if \(\left\{B_{k}\right\}\) converges to some \(B^{\infty}\)._  
Proof: In both cases \(S^{(k)}=S^{(0)}\prod_{i=0}^{k}X_{i}=S^{(0)}B_{k}\quad(X_{i}\in\mathbb{T})\), where \(\mathbb{T}=\widetilde{\mathcal{T}}\) (in case of Algorithm 1) or \(\mathbb{T}=\mathcal{T}\) (in case of Algorithm 2). If \(B_{k}\to B^{\infty}\), then \(S^{(k)}=S^{(0)}B_{k}\to S^{(0)}B^{\infty}:=S^{\infty}\). Since \(e^{T}B_{k}=e^{T}\), we have  
\[\left[ \begin{array}{c}e^{T}\\ S^{(k)}\end{array} \right]=\left[ \begin{array}{c}e^{T}\\ S^{(0)}\end{array} \right]B_{k}.\]  
By assumption, the first matrix on the right is invertible and so  
\[B_{k}=\left[ \begin{array}{c}e^{T}\\ S^{(0)}\end{array} \right]^{-1}\left[ \begin{array}{c}e^{T}\\ S^{(k)}\end{array} \right].\]  
If \(S^{(k)}\to S^{\infty}\), then  
\[B_{k}=\left[ \begin{array}{c}e^{T}\\ S^{(0)}\end{array} \right]^{-1}\!\!\left[ \begin{array}{c}e^{T}\\ S^{(k)}\end{array} \right]\to\left[ \begin{array}{c}e^{T}\\ S^{(0)}\end{array} \right]^{-1}\!\!\left[ \begin{array}{c}e^{T}\\ S^{\infty}\end{array} \right]=B^{\infty}.\]  
From now on, we assume that \(S^{(0)}\) is always non-degenerate (its columns are affinely independent). Lemma 10 is formally independent of \(f\). However, the decision mechanism of the NM algorithm determines the next simplex and the resulting matrix product. Certain configurations clearly cannot occur. Such is the case of strictly convex functions, when no shrinking can occur or \(T(1)P_{2}\) cannot be repeated in a sequence more than five times (for the case \(n=2\)). In general, it is hard to tell what sequences (products) are possible for a given \(f\). Lemma 11: _If \(B_{k}=\prod_{i=0}^{k}X_{i}\to B^{\infty}\) (\(X_{i}\in\mathbb{T}\), \(\mathbb{T}=\widetilde{\mathcal{T}}\) or \(\mathbb{T}=\mathcal{T}\)), then rank \(\left(B^{\infty}\right)\leq n\)._  
Proof: Assume that rank \(\left(B^{\infty}\right)=n+1\). Then, \(B^{\infty}\) is invertible. Since all of \(X_{i}\in\mathbb{T}\) is invertible, \(\lim_{k\to\infty}B_{k-1}^{-1}=\left(B^{\infty}\right)^{-1}\). As \(X_{k}=B_{k-1}^{-1}B_{k}\),  
\[\lim_{k\to\infty}X_{k}=\lim_{k\to\infty}\left(B_{k-1}^{-1}\right)\lim_{k\to \infty}\left(B_{k}\right)=\left(B^{\infty}\right)^{-1}\!\!B^{\infty}=I.\]  
Hence, \(X_{k}\to I\) is necessary for an invertible \(B^{\infty}\). Since \(\mathbb{T}=\widetilde{\mathcal{T}}\) or \(\mathbb{T}=\mathcal{T}\) is a finite set and its elements are different from \(I\), this cannot happen and rank \(\left(B^{\infty}\right)\leq n\).