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

[Alan W. Irwin]

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.

I am pretty confident of the correctness of the line search because the code
tests that the collection of assertions given by Fletcher, 2.6.3 (which he
uses to prove ultimate convergence of the line search) are true after the
bracketing phase is complete and also continue to be true during the course
of the subsequent sectioning phase.  Once you have a provably correct line
search, the BFGS update part of the minimization is straightforward, and I
have followed what was done in GSL for that.

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, but
I am not going to worry about that because quadratic is certainly a
reasonable option discussed by Fletcher, I think quadratic is probably more
robust than cubic for hard problems, and Numerical Recipes is even more
conservative about this question (no derivative information is used at all)
for their own line-search algorithm.

The big news of course is mu 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.

A factor of six is well worth having so I am sure that somebody (Doug McKee
has already expressed interest) will want to port my GPLed fortran
implementation to C for the GSL library.  (I have no plans to do that
myself, but not much code is involved so it should be trivial (a few hours)
to do for somebody with good C skills.)

To facilitate such a port to C, I attach my code (the files bfgs.f and
bfgs.h) and also a main routine to test it with the Rosenbrock function
(test_rosenbrock.f).  To compile and link this under Linux use

g77 -I../include test_rosenbrock.f bfgs.f -lblas -o test_rosenbrock

where it is assumed that bfgs.h (a common block definition that keeps track
of the accounting) has been put in ../include and you have libblas installed
to do the fundamental vector manipulations.

Run the code with

./test_rosenbrock > test_rosenbrock.out

and watch that sucker converge.... :-)

My future plans are to use bfgs.f (and bfgs.h) in a wide variety of equation
of state calculations.  Those calculations should provide rigorous
numerical tests of the code (L-BFGS-B is not nearly robust enough to give
good results for these tests) so I expect there will be additional tweaks of
the line search in bfgs.f to improve its robustness when numerical significance
loss is making life difficult.

For now, though, it is already good enough to solve the non-trivial
Rosenbrock case in a much more efficient manner than the equivalent GSL
routine due to the good quality of the Fletcher line search algorithm.
Finally, I will be happy to consult with anybody who does the equivalent GSL
C code as I gain experience with robustness tweaks of the Fletcher
line-search algorithm which may be required when substantial significance
loss is present.

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
__________________________

bfgs.f
Description: bfgs.f

test_rosenbrock.f
Description: test_rosenbrock.f

bfgs.h
Description: bfgs.h