From octave-sources-request at bevo dot che dot wisc dot edu Sat Nov  1 05:09:14 2003
Subject: Re: Line minimization routines - proposed modification to octave       forgeline_min
From: etienne at isr dot ist dot utl dot pt
To: "Michael Creel" <michael dot creel at uab dot es>
Cc: octave-sources at bevo dot che dot wisc dot edu
Date: Sat, 1 Nov 2003 11:08:40 -0000 (WET)


  Hi all,

just to say that I think you're right to want to prevent line_min() from
iterating zillions of times. One way or another, this should be fixed.
I did not look in the detail of the code you sent (i am w/out Octave at
the moment and for some time) but if it is tested, looks more robust than
the current code and does not cause too much extra overhead, it probably
should go in.

  Cheers,

  Etienne

> Hello all,
> Getting ready to do some large scale minimizations, I've been looking into
> getting an efficient and robust line minimization routine working. Up
> until
> now I've been using my own routine, line_search.m:
>
> line_search.m:
>   * This is a robust routine that checks to see that it really finds a
> stepsize that leads to an improvement.
>
> On the other hand, there is line_min in octave forge.
>   * this is "efficient" in that it tries to find the best stepsize. Seems
> like
> golden step, if my neurons aren't failing
> A couple of problems with this code:
>   * It does not limit the number of iterations used to find the best
> stepsize
>   * it does not check that the final stepsize is in fact better than a
> stepsize of zero. This is a problem that occurs in practice with this
> code,
> not just a possibility.
>
>
> Now, there is no reason to try to get the exact best stepsize, if it takes
> a
> zillion iterations. We're trying to minimize the time needed to minimize
> the
> objective function. The many function evaluations might better be used to
> re-evaluate the direction, rather than find a really optimal stepsize. So,
> there is a tradeoff.
>
> The routine mc_line_min.m combines the two approaches. It is basically
> line_min, but with a limit on the maximum number of function evaluations
> used
> to get the best stepsize that is proportional to the number of parameters.
> Also, checking for actual improvement is enforced, and it falls back to
> the
> line_search routine if none is found.
>
> In some benchmarking, I have found that mc_line_min uses about 0.6 the
> time
> that line_search does. Furthermore, the line_min that comes with octave
> forge
> is prone to getting hung up doing a zillion iterations, and in my work, it
> is
> not usable.
>
> So, for your minimizing pleasure, I attach the following so you can try it
> out
> yourself.
> Regards, Michael
>