Re: [Help-gsl] Comments/questions about BFGS algorithm implemented for the GSL

[Alan W. Irwin]

On 2006-04-20 16:45-0700 Alan W. Irwin wrote:

> On 2006-04-18 15:25-0700 Alan W. Irwin wrote:
>
> > Fletcher gives a nicely detailed description of his implementation of the
> > line search (both the bracketing part and the sectioning part) and BFGS
> > technique, and I am currently implementing that in fortran.
>
> I have now completed my GPLed implementation of Fletcher's line search (R.
> Fletcher, "Practical Methods of Optimization" 2nd ed. John Wiley and Sons),
> + BFGS update in fortran, and the results provide a factor of six
> improvement in efficiency over the equivalent GSL implementation for the
> standard Rosenbrock minimization test.
>
> For the standard Rosenbrock problem, my implementation of Fletcher's line
> search (with quadratic extrapolation/interpolation) requires 80 function
> evaluations and 56 gradient evaluations in 18 iterations (line search plus
> BFGS update) to converge using the same convergence criterion (delta f <
> 1.d-8) as Fletcher.  His corresponding numbers are better (56, 50, in 21
> iterations) presumably because of his cubic extrapolation/interpolation...

> The big news of course is my current fortran implementation requires roughly
> a factor of six less function/gradient calls than the BFGS implementation in
> GSL (which required 519 function evaluations and 381 gradient evaluations in
> 38 complete line searches to achieve convergence) for this standard
> Rosenbrock minimization problem.

I have now made some changes to my fortran implementation including using
cubic extrapolation/interpolation whenever the required derivative
information is available for the last two points of the line search. My
Rosenbrock test minimization efficiency is now 60 function evaluations and
44 gradient evaluations in the 18 BFGS iterations required for convergence,
which is quite close to Fletcher's results, and a factor of 9 (!) better
than the current GSL implementation of the BFGS technique.

I use exactly the GSL BFGS update (translated from C to fortran) between
line searches so the enormous efficiency difference must be due to some
problem with the current GSL line search (which will affect the efficiency
of more than just the BFGS optimization in GSL).

A casual google search shows many others have also commented on the
inefficiency of the GSL line search, and now is an excellent opportunity to
solve the problem once and for all.  GSL line searches will gain almost an
order of magnitude in speed if somebody takes an afternoon's work to port my
fortran implementation of the line search in Fletcher's book to C. (I
estimate it will take only an afternoon for a C expert [which I am not]
since the whole algorithm can be described just by a page of pseudo-code in
Fletcher's book.)

To access my code, test results, and documentation look at the following
SourceForge web pages:

http://freeeos.cvs.sourceforge.net/freeeos/freeeos/utils/README.test_rosenbrock?view=log
http://freeeos.cvs.sourceforge.net/freeeos/freeeos/utils/test_rosenbrock.out_standard?view=log
http://freeeos.cvs.sourceforge.net/freeeos/freeeos/utils/test_rosenbrock.f?view=log
http://freeeos.cvs.sourceforge.net/freeeos/freeeos/src/bfgs.f?view=log
http://freeeos.cvs.sourceforge.net/freeeos/freeeos/include/bfgs.h?view=log

I don't anticipate any further changes to my BFGS implementation, but if
such a change occurs, it will be immediately accessible (as soon as I
CVS commit it to the SourceForge repository) from the above locations.

Build the code with

g77 test_rosenbrock.f bfgs.f -o test_rosenbrock -lblas

(the included common block definition, bfgs.h, must be in the current
directory, and libblas is the fortran BLAS library that usually is part
of the Lapack package).

and execute it with

./test_rosenbrock > test_rosenbrock.out_local

Your local test_rosenbrock.out_local should be the same as
test_rosenbrock.out_standard (aside from differences in floating-point
rounding between your platform and mine).  Furthermore, if you implement the
Fletcher line search in C, you should get very close to the above results
for the Rosenbrock function test case.

Contact me directly if you have any questions about my fortran implementation
of the line search in Fletcher's book.

Alan
__________________________

Alan W. Irwin

Astronomical research affiliation with Department of Physics and Astronomy,
University of Victoria (astrowww.phys.uvic.ca).

Programming affiliations with the FreeEOS equation-of-state implementation
for stellar interiors (freeeos.sf.net); PLplot scientific plotting software
package (plplot.org); the Yorick front-end to PLplot (yplot.sf.net); the
Loads of Linux Links project (loll.sf.net); and the Linux Brochure Project
(lbproject.sf.net).
__________________________

Linux-powered Science
__________________________