seeking convergence with optimize.fmin on scipy

Question

I have a function I want to minimize with scipy.optimize.fmin. Note that I force a print when my function is evaluated.

My problem is, when I start the minimization, the value printed decreases untill it reaches a certain point (the value 46700222.800). There it continues to decrease by very small bites, e.g., 46700222.797,46700222.765,46700222.745,46700222.699,46700222.688,46700222.678 So intuitively, I feel I have reached the minimum, since the length of each step are minus then 1. But the algorithm keeps running untill I get a "Maximum number of function evaluations has been exceeded" error.

My question is: how can I force my algorithm to accept the value of the parameter when the function evaluation reaches a value from where it does not really evolve anymore (let say, I don't gain more than 1 after an iteration). I read that the options ftol could be used but it has absolutely no effect on my code. In fact, I don't even know what value to put for ftol. I tried everything from 0.00001 to 10000 and there is still no convergence.

Answer 1

There is actually no need to see your code to explain what is happening. I will answer point by point quoting you.

My problem is, when I start the minimization, the value printed decreases untill it reaches a certain point (the value 46700222.800). There it continues to decrease by very small bites, e.g., 46700222.797,46700222.765,46700222.745,46700222.699,46700222.688,46700222.678

Notice that the difference between the last 2 values is -0.009999997913837433, i.e. about 1e-2. In the convention of minimization algorithm, what you call values is usually labelled x. The algorithm stops if these 2 conditions are respected AT THE SAME TIME at the n-th iteration:

• convergence on x: the absolute value of the difference between x[n] and the next iteration x[n+1] is smaller than xtol
• convergence on f(x): the absolute value of the difference between f[n] and f[n+1] is smaller than ftol.

Moreover, the algorithm stops also if the maximum number of iterations is reached.

Now notice that xtol defaults to a value of 1e-4, about 100 times smaller than the value 1e-2 that appears for your case. The algorithm then does not stop, because the first condition on xtol is not respected, until it reaches the maximum number of iterations.

I read that the options ftol could be used but it has absolutely no effect on my code. In fact, I don't even know what value to put for ftol. I tried everything from 0.00001 to 10000 and there is still no convergence.

This helped you respecting the second condition on ftol, but again the first condition was never reached.

To reach your aim, increase also xtol.

The following methods will also help you more in general when debugging the convergence of an optimization routine.

• inside the function you want to minimize, print the value of x and the value of f(x) before returning it. Then run the optimization routine. From these prints you can decide sensible values for xtol and ftol.
• consider nondimensionalizing the problem. There is a reason if ftol and xtol default both to 1e-4. They expect you to formulate the problem so that x and f(x) are of order O(1) or O(10), say numbers between -100 and +100. If you carry out the nondimensionalization you handle a simpler problem, in the way that you often know what values to expect and what tolerances you are after.
• if you are interested just in a rough calculation and can't estimate typical values for xtol and ftol, and you know (or you hope) that your problem is well behaved, i.e. that it will converge, you can run fmin in a try block, pass to fmin only maxiter=20 (say), and catch the error regarding the Maximum number of function evaluations has been exceeded.

Answer 2

I just spent three hours digging into the source code of scipy.minimize. In it, the "while" loop in function "_minimize_neldermead" deals with the convergence rule:

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

"fsim" is the variable that stores results from functional evaluation. However, I found that fsim[0] = f(x0) which is the function evaluation of the initial value, and it never changes during the "while" loop. fsim[1:] updates itself all the time. The second condition of the while loop was never satisfied. It might be a bug. But my knowledge of mathematical optimization is far from enough to judge it.

My current solution: design your own system to control the convergence. Add this in your function:

global x_old, Q_old
if (np.absolute(x_old-x).sum() <= 1e-4) and (np.absolute(Q_old-Q).sum() <= 1e-4):
    return None
x_old = x; Q_old = Q

Here Q=f(x). Don't forget to give them an initial value.

Update 01/30/15: I got it! This should be the correct code for the second line of the if function (i.e. remove numpy.absolute):

numpy.max(fsim[0] - fsim[1:]) <= ftol)

btw, this is my first debugging of a open source software. I just created an issue on GitHub.

Update 01/31/15 - 1: I don't think my previous update is correct. Nevertheless, this is the a screenshot of the iterations of a function using the original code.

It prints the values of sim and fsim variable for each iteration. As you can see, the changes of each iteration is less than both of xtol and ftol values, but it just kept going without stopping. The original code compares the difference between fsim[0] and the rest of fsim values, i.e. the value here is always 87.63228689 - 87.61312213 = .01916476, which is greater than ftol=1e-2.

Update 01/31/15 - 2: Here is the data and code that I used to reproduce the previous results. It includes two data files and one iPython Notebook file.