What is xtol for minimization (method = Nelder-Mead)?

The short answer is how accurate you want the result to be, in terms of absolute error. If it xatol

is 0.01 and the method returns the location of the minimum as [1.23, 4.56]

, then there is hope (but not certainty) that the actual minimum has coordinates somewhere between 1.22 - 1.24 and 4.55 - 4.57.

Long answer. The Nelder-Mead method works with a simplex (triangle in 2 dimensions, tetrahedron in 3D, etc.). The Wikipedia page does not indicate how this simplex gets closer to the minimum, changing the size and shape (it gets smaller near the minimum). The search is considered successful if two conditions are met:

• Simplex size no more xatol
  
  (option xtol
  
  deprecated for this method, recommended xatol
  
  )
• The difference between the values ​​of the functions at the vertices of the simplex is at most fatol
  
  .

Informally, this means that the simplex has become small, and the values ​​of the objective function at its vertices are almost the same. Formally, this is a stop condition :

if (numpy.max(numpy.ravel(numpy.abs(sim[1:] - sim[0]))) <= xatol and
        numpy.max(numpy.abs(fsim[0] - fsim[1:])) <= fatol):
    break

      

        
        
        
      

    

Here sim[0]

is the first vertex of the simplex, and sim[1:]

are the remaining vertices. The condition requires that each coordinate of each vertex be within the xatol

corresponding coordinate sim[0]

. The array fsim

contains the values ​​of the functions at these vertices; here the requirement is that |fsim[k] - fsim[0]| <= fatol

for all k.

The default xatol

is 0.0001. When the search is successful, the last simplex will hit the trough; thus the size of the simplex is the precision with which we know the location of the minimum. The smaller one xatol

can be used to accurately determine the minimum, due to the longer operating time.

Usage example

We are looking for the minimum (x ^ 2 + y ^ 2), which, of course, is at the point (0, 0). At default settings, the answer is muted by about 3e-5.

>>> from scipy.optimize import minimize
>>> minimize(lambda x: x[0]**2+x[1]**2, [1, 2], method='Nelder-Mead').x
array([ -3.62769110e-05,  -3.03662006e-05])

      

        
        
        
      

    

At a smaller xatol

value (1e-6 instead of the default 1e-4), the result is about 100 times more accurate, with an error of about 3e-7.

>>> minimize(lambda x: x[0]**2+x[1]**2, [1, 2], method='Nelder-Mead', options={'xatol': 1e-6}).x
array([  3.12645001e-07,  -2.53507540e-07])