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: multidimensional optimization


Brian Gough wrote:
> 
> Fabrice Rossi writes:
>  > 1) convergence test is trickier In general (for Neural Networks
>  > application) we test for numerical nullity of the gradient. This
>  > means the gradient must be know and therefore that the convergence
>  > test prepares part of the next iteration.  We can also use a last
>  > move test.
> 
> It's true that the decomposition of "iteration" and "test" would not
> work if the desired convergence test is algorithm-dependent.
> 
> However quantities such as the gradient and "last move" can be part of
> the algorithm-independent state. This way they are available for testing.
> 
> e.g. The following struct could be used for a gradient solver,
> 
> typedef struct
>   {
>     const gsl_min_fgsolver_type * type;
>     gsl_min_fgsystem * fgsystem ;
>     double f ;           /* function value */
>     double f1 ;          /* previous function value */
>     double * x ;         /* position */
>     double * x1 ;        /* previous position */
>     double * g ;         /* gradient */
>     double * g1 ;        /* previous gradient */
>     void *state;
>   }
> 
> 
> These quantities would seem to be sufficient for most convergence
> tests. The convergence test itself would not compute any quantities
> like the gradient. They can be computed in the main iteration. That's
> how I imagine it working anyway.

Ok, you're right. We can have a step function, or something similar that
computes the gradient for the current estimation of the minimum. As we must
use a one dimensional minimization, we can assume that the value of the
function at the estimated minimum has been already calculated (in the current
sources I think there is no way get the value of the function at the estimated
minimum: it has to be recalculated. I'm I right?). So the loop is:

1) init gsl_min_fgsolver (compute value and gradient at the current position)
2) loop
	2.a) compute the descent direction (the only part that is really algorithme
dependent)
	2.b) call one dimensional minimization
	2.c) prepare next step (basically throw away previous state, compute
gradient, etc.)
	2.d) test for convergence (no computation)

>  >  2) restarting Conjugate gradient methods must be restarted to work
>  > properly (the descent direction must be set to the gradient from
>  > time to time). Systematic restarting is not a good idea in general,
>  > that's why some algorithms compute a last step size to trigger
>  > restarting, or sometimes other technics.  Unfortunately, restarting
>  > triggering test overlaps in general with convergence test.
> 
> It's possible for the iteration function to return an error code,
> suggesting a restart or inditicating that the internal minimisation
> has failed. See roots/newton.c (newton_iterate) for an example where
> the iteration function returns an error code when it encounters a
> difficulty.

Right, but there is overlapping with the convergence test. For instance, you
can compute the norm of the last move, or something similar, which can be used
also for the convergence test.

Anyway, I should try to implement something and THEN comment this source.

Fabrice Rossi

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