# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 5 Convergence of the Function Values at the Vertices
However, if at least for one \(j\
eq h_{k}\), \(f^{(k)}_{j}<f^{(k)}_{h_{k}}\) holds, then \(f^{(k)}_{c}\leq\frac{1}{n}\sum_{i=1,\,i\
eq h_{k}}^{n+1}f^{(k)}_{i}<f^{(k)}_{h _{k}}\) and \(f^{(k)}_{ic}<f^{(k)}_{h_{k}}\). In such a case, there is no shrinking._  
Assume that \(f:\mathbb{R}^{n}\to\mathbb{R}\) is bounded below and only a finite number of shrink operations occur. Then, we have finite numbers \(f^{*}_{i}\) such that \(f^{(k)}_{i}\to f^{*}_{i}\) as \(k\to\infty\), and each \(\left\{f^{(k)}_{i}\right\}\) is monotone decreasing (\(i=1,\ldots,n+1\)). The values \(f^{*}_{i}\) are unordered. However, there is permutation \(\{i_{1},i_{2},\ldots,i_{n+1}\}\) of the indices \(\{1,2,\ldots,n+1\}\) such that  
\[f^{*}_{i_{1}}\leq f^{*}_{i_{2}}\leq\cdots\leq f^{*}_{i_{n}}\leq f^{*}_{i_{n+1}}. \tag{22}\]  
**Lemma 9** (Algorithm 1). : _If \(f\) is convex and bounded below on \(\mathbb{R}^{n}\), then \(f^{*}_{i_{n}}=f^{*}_{i_{n+1}}\)._  
Proof. : Assume that \(f^{*}_{i_{n}}<f^{*}_{i_{n+1}}\). Lemma 6 and Remark 1 imply that for \(0<\varepsilon<f^{*}_{i_{n+1}}-f^{*}_{i_{n}}\), there exists an index \(K>0\) such that for \(k\geq K\),  
\[f^{*}_{i_{j}}\leq f^{(k)}_{i_{j}}\leq f^{*}_{i_{j}}+\varepsilon\quad(j=1,\ldots,n+1).\]  
Note that \(f^{*}_{i_{j}}\leq f^{(k)}_{i_{j}}\leq f^{*}_{i_{k}}+\varepsilon<f^{*}_{i_{n+1} }\leq f^{(k)}_{i_{n+1}}\) (\(j=1,\ldots,n\)). Hence, there cannot be shrinking, and only the worst vertex \(x^{(k)}_{i_{n+1}}\) can change for \(k\geq K\) (\(f(v)\geq f^{*}_{i_{n+1}}\)). Clearly, \(i_{n+1}=h_{k}\) for \(k\geq K\). If \(\alpha=1,2\), then \(f\Big{(}x^{(k)}_{r}\Big{)}<f^{(k)}_{m_{k}}\leq f^{*}_{i_{n}}\) by definition. Hence, only the cases \(\alpha=\pm\frac{1}{2}\) are possible. For simplicity, let \(\eta=i_{n+1}\). Then,  
\[S^{(k+1)}=S^{(k)}T_{\eta}(\alpha)\quad\bigg{(}\alpha\in\left\{-\frac{1}{2}, \frac{1}{2}\right\}\bigg{)}\]  
and  
\[S^{(K+j)}=S^{(K)}\prod_{i=1}^{j}T_{\eta}(\alpha_{i})\quad\bigg{(}\alpha_{i}\in \left\{-\frac{1}{2},\frac{1}{2}\right\}\bigg{)}.\]  
Since \(T_{j}(\alpha)T_{j}(\beta)=T_{j}(-\alpha\beta)\) (\(j=1,\ldots,n+1\)), it follows that  
\[\prod_{i=1}^{j}T_{\eta}(\alpha_{i})=T_{\eta}\Bigg{(}(-1)^{j+1}\prod_{i=1}^{j} \alpha_{i}\Bigg{)}\to T_{\eta}(0)=\left[ \begin{array}{ccc}I_{\eta-1}&\frac{1 }{n}e&0\\ 0&0&0\\ 0&\frac{1}{n}e&I_{n+1-\eta}\end{array} \right],\]  
\[S^{(K+j)}\to S^{(K)}\Bigg{[} \begin{array}{ccc}I_{\eta-1}&\frac{1}{n}e&0\\ 0&0&0\\ 0&\frac{1}{n}e&I_{n+1-\eta}\end{array} \Bigg{]}=S^{*}\]  
and  
\[x^{(k)}_{i_{n+1}}\to x^{*}_{i_{n+1}}=\frac{1}{n}\sum_{j=1,\,j\
eq\eta}^{n+1}x^{ (K)}_{j}=\frac{1}{n}\sum_{j=1}^{n}x^{(K)}_{i_{j}}.\]Since \(f\) is convex, we have  
\[f^{*}_{i_{n+1}}=f\Big{(}x^{*}_{i_{n+1}}\Big{)}=f\Bigg{(}\frac{1}{n}\sum_{j=1}^{n}x ^{(K)}_{i_{j}}\Bigg{)}\leq\frac{1}{n}\sum_{i=1}^{n}f^{(K)}_{i_{j}}<f^{*}_{i_{n+1 }},\]  
which is a contradiction. Hence, \(f^{*}_{i_{n}}=f^{*}_{i_{n+1}}\) holds under convexity. Theorem 4: _If \(f\) is convex and bounded below on \(\mathbb{R}^{2}\), then Algorithm 1 converges in the sense that \(f^{*}_{1}=f^{*}_{2}=f^{*}_{3}\)._  
Proof: Lemmas 6 and 9 imply that \(f^{*}_{i_{1}}\leq f^{*}_{i_{2}}=f^{*}_{i_{3}}\) for some permutation \(i_{1},i_{2},i_{3}\) of \(\{1,2,3\}\). Assume that \(f^{*}_{i_{1}}<f^{*}_{i_{2}}\). Then, there exists an index \(K\) such that for \(k\geq K\), \(f^{*}_{i_{1}}\leq f^{(k)}_{i_{1}}<f^{*}_{i_{2}}+\varepsilon<f^{*}_{i_{2}}\leq f ^{(k)}_{i_{2}}\leq f^{(k)}_{h_{k}}<f^{*}_{i_{2}}+\varepsilon\) (\(f^{*}_{i_{1}}+4\varepsilon<f^{*}_{i_{2}}\)) holds with \(m_{k},h_{k}\in\{i_{2},i_{3}\}\). Since \(f^{(k)}_{i_{1}}<f^{*}_{i_{2}}\), only vertices \(x^{(k)}_{i_{2}}\) and \(x^{(k)}_{i_{3}}\) can change for \(k\geq K\). Also, note that \(f^{(k)}_{i_{1}}<f^{*}_{i_{2}}\) implies that no shrinking may occur. It also follows that only \(f^{(k)}_{r},f^{(k)}_{oc},f^{(k)}_{ic}\geq f^{*}_{i_{2}}\) are possible. Consider now the following 'possible' cases:  
(i) \(f^{*}_{2}\leq f^{(k)}_{r}<f^{(k)}_{h_{k}}\).