forum.alglib.net
http://forum.alglib.net/

L-BFGS-B implementation?
http://forum.alglib.net/viewtopic.php?f=2&t=302		 Page 1 of 1
Author:  Georgios [ Tue Feb 15, 2011 10:55 am ]
Post subject:  L-BFGS-B implementation?
Hello,

I am wondering if there are going to be more optimization methods with bound constraints, like the L-BFGS-B algorithm. I would like to compare the performance of different algorithms (like MinASA and L-BFGS-B) in my application

Alternatively, do you think it would be correct to simply check for the limits of the parameters during the calculation of the derivatives using a four point formula? For example in the already implemented L-BFGS if we have a variable a <= x0 <= b, then if during the derivative calculation the x0+h value is lower or higher than the limits simply set the value equal to the lower or upper bound respectively. In algorithmic sense that is:
if (x0+h < a) then
x0+h = a;
else if (x0 > b) then
x0+h = b;

I have checked this in my software and it seems to be working well (the L-BFGS is faster than MinASA) but I don't know if it worked just in few cases or if it would always work.
Author:  crotundo [ Tue Feb 15, 2011 11:27 am ]
Post subject:  Re: L-BFGS-B implementation?
Hi,

Have you checked the BLEIC minimizer (minBLEIC)?

Kind Regards,
Claudio
Author:  Sergey.Bochkanov [ Tue Feb 15, 2011 11:32 am ]
Post subject:  Re: L-BFGS-B implementation?
No, such simple check is not enough to let algorithm work (except for, maybe, few special cases of "simple" functions). Your idea is a beginning of simple active set method, which "sticks" to bounds once it encounters them. But your basic algorithm will have to "unstick" from bounds sometimes - one thing you haven't implemented, and it will be hard to achieve with your method. So you will have to implement step limits (to track activation of bounds), additional checks for other bounds being activated, some conditions to decide when to "unstick" from boundary.... and you will get minasa algorithm :)

About L-BFGS-B and other bound constrained algorithms - they are not planned. It is easier to debug and tune just a few algorithms, so new bound constrained algorithms are not planned. Even more, it is planned to replace minasa by more general minbleic (after some performance improvements, because current version of minbleic isn't competitive with minasa). But I think that at least one algorithm with general (nonlinear) constraints can be added in some mid-term perspective.
Author:  Georgios [ Wed Feb 16, 2011 12:11 pm ]
Post subject:  Re: L-BFGS-B implementation?
L-BFGS-B existed in a previous version of ALGLIB, right?

http://www.google.com/codesearch/p?hl=en#izPLqJuvKpw/trunk/InvertElli/InvertEllipsometryClass/Optimisation_Algorithms/LBFGS/lbfgsb.cs&q=alglib%20l-bfgs-b&sa=N&cd=4&ct=rc

I am wondering if I could expand the current L-BFGS implementation to deal with bound constraints based on the old code. Is it a completely different implementation or do you think it could be easily adjusted?
Author:  Sergey.Bochkanov [ Wed Feb 16, 2011 12:34 pm ]
Post subject:  Re: L-BFGS-B implementation?
Yes, it existed in ALGLIB before, but it (ALGLIB implementation) was very slow. Additionally, it was hard to support, because it was translation of original L-BFGS-B from Nocedal. L-BFGS-B is a quite complex algorithm with many subproblems being solved for each iteration. Active set methods are simples and more understandable. So one day it was dropped from ALGLIB in favor of active set methods (minASA and upcoming release of new minBLEIC).

If you want to implement L-BFGS-B, you can read "a limited memory algorithm for bound constrained optimization" by Byrd, Lu, Nocedal and Zhu. It describes L-BFGS-B algorithm, and you can see that it is not one you can implement in a day or two.

About reimplementation of unbounded L-BFGS - no, it is not possible. Bounded algorithm is far more complex that its unbounded counterpart, so you will have to rewrite almost anything.
Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/