# The Nelder-Mead Simplex Algorithm Is Sixty Years Old: New Convergence Results and Open Questions
## 1 Introduction  
The original Nelder-Mead (NM) simplex algorithm was constructed in 1965 by [PERSON] and [PERSON] [1] as an improved version of the simplex method of [PERSON], [PERSON] [2]. During the almost six decades that have passed, the Nelder-Mead algorithm has became a truly popular and widely used method for the minimization problem  
\[f(x)\rightarrow\min\quad(f:\mathbb{R}^{n}\rightarrow\mathbb{R})\]  
in derivative-free optimization (see, e.g., [3; 4; 5; 6; 7; 8; 9; 10; 11]).  
In spite of its widespread use, only a few convergence results are known. They are of essentially two types. The first type of results are related to the convergence of function values at the vertices of the simplex sequence. They say nothing about the vertices. The most famous results of this type are due to [PERSON], [PERSON], [PERSON] and [PERSON] [12]. The other type of results are related to the convergence of simplex vertices or simplices. The first result of this type is due to [PERSON] [13], who proved that under a certain (Armijo-type) descent condition, the accumulation points of the simplex sequence are critical points of \(f\). Recent results on the convergence of the simplex sequence to a common limit point are given in papers [14; 15; 16].  
[PERSON] [17; 18] raised several questions concerning the Nelder-Mead method:  
* Do the function values at all vertices necessarily converge to the same value?
* Do all vertices of the simplices converge to the same point?
* Why is it sometimes so effective (compared to other direct search methods) in obtaining a rapid improvement in \(f\)?
* One failure mode is known ([PERSON] [19])--but are there other failure modes?
* Why, despite its apparent simplicity, should the Nelder-Mead method be difficult to analyze mathematically?  
In fact, there are several recent examples that indicate different types of convergence behavior:* The function values at the simplex vertices may converge to a common limit value, while the function \(f\) has no finite minimum and the simplex sequence is unbounded (Example 5 of [14]; Examples 1 and 2 of [15]; Example 4 of [20]).
* The simplex vertices may converge to a common limit point, but it is not a stationary point of \(f\) ([PERSON] [19] and Example 3 of [15]).
* The simplex sequence may converge to a limit simplex of a positive diameter, resulting in different limit values of \(f\) at the vertices at the limit simplex (Theorem 1 of [21]; Example 4 of [14]; Examples 4 and 5 of [15]; Examples 1, 2 and 3 of [20]).
* The function values at the simplex vertices may converge to a common value, while the simplex sequence converges to a limit simplex with a positive diameter (Example of 5 [20]).  
These examples are answering questions (a), (b) and (d) of [PERSON] negatively.  
There are several variants of the original [PERSON] method [1]. Here, we study two main versions of the [PERSON] algorithm: the 'original' (unordered) method of [PERSON] [1] (Algorithm 1) and the 'ordered' version of [PERSON], Reeds, [PERSON] and Wright [12] (Algorithm 2). In Section 2, we introduce both algorithms, while Section 3 contains their matrix representations. In Section 4, we study the connection and spectral properties of these matrices. In Section 5, we prove convergence of the function values at the simplex vertices for both algorithms. These results are more general than those of [PERSON] et al. [12], while their proof is quite simple.  
In Section 6, we study the convergence of the generated simplex sequence. Here, we give necessary and sufficient conditions for the convergence of the simplex sequence (for both algorithms). This relates the convergence to the convergence of an infinite matrix product. We pay particular attention to the case when the simplex sequence converges to a common limit point. The results show why the convergence problem (questions (c) and (e) of [PERSON]) is difficult. This paper closes with computational results, conclusions and open questions.