QuantLib › quantlib-dev

optimizers

Classic

List

Threaded

10 messages Options

Bianchetti Marco

optimizers

Message

Hello,

at the moment are available into QuantLib the following optimizers:

Simplex (recently revisited: the Numerical Recipes implementation badly failed in finding the minimum of a 1D parabole...)
Levenberg-Marquardt
Conjugate Gradient
Steepest Descent (still to be debugged, work in progress)

and we are currently considering the option to port into QuantLib the Broyden-Fletcher-Goldfarb-Shanno (BFGS2) algorithm, which in GSL is declared to be the best (see the text below). So:

Any comment on the choice of BFGS2? do anyone has experience with it ?
is anyone aware of an available open source C++ implementation to be ported into Quantlib with small effort ?

Personally, I would prefer NOT to translate the GSL implementation from C to C++, because of the danger to introduce some tricky bug and because it requires a much more sophisticated test suite (and much work).

ciao

Marco

---

from: http://www.gnu.org/software/gsl/manual/html_node/Multimin-Algorithms.html

Minimizer: gsl_multimin_fdfminimizer_vector_bfgs2
Minimizer: gsl_multimin_fdfminimizer_vector_bfgs

These methods use the vector Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm. This is a quasi-Newton method which builds up an approximation to the second derivatives of the function f using the difference between successive gradient vectors. By combining the first and second derivatives the algorithm is able to take Newton-type steps towards the function minimum, assuming quadratic behavior in that region.
The bfgs2 version of this minimizer is the most efficient version available, and is a faithful implementation of the line minimization scheme described in Fletcher's Practical Methods of Optimization, Algorithms 2.6.2 and 2.6.4. It supercedes the original bfgs routine and requires substantially fewer function and gradient evaluations. The user-supplied tolerance tol corresponds to the parameter \sigma used by Fletcher. A value of 0.1 is recommended for typical use (larger values correspond to less accurate line searches).

-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

DU VIGNAUD DE VILLEFORT FRANCOIS GASAPRD PHI

Re: optimizers

Message

Here is a good C++ implementation candidate,

http://www.alglib.net/optimization/lbfgs.php

Though, I’m not absolutely sure that the terms of use are compatible with those of QL.

François

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Bianchetti Marco
Sent: Wednesday, May 23, 2007 6:13 PM
To: [hidden email]
Subject: [Quantlib-dev] optimizers

Hello,

at the moment are available into QuantLib the following optimizers:

· Simplex (recently revisited: the Numerical Recipes implementation badly failed in finding the minimum of a 1D parabole...)

· Levenberg-Marquardt

· Conjugate Gradient

· Steepest Descent (still to be debugged, work in progress)

and we are currently considering the option to port into QuantLib the Broyden-Fletcher-Goldfarb-Shanno (BFGS2) algorithm, which in GSL is declared to be the best (see the text below). So:

· Any comment on the choice of BFGS2? do anyone has experience with it ?

· is anyone aware of an available open source C++ implementation to be ported into Quantlib with small effort ?

ciao

Marco

---

from: http://www.gnu.org/software/gsl/manual/html_node/Multimin-Algorithms.html

Minimizer: gsl_multimin_fdfminimizer_vector_bfgs2
Minimizer: gsl_multimin_fdfminimizer_vector_bfgs

These methods use the vector Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm. This is a quasi-Newton method which builds up an approximation to the second derivatives of the function f using the difference between successive gradient vectors. By combining the first and second derivatives the algorithm is able to take Newton-type steps towards the function minimum, assuming quadratic behavior in that region.

The bfgs2 version of this minimizer is the most efficient version available, and is a faithful implementation of the line minimization scheme described in Fletcher's Practical Methods of Optimization, Algorithms 2.6.2 and 2.6.4. It supercedes the original bfgs routine and requires substantially fewer function and gradient evaluations. The user-supplied tolerance tol corresponds to the parameter \sigma used by Fletcher. A value of 0.1 is recommended for typical use (larger values correspond to less accurate line searches).

frederic.degraeve (Bugzilla)

Re: optimizers

In reply to this post by Bianchetti Marco

Hello,

The architecture of QuantLib for optimization can be re-used, can't it? The main difference between

conjugate gradient and bfgs is only the update of the vector "lineSearch_->searchDirection()".

bfgs would re-use current "armijo linesearch". However, it is true that this case would need more

