[SciPy-user] Nelder-Mead

[joris at ster.kuleuven.ac.be]

Hi Ryan,

> My advisor is asking me questions about convergence guarantees.

To my knowledge there is no sufficiently general mathematical
convergence proof for the Nelder-Mead algorithm.  

In fact, it is known that the Nelder-Mead can sometimes fail to
converge, especially when the dimension of the search space is
large. In such cases, the simplex is moving perpendicular
to the gradient. It is also known that the simplex sometimes
can become degenerate after which is has to be reinitialised.

Having said that, you should know that there is another simplex
method, invented by Torczon in 1989 which is more robust than
the Nelder-Mead algorithm but at the price of slower convergence.
The Torczon simplex doesn't change shape, only size, and it
tries to replace the best simplex corner rather than the worse
simplex corner. The algorithm is mathematically more tractable
and Torczon has a "convergence proof", of course with idealised
assumptions.


> Are there any convergence proofs for the other minimization 
> methods in scipy.optimize?

I don't think so. Optimization is an art, not an exact science.
Even an algorithm as simple as the Newton one can easily fail, 
for example because the Jacobian is ill-conditioned, or because 
an iteration step leads again to an earlier point so that infinite 
looping occurs.

Cheers,
Joris




Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm