[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-gsl] Comments/questions about BFGS algorithm implemented for t
Alan W. Irwin
Re: [Help-gsl] Comments/questions about BFGS algorithm implemented for the GSL
Sun, 04 Jun 2006 17:07:22 -0700 (PDT)
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
To access my code, test results, and documentation look at the following
SourceForge web pages:
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 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
- Re: [Help-gsl] Comments/questions about BFGS algorithm implemented for the GSL,
Alan W. Irwin <=