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

[Alan W. Irwin]

On 2006-04-18 20:38+0100 Brian Gough wrote:

> Alan W. Irwin writes:
> > But why does it take so long (119 iterations) to get to the final rapid
> > convergence phase (both for the GSL C version and my fortran implementation
> > of the same algorithm)?  In Fletcher's book, "Practical Methods of
> > Optimization", 2nd edition, the problem only requires 21 iterations to
> > converge (see Table 3.5.1) with Fletcher's own BFGS code.  Although, my
> > experients showed the L-BFGS-B implementation is fundamentally non-robust,
> > for this test function it seems to be okay, and it converges in 39
> > iterations confirming there is something wrong with the efficiency of the
> > preliminary convergence steps in the GSL case.
> >
> > I suspect there is a substantial inefficiency problem with the GSL line-
> > search implementation (since the BFGS update part is completely
> > straightforward).  I am not any sort of expert in this field though so I
> > cannot pin down where the problem is occurring, but a superficial google
> > search reveals a number of complaints about the GSL minimization efficiency.
>
> Thanks for your thoughtful comments.  I agree that the line
> minimisation is a likely suspect and has room for improvement.  What
> line minimisation method is used by Fletcher and what criteria for
> stopping each line minimisation? (I don't have the book but I will see
> about getting it).

First to get a misleading issue that I introduced above out of the way, I
have subsequently learned that the GSL bracketing effort is not logically
part of the line search. Instead, if a smaller function value is found than
f0, (i.e., the solution of the line search is not yet bracketed), there is
an immediate return from bfgs_iterate with a doubled step size and to
continue the bracketing attempt you must simply call bfgs_iterate again.  So
to compare with other line searches that include the bracketing effort as
part of the line search, you mustn't count all calls to bfgs_iterate as a
line search iteration.  Once I made this change in accounting, then the
total number of line searches for the Rosenbrock function problem reduces
from the previously reported large number of iterations to what seems a
respectable 38 for the GSL routine. However, that drop in numbers caused by
the different accounting simply means way too many function and gradient
evaluations are going on in the bracketing phase compared to other
implementations.

To account for this directly, I have counted function and gradient
evaluations for the standard Rosenbrock minimization, and the results (519
function evaluations and 381 gradient evalations in 38 complete line
searches to achieve convergence) are roughly an order of magnitude worse for
GSL than the same Rosenbrock function minimization using other
implementations.  The corresponding numbers are 56, 50, and 21 for the
Fletcher BFGS algorithm (as reported by his book), and 47, 47, and 39 for
the L-BFGS-B fortran algorithm that I find works quite nicely in this case.
(Note, I normally don't use L-BFGS-B because of the non-standard free
license and general non-robustness, but it is useful for this comparison.)
Since all methods roughly have the same number of complete line searches, I
think the large number of function and gradient evaluations in the GSL line
search confirms inefficiencies (probably both in the bracketing part and
sectioning part) of the GSL line search algorithm.

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.  Once that
works, I will make that GPLed code available to this list so that others
here will have an opportunity to implement that in C for GSL. (My C skills
are rusty so I don't want to take the comparatively large time that would be
required for me to do the C implementation myself.) Doug McKee has already
expressed some interest in doing that C coding independently, but it might
be worthwhile to wait until I get some positive results with the Fletcher
algorithm both with the simple Rosenbrock function minimization test and my
much more stringent large variety of free-energy minimization tests.

To address the above questions from Brian, Fletcher doesn't name his line
search algorithm (although he thoroughly describes it).  Both the bracketing
part (13 lines of pseudo-code) and the sectioning part (11 lines of
pseudo-code) seem fairly sophisticated with tolerance for roundoff error
built in, etc.  Furthermore, the Fletcher line search algorithm has a sigma
parameter which can be used to make anywhere from completely accurate line
searches (sigma = 0.0, normally only used for theoretical investigations) to
fairly accurate line searches (sigma = 0.1) to inexact line searches (sigma
= 0.9).  From quite a body of numerical tests on standard problems, Fletcher
concluded (with some surprise since inexact line searches were in vogue at
the time) that the fairly accurate line search method was more efficient
than the inexact line search by a small margin.  GSL developers would
probably want to fix sigma to one of Fletcher's tested values within the
code. It's doubtful users would want to be able to set this parameter for
themselves since it makes so little difference (at least according to
Fletcher's tests.)

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
__________________________