view release on metacpan or  search on metacpan

lbfgs.h  view on Meta::CPAN

 *	@param	x			The array of variables. A client program can set
 *						default values for the optimization and receive the
 *						optimization result through this array.
 *	@param	ptr_fx		The pointer to the variable that receives the final
 *						value of the objective function for the variables.
 *						This argument can be set to \c NULL if the final
 *						value of the objective function is unnecessary.
 *	@param	proc_evaluate	The callback function to provide function and
 *							gradient evaluations given a current values of
 *							variables. A client program must implement a
 *							callback function compatible with \ref
 *							lbfgs_evaluate_t and pass the pointer to the
 *							callback function.
 *	@param	proc_progress	The callback function to receive the progress
 *							(the number of iterations, the current value of
 *							the objective function) of the minimization
 *							process. This argument can be set to \c NULL if
 *							a progress report is unnecessary.
 *	@param	instance	A user data for the client program. The callback
 *						functions will receive the value of this argument.
 *	@param	param		The pointer to a structure representing parameters for
 *						L-BFGS optimization. A client program can set this
 *						parameter to \c NULL to use the default parameters.
 *						Call lbfgs_parameter_init() function to fill a
 *						structure with the default values.
 *	@retval	int			The status code. This function returns zero if the
 *						minimization process terminates without an error. A
 *						non-zero value indicates an error.
 */
int lbfgs(
	const int n,
	lbfgsfloatval_t *x,
	lbfgsfloatval_t *ptr_fx,
	lbfgs_evaluate_t proc_evaluate,
	lbfgs_progress_t proc_progress,
	void *instance,
	lbfgs_parameter_t *param
	);

/**
 * Initialize L-BFGS parameters to the default values.
 *
 *	Call this function to fill a parameter structure with the default values
 *	and overwrite parameter values if necessary.
 *
 *	@param	param		The pointer to the parameter structure.
 */
void lbfgs_parameter_init(lbfgs_parameter_t *param);

/** @} */

#ifdef	__cplusplus
}
#endif/*__cplusplus*/



/**
@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,
requires computation or approximation of the inverse of the hessian matrix of
the objective function in order to find the point where the gradient G(X) = 0.
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 approximates the inverse hessian matrix efficiently by using information
from last m iterations. This innovation saves the memory storage and
computational time a lot for large-scaled problems.

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>:
  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; compile the library with __SSE__ symbol
  defined to activate the optimization routine.

This library is used by the 
<a href="http://www.chokkan.org/software/crfsuite/">CRFsuite</a> project.

@section download Download

- <a href="http://www.chokkan.org/software/dist/liblbfgs-1.3.tar.gz">Source code</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.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 main.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 (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
  <a href="http://cctbx.sourceforge.net/current_cvs/c_plus_plus/namespacescitbx_1_1lbfgs.html">scitbx::lbfgs</a>.
*/

#endif/*__LBFGS_H__*/