[Help-gsl] questions about gsl_multimin_f*_minimizers (efficiency, drawbacks)

[Help-gsl] questions about gsl_multimin_f*_minimizers (efficiency, drawbacks)

[Marc Baaden]

Hi,

I have some questions wrt the efficiency of the routines in gsl_multimin.
I have replaced a routine in an existing Fortran code (originally using
a Quasi-Newton minimizer (Harwell VA13A)) by a call to the gsl_multimin
routines, with the choice of either conjugate_pr, conjugate_fr, 
steepest_descent, vector_bfgs or nm_simplex.

The original Harwell VA13A algorithm should be quite similar to vector_bfgs.
So I was rather surprised that there is quite a noticeable "performance"
difference, the Harwell code being roughly a factor of 1.5-2 faster.
(NB: I should say here, that I use the minimizer in an interactive procedure,
where you can follow the actual minimization on the screen. So I am not
giving quantitative timings but qualitative observations).
There is no big difference with the other fdf minimizers. NM_simplex is not
adapted for the problem.

I can see different reasons for this "slow" performance, and wonder whether
there is a workaround or trick to apply or some minimizer parameters to tweak.

- In the Harwell code, one can give a step size for each of the variables
  to be minimized, whereas there is an overall step size in GSL.
  That might make a difference eg for bfgs. Can that be implemented ?
  Anybody got experience with this ?

- Concerning the function that I minimize, it is very difficult / inefficient
  to separate function evaluation and derivative calculation. So at every call
  to f, df or fdf both are evaluated. The function evaluation (which is
  necessary for the
  gradient calculation) is the bottleneck of the program (gprof: 80 % !!).
  So if the number of times this routine is called could be minimized, then
  this would probably give a significant speedup.

  My impression is that depending on the GSL method, the function is evaluated
  2-3 times more often than with the original Harwell code.

  My guess is that because with Harwell, we calculated the Hessian once at
  the beginning, and then update very rarely, it is efficient and needs less
  function evaluations, whereas I maybe the GSL
  routines re-calculate the Hessian more often. Can this be modified (eg
  give a frequency for the calculation of the second derivatives) ?

- Another (general) problem in my case is that the parameters of the
  parametric function vary over time (as I said the minimization is 
  interactive and the user can influence the function by changing its
  parameters). This seems to be an intrinsic problem when using an
  advanced fdf minimizer (other than steepest descent).

  Are there other minimization methods (or workarounds) better adapted for
  this case ?

Thanks in advance,
  Marc Baaden

-- 
 Dr. Marc Baaden  - Institut de Biologie Physico-Chimique, Paris
 mailto:baaden@smplinux.de      -      http://www.marc-baaden.de
 FAX: +49 697912 39550  -  Tel: +33 15841 5176 ou +33 609 843217




_______________________________________________
Help-gsl mailing list
Help-gsl@gnu.org
http://mail.gnu.org/mailman/listinfo/help-gsl

Re: [Help-gsl] questions about gsl_multimin_f*_minimizers (efficiency, drawbacks)

[Alan Aspuru-Guzik]

Dear Marc,

I found a similar situation. I have to minimize a very expensive
functional as well (>99% CPU). The ideal thing to do would be to
contribute better minimization algorithms to the GSL codebase. Because I
have no time to do so, I looked for other alternatives.

I found a very good optimization code that is very similar in spirit to
GSL:
http://csmr.ca.sandia.gov/opt++/

It took me like an hour to fix my C program's header files and write
function wrappers for use in OPT++. Maybe you should explore this
avenue.

Alan


On Sat, 2003-11-08 at 02:40, Marc Baaden wrote:

>   Are there other minimization methods (or workarounds) better adapted for
>   this case ?
> 
> Thanks in advance,
>   Marc Baaden
-- 
- - - - - - - - - - - - - [ cut here ] - - - - - - - - - - - - - - - - -
 
Alán Aspuru-Guzik                        [http://alan.aspuru.com] 

Re: [Help-gsl] questions about gsl_multimin_f*_minimizers (efficiency, drawbacks)

[Brian Gough]

Marc Baaden writes:
 > I have some questions wrt the efficiency of the routines in gsl_multimin.
 > I have replaced a routine in an existing Fortran code (originally using
 > a Quasi-Newton minimizer (Harwell VA13A)) by a call to the gsl_multimin
 > routines, with the choice of either conjugate_pr, conjugate_fr, 
 > steepest_descent, vector_bfgs or nm_simplex.
 > 
 > The original Harwell VA13A algorithm should be quite similar to vector_bfgs.
 > So I was rather surprised that there is quite a noticeable "performance"
 > difference, the Harwell code being roughly a factor of 1.5-2 faster.

Hi,

How does the choice of line-minimisation tolerance affect the
comparison?

In addition to the number of function evaluations it would be of
interest to compare the number of direction vectors used, since this
is (to some extent) independent of the line minimisation tolerance.

-- 
Brian Gough