This is the mail archive of the gsl-discuss@sourceware.cygnus.com mailing list for the GSL project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: multimin question


I've been thinking about stopping criterion for multimin. I've the following
ideas but I need feedback on everything, as my only experience is Neural
Networks a field in which reaching a minimum is unfortunately a seldom event
8-).

- elementary tests:
	- gradient norm. This is the only one which is really correct on a
mathematical point of view, because having a zero gradient is a necessary
condition for a minimum. The main problem is that (as explained in my previous
post) the gradient is used to locate the minimum so having a very small value
might be impossible
	- last move in input space (i.e. in R^n). Thanks to the history, it's easy to
implement. But with complex algorithms (conjugate gradients) you might obtain
a bad descent direction. Rather than stoping the algorithm for a small move,
you should restart it with the gradient as descent direction. 
	- last move in output space (i.e. for f(x), where x is the current estimate
of the minimum). Again easy to implement, again might trigger problems for bad
descent direction.

- more complex tests:
Basically, I think the algorithm should use a return code of the bracketing
algorithm. With the corrected version of my bracketing algorithm (in the CVS)
and my current (not in the CVS) version of the test program, it might happen
that the algorithm fails to fulfill the convergence criterion. In this case,
it fails because the bracketing algorithm does not find a bracketing interval
whereas the algorithm has been restarted (and therefore that the descent
direction is in fact the gradient). But there are basically two reasons for
the bracketing to fail : 
1) it is not able to find a x>e (e is the machine precision) such that
f(x)<f(0)
2) it has x such that x>e, f(x)<f(0) but it is not able to find a y>x such
that f(y)>f(x).

The second case is quite strange. The first case is very common and simply
shows that the descent direction does not allow decrease. I considered this to
be a bug, so I programmed bracketing to return GSL_FAILURE. But it should
return something else. Then in the multimin algorithm, we will react on the
result. If the bracketing fails for reason 1 and we have used the gradient as
descent direction, we might decide that the algorithm as converged.

Comments?

Fabrice Rossi

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]