time for tests and also that no box constraints have been developed in QuantLib with conjugate gradient.

Regards,

Frédéric Degraeve

From: [hidden email] [mailto:[hidden email] ] On Behalf Of DU VIGNAUD DE VILLEFORT FRANCOIS GASAPRD PHI
Sent: mercredi 23 mai 2007 19:35
To: Bianchetti Marco; [hidden email]
Subject: Re: [Quantlib-dev] optimizers

Here is a good C++ implementation candidate,

http://www.alglib.net/optimization/lbfgs.php

Though, I'm not absolutely sure that the terms of use are compatible with those of QL.

François

Hello,

at the moment are available into QuantLib the following optimizers:

· Simplex (recently revisited: the Numerical Recipes implementation badly failed in finding the minimum of a 1D parabole...)

· Levenberg-Marquardt

· Conjugate Gradient

· Steepest Descent (still to be debugged, work in progress)

and we are currently considering the option to port into QuantLib the Broyden-Fletcher-Goldfarb-Shanno (BFGS2) algorithm, which in GSL is declared to be the best (see the text below). So:

· Any comment on the choice of BFGS2? do anyone has experience with it ?

· is anyone aware of an available open source C++ implementation to be ported into Quantlib with small effort ?

ciao

Marco

---

from: http://www.gnu.org/software/gsl/manual/html_node/Multimin-Algorithms.html

Minimizer: gsl_multimin_fdfminimizer_vector_bfgs2
Minimizer: gsl_multimin_fdfminimizer_vector_bfgs

These methods use the vector Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm. This is a quasi-Newton method which builds up an approximation to the second derivatives of the function f using the difference between successive gradient vectors. By combining the first and second derivatives the algorithm is able to take Newton-type steps towards the function minimum, assuming quadratic behavior in that region.

The bfgs2 version of this minimizer is the most efficient version available, and is a faithful implementation of the line minimization scheme described in Fletcher's Practical Methods of Optimization , Algorithms 2.6.2 and 2.6.4. It supercedes the original bfgs routine and requires substantially fewer function and gradient evaluations. The user-supplied tolerance tol corresponds to the parameter \sigma used by Fletcher. A value of 0.1 is recommended for typical use (larger values correspond to less accurate line searches).

Bianchetti Marco

Re: optimizers

In reply to this post by Bianchetti Marco

Francois:
François :

>Though, I'm not absolutely sure that the terms of use are compatible with those of QL.

They look ok, any comment ?

--- from http://www.alglib.net/copyrules.php ---
Use Conditions for Source Codes
9. Unless otherwise stated, the Source Codes shall be distributed on the basis of the terms and conditions, set out in this Document.
10. The visitor may include the Source Codes in the software (irrespective of the fact whether those software programs are commercial or not).
11. The visitor may modify the Source Codes on condition that the comments, which accompany them (including the link to the distribution terms and conditions), shall remain unchanged.
12. The visitor may distribute the software programs, which use various Source Codes. The distribution of the Source Codes is allowed only along with the program, which uses them. The visitor may not alter the distribution terms and conditions for the Source Codes.
13. When using any kind of the Source Codes, the link to ALGLIB Project is regarded as obligatory. In particular, when distributing the software programs, which use Source Codes, through the Internet, it is obligatory to use the hyperlink to the www.alglib.net at each page of the website, which distributes the software programs.
14. Any other ways of using the Source Codes are possible only under agreement with the author of ALGLIB Project.
---

Ciao
Marco

-----Original Message-----
From: DU VIGNAUD DE VILLEFORT FRANCOIS GASAPRD PHI
Sent: mercoledì 23 maggio 2007 19.35
To: Bianchetti Marco; [hidden email]
Subject: RE: [Quantlib-dev] optimizers

Here is a good C++ implementation candidate,

http://www.alglib.net/optimization/lbfgs.php

Though, I'm not absolutely sure that the terms of use are compatible with those of QL.
François

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Bianchetti Marco
Sent: Wednesday, May 23, 2007 6:13 PM
To: [hidden email]
Subject: [Quantlib-dev] optimizers

Hello,

