Algorithm-LBFGS
view release on metacpan or search on metacpan
- A totally refactoring
- uses liblbfgs instead of the f2c version of lbfgs.f
- removed the dependency of libf2c
- broke the former API
- Object oriented and thread safe
0.02 Fri Jan 11 14:22:00 2008
- corrected some documentation typos
0.01 Tue Jan 8 15:31:18 2008
- original version; created by h2xs 1.23 with options
-An Algorithm::LBFGS
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
/* $Id: lbfgs.c 56 2007-12-16 08:01:47Z naoaki $ */
/*
This library is a C port of the FORTRAN implementation of Limited-memory
Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) method written by Jorge Nocedal.
The original FORTRAN source code is available at:
http://www.ece.northwestern.edu/~nocedal/lbfgs.html
The L-BFGS algorithm is described in:
- Jorge Nocedal.
Updating Quasi-Newton Matrices with Limited Storage.
<i>Mathematics of Computation</i>, Vol. 35, No. 151, pp. 773--782, 1980.
- Dong C. Liu and Jorge Nocedal.
On the limited memory BFGS method for large scale optimization.
<i>Mathematical Programming</i> B, Vol. 45, No. 3, pp. 503-528, 1989.
<i>ACM Transactions on Mathematical Software (TOMS)</i>, Vol. 20, No. 3,
pp. 286-307, 1994.
This library also implements Orthant-Wise Limited-memory Quasi-Newton (OW-LQN)
method presented in:
- Galen Andrew and Jianfeng Gao.
Scalable training of L1-regularized log-linear models.
In <i>Proceedings of the 24th International Conference on Machine
Learning (ICML 2007)</i>, pp. 33-40, 2007.
I would like to thank the original author, Jorge Nocedal, who has been
distributing the effieicnt and explanatory implementation in an open source
licence.
*/
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif/*HAVE_CONFIG_H*/
#include <stdio.h>
#include <stdlib.h>
/**
@mainpage C port of Limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS)
@section intro Introduction
This library is a C port of the implementation of Limited-memory
Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) method written by Jorge Nocedal.
The original FORTRAN source code is available at:
http://www.ece.northwestern.edu/~nocedal/lbfgs.html
The L-BFGS method solves the unconstrainted minimization problem,
<pre>
minimize F(x), x = (x1, x2, ..., xN),
</pre>
only if the objective function F(x) and its gradient G(x) are computable. The
Newton's method, which is a well-known algorithm for the optimization,
Among the various ports of L-BFGS, this library provides several features:
- <b>Optimization with L1-norm (orthant-wise L-BFGS)</b>:
In addition to standard minimization problems, the library can minimize
a function F(x) combined with L1-norm |x| of the variables,
{F(x) + C |x|}, where C is a constant scalar parameter. This feature is
useful for estimating parameters of log-linear models with L1-regularization.
- <b>Clean C code</b>:
Unlike C codes generated automatically by f2c (Fortran 77 into C converter),
this port includes changes based on my interpretations, improvements,
optimizations, and clean-ups so that the ported code would be well-suited
for a C code. In addition to comments inherited from the original code,
a number of comments were added through my interpretations.
- <b>Callback interface</b>:
The library receives function and gradient values via a callback interface.
The library also notifies the progress of the optimization by invoking a
callback function. In the original implementation, a user had to set
function and gradient values every time the function returns for obtaining
updated values.
- <b>Thread safe</b>:
The library is thread-safe, which is the secondary gain from the callback
interface.
- <b>Cross platform.</b> The source code can be compiled on Microsoft Visual
Studio 2005, GNU C Compiler (gcc), etc.
- <b>Configurable precision</b>: A user can choose single-precision (float)
or double-precision (double) accuracy by changing ::LBFGS_FLOAT macro.
- <b>SSE/SSE2 optimization</b>:
<i>ACM Transactions on Mathematical Software (TOMS)</i>, Vol. 20, No. 3,
pp. 286-307, 1994.
This library also implements Orthant-Wise Limited-memory Quasi-Newton (OW-LQN)
method presented in:
- Galen Andrew and Jianfeng Gao.
Scalable training of L1-regularized log-linear models.
In <i>Proceedings of the 24th International Conference on Machine
Learning (ICML 2007)</i>, pp. 33-40, 2007.
Finally I would like to thank the original author, Jorge Nocedal, who has been
distributing the effieicnt and explanatory implementation in an open source
licence.
@section reference Reference
- <a href="http://www.ece.northwestern.edu/~nocedal/lbfgs.html">L-BFGS</a> by Jorge Nocedal.
- <a href="http://research.microsoft.com/research/downloads/Details/3f1840b2-dbb3-45e5-91b0-5ecd94bb73cf/Details.aspx">OWL-QN</a> by Galen Andrew.
- <a href="http://chasen.org/~taku/software/misc/lbfgs/">C port (via f2c)</a> by Taku Kudo.
- <a href="http://www.alglib.net/optimization/lbfgs.php">C#/C++/Delphi/VisualBasic6 port</a> in ALGLIB.
- <a href="http://cctbx.sourceforge.net/">Computational Crystallography Toolbox</a> includes
( run in 0.940 second using v1.01-cache-2.11-cpan-1c8d708658b )