Re: [Getfem-users] Possible bug in GMM BFGS code, linesearch

[Yves Renard]

Le vendredi 24 août 2007 14:51, vous avez écrit :
> Hello Dr. Renard,
>
> I think there is a bug in the following two lines of the GMM BFGS code:
>
> if (valy <= R(2)*valx && (lambda < R(lambda_init*1E-8) ||
>           (!unbounded && lambda_max-lambda_min < R(lambda_init*1E-8))))
>
> The first term (valy <= R(2)*valx) should check that the objective is
> bounded by 2*valx.  In case both valx and valy are positive, this works
> fine.  If valx and valy are negative, this is exactly inverted and the
> condition almost always fails.  Then BFGS does loop endlessly.
>
> Do I miss something in the above code?  (I found the problem by a small
> toy problem which has a negative value optimal solution.)

Dear Sebastian,

Yiou are right, the application on which we use BFGS are all with strictly 
positive  objective values. This is why we had no problems with this untill 
now. This is not correct of course for negative values. This test was added 
to detect the blocked situations in the applications we deal with. It is a 
little bit had oc. More experiments should be done to test its robustness.

A possible correction should be to replace R(2)*valx by something like
valx + R(2)*gmm::abs(derivative)*lambda


> attached you find a preliminary version of limited memory BFGS, 
> implemented following your gmm_solver_bfgs.h as a template.  I also 
> added a testcase showing the substantial speed improvement over BFGS for 
> problems with many variables.
> If you have no objections and after some testing I will perform in the 
> next week, you can include it into the GMM library.

Thank you very much for the limited memory version. I will be pleased to 
integrate it to Gmm once you have a stable version (you can also provide the 
sharper test you have to add to the tests programs). 

> I plan to write solvers for linear programs and quadratic programs for 
> small to medium scale problems in the GMM style of templates, mainly for 
> my own needs.  If you are interested to include them into GMM, I will 
> send them to you once they are ready.

I could be of course interesting for many people which use Gmm. 
The interest to share such a library is that anyone can propose some 
algorithms and other peoples can test them, ameliorate them ...

> One detail question: how can you actually easily debug the templated 
> code in a Linux+gcc+gdb environment?

Most of the time I use directly gdb or I use with xemacs interface. You can 
also use valgrind for memory fault or memory leaks problems. I agree debuging 
c++ template sounds sometimes like a nightmare ... !


Good continuation Sebastian, and thank you for your contribution.

Yves.

-------------------------------------------------------------------------
  Yves Renard (address@hidden)       tel : (33) 04.72.43.80.11
  Pole de Mathematiques,                       fax : (33) 04.72.43.85.29
  Institut Camille Jordan - CNRS UMR 5208
  INSA de Lyon, Universite de Lyon
  20, rue Albert Einstein
  69621 Villeurbanne Cedex, FRANCE
  http://math.univ-lyon1.fr/~renard
-------------------------------------------------------------------------