Re: multidimensional optimization

[Fabrice Rossi <rossi at ufrmd dot dauphine dot fr>]

Fabrice Rossi wrote:
> 
> Brian Gough wrote:
> >
> > It might be important for the user to follow the progress of the 1d
> > minimisations, so perhaps the algorithm should be split twice. A
> > separate inner loop for the 1-d minimisation could be used like this,
> >
> >     do {
> >       get gradient
> >       do {
> >         minimise in 1d
> >       } while (!converged_1d)
> >       ...
> >    } while (!converged)
> >
> > I'm don't think that the user should call the existing gsl_min
> > functions --- we would provide a suitable minimisation function (maybe
> > a wrapper around an existing gsl_min function) that will take care of
> > the vector arithmetic so the 1d minimisation is as simple as the outer
> > loop.
> 
> Right. I've already written a wrapper that allows to consider a R^n function,
> a starting point and a direction as a R function. I will provide a way to
> control the 1d minimisation and a way to automatize everything (with a
> suitable way to specify parameters for the internal 1d minimisation).

There is a small efficiency related problem with the current implementation of
1-d minimisation. When a 1d-min is started, the init function computes the
value of the studied function at each of the three starting points and in
general store these values in the internal state of the algorithm. This is a
nice behavior when the minimization is done starting with an interval
specified by the user (for instance). In the case of gradient descent, this is
a source of useless computation. We need to find an initial interval where the
1d-min is going to proceed. In order to do this, we must evaluate the function
at several places, which implies that the 1-d min will recompute already known
values. This is not a good idea: I've done a lot of experiments with neural
networks and I've "discovered" that precise localization of the minimum in the
1d-min is not needed. In fact, on many examples, I only needed between 5 and
10 evaluations of the 1d function to find a suitable point. This means that
having 3 useless evaluation if really not good.

I propose therefore to modify the gsl_min_fminimizer structure so as to
include the value of the studied function at the estimated minimum and at the
bounds of the interval. In order to allow flexibility, I propose to include
boolean flags to specify wether these values are available or not. 

We can use something like:
typedef struct
  {
    const gsl_min_fminimizer_type * type;
    gsl_function * function ;
    double minimum ;
    double f_minimum ;
    unsigned char is_f_minimum; /* is it the correct way to make a flag? */
    gsl_interval interval ;
    double f_lower;
    unsigned char is_f_lower;
    double f_upper;
    unsigned char is_f_upper;
    void *state;
  }
gsl_min_fminimizer;

Thanks to the flags, it is possible to implement 1d-min algorithms that do not
compute the value of the function at the bounds of the interval.

Any objection/suggestion?

Fabrice Rossi