at the moment are available into QuantLib the following optimizers:
· Simplex (recently revisited: the Numerical Recipes implementation badly failed in finding the minimum of a 1D parabole...)
· Levenberg-Marquardt
· Conjugate Gradient
· Steepest Descent (still to be debugged, work in progress)
and we are currently considering the option to port into QuantLib the Broyden-Fletcher-Goldfarb-Shanno (BFGS2) algorithm, which in GSL is declared to be the best (see the text below). So:
· Any comment on the choice of BFGS2? do anyone has experience with it ?
· is anyone aware of an available open source C++ implementation to be ported into Quantlib with small effort ?
Personally, I would prefer NOT to translate the GSL implementation from C to C++, because of the danger to introduce some tricky bug and because it requires a much more sophisticated test suite (and much work).

ciao
Marco

---
from: http://www.gnu.org/software/gsl/manual/html_node/Multimin-Algorithms.html
Minimizer: gsl_multimin_fdfminimizer_vector_bfgs2
Minimizer: gsl_multimin_fdfminimizer_vector_bfgs
These methods use the vector Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm. This is a quasi-Newton method which builds up an approximation to the second derivatives of the function f using the difference between successive gradient vectors. By combining the first and second derivatives the algorithm is able to take Newton-type steps towards the function minimum, assuming quadratic behavior in that region.
The bfgs2 version of this minimizer is the most efficient version available, and is a faithful implementation of the line minimization scheme described in Fletcher's Practical Methods of Optimization, Algorithms 2.6.2 and 2.6.4. It supercedes the original bfgs routine and requires substantially fewer function and gradient evaluations. The user-supplied tolerance tol corresponds to the parameter \sigma used by Fletcher. A value of 0.1 is recommended for typical use (larger values correspond to less accurate line searches).

-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Luigi Ballabio

Re: optimizers

On May 28, 2007, at 6:54 PM, Bianchetti Marco wrote:

>> Though, I'm not absolutely sure that the terms of use are compatible
>> with those of QL.
>
> They look ok, any comment ?
>
> --- from http://www.alglib.net/copyrules.php ---
> 13. When using any kind of the Source Codes, the link to ALGLIB
> Project is regarded as obligatory. In particular, when distributing
> the software programs, which use Source Codes, through the Internet,
> it is obligatory to use the hyperlink to the www.alglib.net at each
> page of the website, which distributes the software programs.

This looks problematic, especially since the QuantLib download page is
provided by Sourceforge without any way for us to provide such link.
Also a bit worrying is:

> 4. The requirements, set out in this Document, may be altered at any
> time, without any provisional notification. The visitor shall agree
> either to act in compliance with the altered requirements, or withdraw
> from using the data, obtained within the framework of ALGLIB Project.

Later,
Luigi

-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev

Ferdinando M. Ametrano-3

Re: optimizers

I will simplify for sake of clarity, but since we've adopted the BSD
license, nothing but BSD license is compatible with QuantLib. Anything
else would restrict the user freedom.

ciao -- Nando

PS I'm fully aware of GPL being free and being even more effective in
preserving freedom, but let's reserve this issue for another thread
;-)

On 5/28/07, Luigi Ballabio <[hidden email]> wrote:

>
> On May 28, 2007, at 6:54 PM, Bianchetti Marco wrote:
> >> Though, I'm not absolutely sure that the terms of use are compatible
> >> with those of QL.
> >
> > They look ok, any comment ?
> >
> > --- from http://www.alglib.net/copyrules.php ---
> > 13. When using any kind of the Source Codes, the link to ALGLIB
> > Project is regarded as obligatory. In particular, when distributing
> > the software programs, which use Source Codes, through the Internet,
> > it is obligatory to use the hyperlink to the www.alglib.net at each
> > page of the website, which distributes the software programs.
>
> This looks problematic, especially since the QuantLib download page is
> provided by Sourceforge without any way for us to provide such link.
> Also a bit worrying is:
>
> > 4. The requirements, set out in this Document, may be altered at any
> > time, without any provisional notification. The visitor shall agree
> > either to act in compliance with the altered requirements, or withdraw
> > from using the data, obtained within the framework of ALGLIB Project.
>
> Later,
> Luigi
>
>
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by DB2 Express
> Download DB2 Express C - the FREE version of DB2 express and take
> control of your XML. No limits. Just data. Click to get it now.
> http://sourceforge.net/powerbar/db2/
> _______________________________________________
> QuantLib-dev mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/quantlib-dev
>

alglib

Re: optimizers

Hello!

I've noticed your thread while checking indexing of alglib.net by Google.

