# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 5 Convergence of the Function Values at the Vertices
We assume that \(K>0\) is big enough, so that for \(k\geq K\), \(f_{1}^{*}\leq f_{1}^{(k)}<f_{1}^{*}+\varepsilon\), \(f_{2}^{*}\leq f_{i}^{(k)}<f_{2}^{*}+\varepsilon\) (\(i=2,3\)), where \(\varepsilon>0\) is such that \(f_{1}^{*}+4\varepsilon<f_{2}^{*}\). Depending on the selected case, \(f_{r}^{(k)}\geq f_{2}^{*}\), \(f_{oc}^{(k)}\geq f_{2}^{*}\) or \(f_{ic}^{(k)}\geq f_{2}^{*}\) must hold. In case (i), \(x_{r}^{(k)}\) replaces \(x_{2}^{(k)}\) and \(S^{(k+1)}=S^{(k)}T(1)P_{2}\). In case (ii), since \(x_{oc}^{(k)}=\frac{1}{2}\Big{(}x_{c}^{(k)}+x_{r}^{(k)}\Big{)}\), we have  
\[f_{oc}^{(k)}\leq\frac{1}{4}f_{1}^{(k)}+\frac{1}{4}f_{2}^{(k)}+\frac{1}{2}f_{r} ^{(k)}\leq\frac{1}{4}(f_{1}^{*}+\varepsilon)+\frac{3}{4}(f_{2}^{*}+\varepsilon )<f_{2}^{*}.\]  
Hence, case (ii) cannot occur. Similarly, in case (iii),  
\[f_{ic}^{(k)}\leq\frac{1}{4}f_{1}^{(k)}+\frac{1}{4}f_{2}^{(k)}+\frac{1}{2}f_{3} ^{(k)}\leq\frac{1}{4}(f_{1}^{*}+\varepsilon)+\frac{3}{4}(f_{2}^{*}+\varepsilon )<f_{2}^{*}\]  
showing that case (iii) cannot occur. Hence, we can only have the simplex sequence  
\[S^{(k+K)}=S^{(K)}[T(1)P_{2}]^{k},\quad k\geq 0.\]  
Since \(T(1)P_{2}\) is a 6-involutory matrix \(\big{(}[T(1)P_{2}]^{6}=I_{3}\big{)}\), \(\big{\{}S^{(k+K)}\big{\}}\) is a periodic sequence and \(S^{(6+K)}=S^{(K)}\), which is impossible by the insertion rule. This is a contradiction; thus, \(f_{1}^{*}=f_{2}^{*}=f_{3}^{*}\). For Algorithm 1, we prove the following results. First, observe the following facts. For nonshrink steps, we have  
(i) \(x_{i}^{(k+1)}=x_{i}^{(k)}\) for \(i\
eq h_{k}\), \(x_{h_{k}}^{(k)}=v\);  
(ii) \(f_{i}^{(k+1)}=f_{i}^{(k)}\) (\(i\
eq h_{k}\)) and \(f_{h_{k}}^{(k+1)}<f_{h_{k}}^{(k)}\);  
(iii) \(f_{h_{k}}^{(k)}=\min_{i}f_{i}^{(k)}\leq f_{i}^{(k)}\leq\max_{i}f_{i}^{(k)}=f_{ h_{k}}^{(k)}\);  
(iv) \(f_{\ell_{k+1}}^{(k+1)}\leq f_{h}^{(k)}\) and \(f_{h_{k+1}}^{(k+1)}\leq f_{h_{k}}^{(k)}\). Hence, \(f_{i}^{(k+1)}\leq f_{i}^{(k)}\) (\(i=1,\ldots,n+1\)). **Lemma 6** (Algorithm 1). : _If \(f:\mathbb{R}^{n}\to\mathbb{R}\) is bounded below and only a finite number of shrink operations occur, then there exist finite limit values \(f_{i}^{*}\) such that \(f_{i}^{(k)}\to f_{i}^{*}\) (\(i=1,2,\ldots,n+1\))._  
The only difference to Lemma 2 is that the function values \(f_{i}^{(k)}\) and their limits are not ordered. **Lemma 7** (Algorithm 1). : _If \(f:\mathbb{R}^{n}\to\mathbb{R}\) is quasiconvex on \(\mathbb{R}^{n}\) and bounded below, then there exist finite limit values \(f_{i}^{*}\) such that \(f_{i}^{(k)}\to f_{i}^{*}\) (\(i=1,2,\ldots,n+1\))._  
Proof. : If \(f\) is quasiconvex, then in the case of shrinking, the inequality  
\[f_{i}^{(k+1)}=f\bigg{(}\frac{1}{2}\Big{(}x_{i}^{(k)}+x_{\ell_{k}}^{(k)}\Big{)} \bigg{)}\leq\max\Big{\{}f_{i}^{(k)},f_{\ell_{k}}^{(k)}\Big{\}}=f_{i}^{(k)}\quad( i=1,\ldots,n+1)\]  
also holds. So does Lemma 6. **Lemma 8** (Algorithm 1). : _If \(f:\mathbb{R}^{n}\to\mathbb{R}\) is strictly convex, then no shrinking occurs._  
Proof. : Shrinking happens if \(f^{(k)}_{m_{k}}\leq f^{(k)}_{r}<f^{(k)}_{h_{k}}\wedge f^{(k)}_{oc}>f^{(k)}_{r}\) or \(f^{(k)}_{ic}\geq f^{(k)}_{h_{k}}\wedge f^{(k)}_{r}\geq f^{(k)}_{h_{k}}\) holds. In general, \(f^{(k)}_{c}<\frac{1}{n}\sum_{i=1,\,i\
eq h_{k}}^{n+1}f^{(k)}_{i}\leq f^{(k)}_{m _{k}}\). If \(f^{(k)}_{m_{k}}\leq f^{(k)}_{r}<f^{(k)}_{h_{k}}\), then \(f^{(k)}_{oc}=f\Big{(}\frac{1}{2}\Big{(}x^{(k)}_{r}+x^{(k)}_{c}\Big{)}\Big{)}< \frac{1}{2}\Big{(}f^{(k)}_{r}+f^{(k)}_{m_{k}}\Big{)}\leq f^{(k)}_{r}\). If \(f^{(k)}_{r}\geq f^{(k)}_{h_{k}}\), then \(f^{(k)}_{ic}=f\Big{(}\frac{1}{2}\Big{(}x^{(k)}_{c}+x^{(k)}_{h_{k}}\Big{)} \Big{)}<\frac{1}{2}\Big{(}f^{(k)}_{c}+f^{(k)}_{h_{k}}\Big{)}\leq f^{(k)}_{h_{k}}\). **Remark 1** (Algorithm 1). : _Assume that \(f:\mathbb{R}^{n}\to\mathbb{R}\) is convex. Then, \(f^{(k)}_{c}\leq f^{(k)}_{m_{k}}\). If \(f^{(k)}_{m_{k}}\leq f^{(k)}_{r}<f^{(k)}_{h_{k}}\), then \(f^{(k)}_{oc}\leq f^{(k)}_{r}\). If \(f^{(k)}_{r}\geq f^{(k)}_{h_{k}}\), then \(f^{(k)}_{ic}\leq f^{(k)}_{h_{k}}\).