1

Topic: Simplifying L-BFGS-B

I am trying to use L-BFGS-B algorithm as a part of a game engine to minimize a function that look like this


http://img170.imageshack.us/img170/1900/88964635.jpg


Where everything except alpha_1 to alpha_n is a constant and all alphas lie between 0 and 1.

I have read the original paper on L-BFGS-B algorithm they suggested three methods for subspace minimization, I would like to know which among the three would be most suitable for solving a problem like this.And are there any more changes that we can make in order tune the algorithm for our application. I want it to perform as fast as it can.

Or can you suggest some other algorithm that would produce far better results than L-BFGS-B , for a function of this kind,thereby killing the possibility of further improvement.


Thanks in advance...

Re: Simplifying L-BFGS-B

there was a post with a problem like yours (isn't it yours?):
http://forum.openopt.org/viewtopic.php?id=40

I can only suggest using ALGENCAN along with lbfgsb, sometimes it solves faster (ALGENCAN has very powerful underlying solver GENCAN for box-bound problems).

--------------------------------------------------(Signature)--------------------------------------------------------
Currently I'm busy with a paid work and thus have a limited time for OpenOpt suite support on the forum.

3

Re: Simplifying L-BFGS-B

Dmitrey wrote:

there was a post with a problem like yours (isn't it yours?):
http://forum.openopt.org/viewtopic.php?id=40

I can only suggest using ALGENCAN along with lbfgsb, sometimes it solves faster (ALGENCAN has very powerful underlying solver GENCAN for box-bound problems).


Yaa True thats mine, I didnt login so i posted as guest...

Actually I used L-BFGS-B because it was very well documented and also found lot of codes on the internet ,so i made every thing running using this algorithm  implementing in C# . But now my professor ask me if there are any possibilities of improvement so i am searching for an answer.

At that time you told that  ALGENCAN was not easy to install on windows .But in any case we have to work on windows so i didnt look into that possibility. And Since I would have to implement everything I would like something that is very well documented.

Re: Simplifying L-BFGS-B

You could try to implement second derivatives and involve a solver capable of handling them.

Another idea is to obtain solution of sparse linear system -F'' x = F' and pass it instead of F' to lbfgsb or another suitable solver.

--------------------------------------------------(Signature)--------------------------------------------------------
Currently I'm busy with a paid work and thus have a limited time for OpenOpt suite support on the forum.

5

Re: Simplifying L-BFGS-B

Dmitrey wrote:

You could try to implement second derivatives and involve a solver capable of handling them.

Another idea is to obtain solution of sparse linear system -F'' x = F' and pass it instead of F' to lbfgsb or another suitable solver.



I sorry  don't understand what your second idea is, can you please explain a little what would the solution of sparse linear system -F'' x = F' give and how would it help the algorithm to produce better results. OR may be give some references that would help me understand what you are suggesting.

Re: Simplifying L-BFGS-B

solution of sparse linear system -F'' z = F'  is Newton step. It is step wrt 2nd derivatives of a function represented as Taylor_serie
F(x) = F0 + (x-x0)F'(x0) + 0.5 * (x-x0)^2 * F''(x0) + O((x-x0)^3)
Differentiation of the statement above by x yields (ignoring O((x-x0)^3))
F'(x) =  F'(x0) +  (x-x0) * F''(x0)
In the optimum point it should be equal to 0, so the best direction in the quadratic model is a solution of -F'' z = F'
(x_new = x0 + alpha*z, alpha is a number that solver will try to estimate, or somehow handle the direction provided by user via another way).

--------------------------------------------------(Signature)--------------------------------------------------------
Currently I'm busy with a paid work and thus have a limited time for OpenOpt suite support on the forum.

7

Re: Simplifying L-BFGS-B

OK , Thanks for the explanation , I got it now. I will definitely try this out .

I wanted to ask one more thing. From one of your posts I got to know about BOBYQA , I just wanted to ask is that if i some how implement this into my application will it produce better results then the results produced by my present use of L-BFGS-B. And how difficult would it be to implement this algorithm in C# .

Re: Simplifying L-BFGS-B

You shouldn't use BOBYQA (at least for your problem). It is TOO hard to translate it into C#; and it cannot handle even user-provided gradient (and, of course, 2nd derivatives) - both are quite easy to provide for your problem. As far as I understood, you already have user-provided gradient for your problem, if not  - it should be the first thing to be done for to speed up your calculations (provided your number of variables is rather big).

--------------------------------------------------(Signature)--------------------------------------------------------
Currently I'm busy with a paid work and thus have a limited time for OpenOpt suite support on the forum.

9

Re: Simplifying L-BFGS-B

Dmitrey wrote:

You shouldn't use BOBYQA (at least for your problem). It is TOO hard to translate it into C#; and it cannot handle even user-provided gradient (and, of course, 2nd derivatives) - both are quite easy to provide for your problem. As far as I understood, you already have user-provided gradient for your problem, if not  - it should be the first thing to be done for to speed up your calculations (provided your number of variables is rather big).


Yes we have supplied predefined gradient to our problem.

Thank you very much for your help.