# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 3 Matrix Representations for the Two Algorithms  
The steps of both algorithms can be easily described by transformation matrices. We first consider Algorithm 1. If the incoming vertex \(v=x^{(k)}(\alpha_{k})\) (\(\alpha_{k}\in\left\{\pm\frac{1}{2},1,2\right\}\)) belongs to \(\left\{x_{r}^{(k)},x_{e}^{(k)},x_{oc}^{(k)},x_{ic}^{(k)}\right\}\), then  
\[S^{(k+1)}=\left[x_{1}^{(k)},\ldots,x_{h_{k}-1}^{(k)},v,x_{h_{k}+1}^{  
where \(e_{j}\) is the \(j\)-th unit vector. Then, \(v=S^{(k)}c_{h_{k}}(\alpha_{k})\) and  
\[S^{(k+1)}=S^{(k)}T_{h_{k}}(\alpha_{k})\quad\Big{(}\alpha_{k}\in\left\{\pm\frac{1 }{2},1,2\right\}\Big{)}. \tag{7}\]  
The shrinking iteration can be written as  
\[S^{(k+1)}=S^{(k)}T^{sltr}_{\ell_{k}}\quad\Big{(}T^{sltr}_{\ell_{k}}=\frac{1}{2} I+\frac{1}{2}e_{\ell_{k}}e^{T}\Big{)}, \tag{8}\]  
where \(e=[1,1,\ldots,1]^{T}\). It follows that  
\[S^{(k+1)}=S^{(k)}T^{(k)}=S^{(0)}\prod_{i=0}^{k}T^{(i)}=S^{(0)}B_{k}\quad\Big{(} T^{(i)}\in\tilde{\mathcal{T}}\Big{)}, \tag{9}\]  
where  
\[\tilde{\mathcal{T}}=\bigg{\{}T_{\ell}(\alpha):1\leq\ell\leq n+1,\;\alpha=\pm \frac{1}{2},1,2\bigg{\}}\cup\Big{\{}T^{sltr}_{j}:1\leq j\leq n+1\Big{\}}. \tag{10}\]  
The set \(\tilde{\mathcal{T}}\) has exactly \(5(n+1)\) nonsingular matrices. Note that \(e^{T}T_{j}(\alpha)=e^{T}\) and \(e^{T}T^{sltr}_{\ell_{k}}=e^{T}\).  
For Algorithm 2, we have the following (see, e.g., [14; 15]). Assume that simplex \(S^{(k)}\) satisfies condition (4). Then, for nonshrinking iterations, the new simplex is given by  
\[S^{(k+1)}=S^{(k)}T(\alpha)P_{j^{(k)}}\quad(\alpha\in\left\{\pm\frac{1}{2},1,2 \right\}), \tag{11}\]  
where  
\[T(\alpha)=\left[\begin{array}{cc}I_{n}&\frac{1+n}{n}e\\ 0&-\alpha\end{array}\right]\in\mathbb{R}^{(n+1)\times(n+1)} \tag{12}\]  
and  
\[P_{j}=\big{[}e_{1},\ldots,e_{j-1},e_{n+1},e_{j},\ldots,e_{n}\big{]}\in\mathbb{ R}^{(n+1)\times(n+1)}\quad(j=1,\ldots,n+1) \tag{13}\]  
is a permutation matrix. If shrinking occurs, the new simplex is  
\[S^{(k+1)}=S^{(k)}T_{sltr}P\quad\Big{(}T_{sltr}=\frac{1}{2}I_{n+1}+\frac{1}{2} e_{1}e^{T}\Big{)},\]  
where the permutation matrix \(P\in\mathcal{P}_{n+1}\) is defined by the ordering condition (4) and \(\mathcal{P}_{n+1}\) is the set of all possible permutation matrices of order \(n+1\).  
Define the sets  
\[\mathcal{T}_{1}=\bigg{\{}T(\alpha)P_{j}:\alpha\in\left\{-\frac{1}{2},\frac{1}{ 2}\right\},\;j=1,\ldots,n+1\bigg{\}},\]  
\[\mathcal{T}_{2}=\big{\{}T(1)P_{j}:j=1,\ldots,n\big{\}}\cup\{T(2)P_{1}\},\quad \mathcal{T}_{3}=\{T_{sltr}P:P\in\mathcal{P}_{n+1}\}\]  
and  
\[\mathcal{T}=\mathcal{T}_{1}\cup\mathcal{T}_{2}\cup\mathcal{T}_{3}. \tag{14}\]  
It follows that  
\[S^{(k+1)}=S^{(k)}T_{k}P^{(k)}=S^{(0)}\prod_{i=0}^{k}T_{i}P^{(i)}=S^{(0)}B_{k} \quad\Big{(}T_{i}P^{(i)}\in\mathcal{T},k\geq 1\Big{)}, \tag{15}\]  
where  
\[B_{k}=\prod_{i=0}^{k}T_{i}P^{(i)}\quad\Big{(}T_{i}P^{(i)}\in\mathcal{T}\Big{)}. \tag{16}\]The set \(\mathcal{T}\) consists of \(3n+3+(n+1)!\) nonsingular matrices. For any \(T_{i}P^{(i)}\in\mathcal{T},e^{T}T_{i}P^{(i)}=e^{T}\).  
Observe that both algorithms are nonstationary iterations. Note that the number of shrinking matrices for Algorithm 2 increased to \((n+1)!\) compared to the \(n+1\) shrinking matrices of Algorithm 1.