# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 5 Convergence of the Function Values at the Vertices  
[PERSON] et al. (1998) studied the convergence of function values at the simplex vertices for Algorithm 2. We cite their two most important results, before proving more general results for both Algorithms. **Lemma 2** (Lemma 3.3 of (1998)). : _If function \(f\) is bounded from below on \(\mathbb{R}^{n}\) and only a finite number of shrink iterations occur, then each sequence \(\left\{f_{i}^{(k)}\right\}_{k=0}^{\infty}\) (generated by Algorithm 2) converges to some limit \(f_{i}^{*}\) for \(i=0,1,\ldots,n+1\) and \(f_{1}^{*}\leq f_{2}^{*}\leq\cdots\leq f_{n+1}^{*}\)._  
Lemma 2 guarantees the convergence under rather general conditions. In general, the limit values \(\left\{f_{i}^{*}\right\}_{i=1}^{n+1}\) can be different as shown by Examples 1 and 2 of ([PERSON], 1998) (also see ([PERSON], 1998; [PERSON], 1998)). **Theorem 2** (Theorem 5.1 of (1998)). : _Assume that \(f\) is a strictly convex function on \(\mathbb{R}^{2}\) with bounded level sets. Assume that \(S^{(0)}\) is non-degenerate. Then, the Nelder-Mead simplex method (Algorithm 2) converges in the sense that \(f_{1}^{*}=f_{2}^{*}=f_{3}^{*}=f^{*}\)._  
Theorem 2 is generally considered as the main result of (1998). In addition, it can be proved (see ([PERSON], 1998)) that if \(f\) is strictly convex on \(\mathbb{R}^{2}\) with bounded level sets, \(S^{(0)}\) is non-degenerate (affine invariant); thus, any accumulation point \(S^{\prime}\) of the simplex sequence \(\left\{S^{(k)}\right\}\) (generated by Algorithm 2) has the form \(S^{\prime}=[x^{\prime},x^{\prime},x^{\prime}]\). We need the following concept and results. **Definition 1**. : _Let \(f\) be defined on a convex set \(S\subset\mathbb{R}^{n}\). The function \(f\) is said to be quasiconvex on \(S\) if_  
\[f(\lambda x_{1}+(1-\lambda)x_{2})\leq\max\{f(x_{1}),f(x_{2})\}\]  
_for every \(x_{1},x_{2}\in S\) and for every \(\lambda\in[0,1]\)._  
Convexity implies quasiconvexity. **Lemma 3** (Lemma 6 of ([PERSON], 1998)). : _If \(f\) is quasiconvex and bounded below on \(\mathbb{R}^{n}\), then each sequence \(\left\{f_{i}^{(k)}\right\}_{k=0}^{\infty}\) is monotone decreasing and converges to some limit \(f_{i}^{*}\) for \(i=0,1,\ldots,n+1\). Furthermore, \(f_{1}^{*}\leq f_{2}^{*}\leq\cdots\leq f_{n+1}^{*}\)._  
**Corollary 3** (Corollary 2 of ([PERSON], 1998)). : _If \(f\) is convex on \(\mathbb{R}^{n}\) and an index \(1\leq j\leq n\) exists such that \(f_{j}^{(k)}<f_{n+1}^{(k)}\), then \(f_{ic}^{(k)}<f_{n+1}^{(k)}\) and no shrinking occurs in iteration \(k\)._  
**Lemma 4** (Lemma 10 of ([PERSON], 1998)). : _Assume that \(f\) is convex and bounded below on \(\mathbb{R}^{n}\). If for some integer \(\ell\) (\(1\leq\ell\leq n\)),_  
\[f_{\ell}^{*}<f_{\ell+1}^{*}, \tag{21}\]  
_then there is an index \(K>0\) such that for all \(k\geq K\), \(j^{(k)}>\ell\), that is, the first \(\ell\) vertices do not change._  
**Lemma 5** (Lemma 11 of ([PERSON], 1998)). : _If \(f\) is convex and bounded below on \(\mathbb{R}^{n}\), then \(f_{n}^{*}=f_{n+1}^{*}\)._  
The following generalization of Theorem 2 of [PERSON] et al. was proved in ([PERSON], 1998). Here, we present it with a new short proof. **Theorem 3**. : _Assume that \(f\) is a convex function on \(\mathbb{R}^{2}\) and is bounded below. Then, the Nelder-Mead simplex method (Algorithm 2) converges in the sense that \(f_{1}^{*}=f_{2}^{*}=f_{3}^{*}\)._Proof. : It follows (Lemmas 3 and 5) that \(f_{1}^{*}\leq f_{2}^{*}=f_{3}^{*}\). Assume that \(f_{1}^{*}<f_{2}^{*}\). It follows from Lemma 4 that there exists an index \(K>0\) such that for \(k\geq K\), \(x_{1}^{(k)}=x_{1}^{(K)}\). Hence, only \(x_{2}^{(k)}\) and \(x_{3}^{(k)}\) may change. The insertion rule and the impossibility of shrinking (Corollary 3) imply that only the following cases are possible:  
(i) \(f_{1}^{(k)}\leq f_{r}^{(k)}<f_{2}^{(k)}\);  
(ii) \(f_{2}^{(k)}\leq f_{r}^{(k)}<f_{3}^{(k)}\) and \(f_{1}^{(k)}\leq f_{oc}^{(k)}\leq f_{r}^{(k)}\);  
(iii) \(f_{3}^{(k)}\leq f_{r}^{(k)}\) and \(f_{1}^{(k)}\leq f_{ic}^{(k)}<f_{3}^{(k)}\).