forum.alglib.net

ALGLIB forum
It is currently Thu Dec 05, 2024 1:18 am

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 5 posts ] 
Author Message
 Post subject: L-BFGS-B implementation?
PostPosted: Tue Feb 15, 2011 10:55 am 
Offline

Joined: Sun Oct 31, 2010 12:38 pm
Posts: 10
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.


Top
 Profile  
 
 Post subject: Re: L-BFGS-B implementation?
PostPosted: Tue Feb 15, 2011 11:27 am 
Offline

Joined: Tue Jan 11, 2011 10:44 am
Posts: 9
Hi,

Have you checked the BLEIC minimizer (minBLEIC)?

Kind Regards,
Claudio


Top
 Profile  
 
 Post subject: Re: L-BFGS-B implementation?
PostPosted: Tue Feb 15, 2011 11:32 am 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 927
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.


Top
 Profile  
 
 Post subject: Re: L-BFGS-B implementation?
PostPosted: Wed Feb 16, 2011 12:11 pm 
Offline

Joined: Sun Oct 31, 2010 12:38 pm
Posts: 10
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?


Top
 Profile  
 
 Post subject: Re: L-BFGS-B implementation?
PostPosted: Wed Feb 16, 2011 12:34 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 927
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group