Re: [Quantlib-dev] optimizers

[<fre...@gm...>]

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=E9d=E9ric Degraeve


 ------------------------------

*From:* qua...@li... [mailto:
qua...@li...] *On Behalf Of *DU VIGNAUD DE
VILLEFORT FRANCOIS GASAPRD PHI
*Sent:* mercredi 23 mai 2007 19:35
*To:* Bianchetti Marco; qua...@li...
*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=E7ois



-----Original Message-----
*From:* qua...@li... [mailto:
qua...@li...] *On Behalf Of *Bianchetti Marco
*Sent:* Wednesday, May 23, 2007 6:13 PM
*To:* qua...@li...
*Subject:* [Quantlib-dev] optimizers



Hello,



at the moment are available into QuantLib the following optimizers:

=B7         Simplex (recently revisited: the Numerical Recipes implementati=
on
badly failed in finding the minimum of a 1D parabole...)

=B7         Levenberg-Marquardt

=B7         Conjugate Gradient

=B7         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:

=B7         Any comment on the choice of BFGS2? do anyone has experience wi=
th
it ?

=B7         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 t=
o
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 t=
o
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
tolcorresponds 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).