Skip to content

Commit

Permalink
drop doxygen mainpage from liblbfgs (clashes with shogun mainpage)
Browse files Browse the repository at this point in the history
  • Loading branch information
Soeren Sonnenburg committed Jun 28, 2012
1 parent d1ee078 commit 11eba43
Showing 1 changed file with 0 additions and 219 deletions.
219 changes: 0 additions & 219 deletions src/shogun/optimization/lbfgs/lbfgs.h
View file
Expand Up @@ -471,223 +471,4 @@ void lbfgs_parameter_init(lbfgs_parameter_t *param);

} // namespace shogun

/**
@mainpage libLBFGS: a library 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
well-known Newton's method requires computation of the inverse of the hessian
matrix of the objective function. However, the computational cost for the
inverse hessian matrix is expensive especially when the objective function
takes a large number of variables. The L-BFGS method iteratively finds a
minimizer by approximating the inverse hessian matrix by information from last
m iterations. This innovation saves the memory storage and computational time
drastically for large-scaled problems.
Among the various ports of L-BFGS, this library provides several features:
- <b>Optimization with L1-norm (Orthant-Wise Limited-memory Quasi-Newton
(OWL-QN) method)</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 sparse log-linear models (e.g.,
logistic regression and maximum entropy) with L1-regularization (or
Laplacian prior).
- <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 2010, 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>:
This library includes SSE/SSE2 optimization (written in compiler intrinsics)
for vector arithmetic operations on Intel/AMD processors. The library uses
SSE for float values and SSE2 for double values. The SSE/SSE2 optimization
routine is disabled by default.
This library is used by:
- <a href="http://www.chokkan.org/software/crfsuite/">CRFsuite: A fast implementation of Conditional Random Fields (CRFs)</a>
- <a href="http://www.chokkan.org/software/classias/">Classias: A collection of machine-learning algorithms for classification</a>
- <a href="http://www.public.iastate.edu/~gdancik/mlegp/">mlegp: an R package for maximum likelihood estimates for Gaussian processes</a>
- <a href="http://infmath.uibk.ac.at/~matthiasf/imaging2/">imaging2: the imaging2 class library</a>
- <a href="http://search.cpan.org/~laye/Algorithm-LBFGS-0.16/">Algorithm::LBFGS - Perl extension for L-BFGS</a>
- <a href="http://www.cs.kuleuven.be/~bernd/yap-lbfgs/">YAP-LBFGS (an interface to call libLBFGS from YAP Prolog)</a>
@section download Download
- <a href="https://github.com/downloads/chokkan/liblbfgs/liblbfgs-1.10.tar.gz">Source code</a>
- <a href="https://github.com/chokkan/liblbfgs">GitHub repository</a>
libLBFGS is distributed under the term of the
<a href="http://opensource.org/licenses/mit-license.php">MIT license</a>.
@section changelog History
- Version 1.10 (2010-12-22):
- Fixed compiling errors on Mac OS X; this patch was kindly submitted by
Nic Schraudolph.
- Reduced compiling warnings on Mac OS X; this patch was kindly submitted
by Tamas Nepusz.
- Replaced memalign() with posix_memalign().
- Updated solution and project files for Microsoft Visual Studio 2010.
- Version 1.9 (2010-01-29):
- Fixed a mistake in checking the validity of the parameters "ftol" and
"wolfe"; this was discovered by Kevin S. Van Horn.
- Version 1.8 (2009-07-13):
- Accepted the patch submitted by Takashi Imamichi;
the backtracking method now has three criteria for choosing the step
length:
- ::LBFGS_LINESEARCH_BACKTRACKING_ARMIJO: sufficient decrease (Armijo)
condition only
- ::LBFGS_LINESEARCH_BACKTRACKING_WOLFE: regular Wolfe condition
(sufficient decrease condition + curvature condition)
- ::LBFGS_LINESEARCH_BACKTRACKING_STRONG_WOLFE: strong Wolfe condition
- Updated the documentation to explain the above three criteria.
- Version 1.7 (2009-02-28):
- Improved OWL-QN routines for stability.
- Removed the support of OWL-QN method in MoreThuente algorithm because
it accidentally fails in early stages of iterations for some objectives.
Because of this change, <b>the OW-LQN method must be used with the
backtracking algorithm (::LBFGS_LINESEARCH_BACKTRACKING)</b>, or the
library returns ::LBFGSERR_INVALID_LINESEARCH.
- Renamed line search algorithms as follows:
- ::LBFGS_LINESEARCH_BACKTRACKING: regular Wolfe condition.
- ::LBFGS_LINESEARCH_BACKTRACKING_LOOSE: regular Wolfe condition.
- ::LBFGS_LINESEARCH_BACKTRACKING_STRONG: strong Wolfe condition.
- Source code clean-up.
- Version 1.6 (2008-11-02):
- Improved line-search algorithm with strong Wolfe condition, which was
contributed by Takashi Imamichi. This routine is now default for
::LBFGS_LINESEARCH_BACKTRACKING. The previous line search algorithm
with regular Wolfe condition is still available as
::LBFGS_LINESEARCH_BACKTRACKING_LOOSE.
- Configurable stop index for L1-norm computation. A member variable
::lbfgs_parameter_t::orthantwise_end was added to specify the index
number at which the library stops computing the L1 norm of the
variables. This is useful to prevent some variables from being
regularized by the OW-LQN method.
- A sample program written in C++ (sample/sample.cpp).
- Version 1.5 (2008-07-10):
- Configurable starting index for L1-norm computation. A member variable
::lbfgs_parameter_t::orthantwise_start was added to specify the index
number from which the library computes the L1 norm of the variables.
This is useful to prevent some variables from being regularized by the
OWL-QN method.
- Fixed a zero-division error when the initial variables have already
been a minimizer (reported by Takashi Imamichi). In this case, the
library returns ::LBFGS_ALREADY_MINIMIZED status code.
- Defined ::LBFGS_SUCCESS status code as zero; removed unused constants,
LBFGSFALSE and LBFGSTRUE.
- Fixed a compile error in an implicit down-cast.
- Version 1.4 (2008-04-25):
- Configurable line search algorithms. A member variable
::lbfgs_parameter_t::linesearch was added to choose either MoreThuente
method (::LBFGS_LINESEARCH_MORETHUENTE) or backtracking algorithm
(::LBFGS_LINESEARCH_BACKTRACKING).
- Fixed a bug: the previous version did not compute psuedo-gradients
properly in the line search routines for OWL-QN. This bug might quit
an iteration process too early when the OWL-QN routine was activated
(0 < ::lbfgs_parameter_t::orthantwise_c).
- Configure script for POSIX environments.
- SSE/SSE2 optimizations with GCC.
- New functions ::lbfgs_malloc and ::lbfgs_free to use SSE/SSE2 routines
transparently. It is uncessary to use these functions for libLBFGS built
without SSE/SSE2 routines; you can still use any memory allocators if
SSE/SSE2 routines are disabled in libLBFGS.
- Version 1.3 (2007-12-16):
- An API change. An argument was added to lbfgs() function to receive the
final value of the objective function. This argument can be set to
\c NULL if the final value is unnecessary.
- Fixed a null-pointer bug in the sample code (reported by Takashi Imamichi).
- Added build scripts for Microsoft Visual Studio 2005 and GCC.
- Added README file.
- Version 1.2 (2007-12-13):
- Fixed a serious bug in orthant-wise L-BFGS.
An important variable was used without initialization.
- Version 1.1 (2007-12-01):
- Implemented orthant-wise L-BFGS.
- Implemented lbfgs_parameter_init() function.
- Fixed several bugs.
- API documentation.
- Version 1.0 (2007-09-20):
- Initial release.
@section api Documentation
- @ref liblbfgs_api "libLBFGS API"
@section sample Sample code
@include sample.c
@section ack Acknowledgements
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.
The line search algorithms used in this implementation are described in:
- John E. Dennis and Robert B. Schnabel.
<i>Numerical Methods for Unconstrained Optimization and Nonlinear
Equations</i>, Englewood Cliffs, 1983.
- Jorge J. More and David J. Thuente.
Line search algorithm with guaranteed sufficient decrease.
<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 (OWL-QN)
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.
Special thanks go to:
- Yoshimasa Tsuruoka and Daisuke Okanohara for technical information about
OWL-QN
- Takashi Imamichi for the useful enhancements of the backtracking method
- Kevin S. Van Horn, Nic Schraudolph, and Tamas Nepusz for bug fixes
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/en-us/downloads/b1eb1016-1738-4bd5-83a9-370c9d498a03/default.aspx">Orthant-Wise Limited-memory Quasi-Newton Optimizer for L1-regularized Objectives</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
<a href="http://cctbx.sourceforge.net/current_cvs/c_plus_plus/namespacescitbx_1_1lbfgs.html">scitbx::lbfgs</a>.
*/

#endif/*__LBFGS_H__*/

0 comments on commit 11eba43

Please sign in to comment.