As the author of the ALGLIB project I can inform you that these terms of use are going to change to less restrictive and more clear open-source license. I just haven't decided yet what license best suits needs of programming community. As for you and your project, you can use BFGS (and/or L-BFGS) source code under BSD license (without any additional requirements).

Best regards, Sergey Bochkanov.

Ferdinando M. Ametrano-3

Re: optimizers

Hi Sergey,

I'm not familiar with BFGS (and/or L-BFGS) and I can't find it in my
personal authoritative reference:
http://www.gnu.org/licenses/license-list.html

It would be very nice to have ALGLIB not only open source, but also
free software as in http://www.gnu.org/philosophy/free-sw.html

In any case I can't see QuantLib depending on any software which is
not free and/or not compatible with the GNU GPL

ciao -- Nando

On 6/3/07, alglib <[hidden email]> wrote:

>
> Hello!
>
> I've noticed your thread while checking indexing of alglib.net by Google.
>
> As the author of the ALGLIB project I can inform you that these terms of use
> are going to change to less restrictive and more clear open-source license.
> I just haven't decided yet what license best suits needs of programming
> community. As for you and your project, you can use BFGS (and/or L-BFGS)
> source code under BSD license (without any additional requirements).
>
> Best regards, Sergey Bochkanov.
> --
> View this message in context: http://www.nabble.com/optimizers-tf3805081.html#a10935893
> Sent from the quantlib-dev mailing list archive at Nabble.com.
>
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by DB2 Express
> Download DB2 Express C - the FREE version of DB2 express and take
> control of your XML. No limits. Just data. Click to get it now.
> http://sourceforge.net/powerbar/db2/
> _______________________________________________
> QuantLib-dev mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/quantlib-dev
>

alglib

Re: optimizers

Hello!

BFGS stands for "Broyden-Fletcher-Goldfarb-Shanno". It is algorithm name, not license name.

Original FORTRAN implementation of the L-BFGS algorithm was "freely available for educational or commercial purposes". As far as I can see it is compatible with BSD. I am not a lawyer but common sense tells me it is compatible.

I've put some restrictions on the use of the translated code (which were discussed above), but if you wish, you can use it under BSD (QuantLib uses BSD, isn't it?). You have a nice project and I would be glag to help you.

Ferdinando Ametrano wrote

Hi Sergey,

I'm not familiar with BFGS (and/or L-BFGS) and I can't find it in my
personal authoritative reference:
http://www.gnu.org/licenses/license-list.html

It would be very nice to have ALGLIB not only open source, but also
free software as in http://www.gnu.org/philosophy/free-sw.html

In any case I can't see QuantLib depending on any software which is
not free and/or not compatible with the GNU GPL

ciao -- Nando

Bianchetti Marco

Re: optimizers

In reply to this post by Bianchetti Marco

Thank you Sergey for the licensing of BFGS algo.
We put this task in our todo list (low priority indeeed), is it of
interest for you ?
I mean, just plugging BFGS into Quantlib, insipirated by the present
framework for optimizers (Simplex or Levenberg-Marquardt, for instance).
Let us know.
Regards
Marco

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf
> Of alglib
> Sent: 04 June 2007 14:05
> To: [hidden email]
> Subject: Re: [Quantlib-dev] optimizers
>
>
>
> Hello!
>
> BFGS stands for "Broyden-Fletcher-Goldfarb-Shanno". It is
> algorithm name,
> not license name.
>
> Original FORTRAN implementation of the L-BFGS algorithm was "freely
> available for educational or commercial purposes". As far as
> I can see it is
> compatible with BSD. I am not a lawyer but common sense tells me it is
> compatible.
>
> I've put some restrictions on the use of the translated code
> (which were
> discussed above), but if you wish, you can use it under BSD
> (QuantLib uses
> BSD, isn't it?). You have a nice project and I would be glag
> to help you.
>
>
> Ferdinando Ametrano wrote:
> >
> > Hi Sergey,
> >
> > I'm not familiar with BFGS (and/or L-BFGS) and I can't find it in my
> > personal authoritative reference:
> > http://www.gnu.org/licenses/license-list.html
> >
> > It would be very nice to have ALGLIB not only open source, but also
> > free software as in http://www.gnu.org/philosophy/free-sw.html
> >
> > In any case I can't see QuantLib depending on any software which is
> > not free and/or not compatible with the GNU GPL
> >
> > ciao -- Nando
> >