bozo

Bozo is a Clojure wrapper for the L-BFGS optimization algorithm.

L-BFGS

Limited-memory BFGS (L-BFGS or LM-BFGS) is an optimization algorithm in the family of quasi-Newton methods that approximates the Broyden- Fletcher-Goldfarb-Shanno (BFGS) algorithm using a limited amount of computer memory. It is a popular algorithm for parameter estimation in machine learning. -- Wikipedia Limited-memory BFGS

Usage

Add the following to your :dependencies in project.clj:

    [bozo/bozo "0.1.1"]

Then, you can call the optimizer as follows:

    (lbfgs f x0)

Assuming f is the function to minimize, starting with an initial estimate x0.
f should take a parameter x (double array) as argument, and return a pair including:

• the value of f at x (double value)
• the value of the derivative of f wrt each component of x at x (double array of same size as x)

There are several optional parameters:

• :maxit the maximum number of iterations (default 200).
• :m the number of corrections used in the BFGS update (default 5).
  • values of m less than 3 are not recommended;
  • large values of m will result in excessive computing time.
  • 3 <= m <= 7 is recommended. Restriction: m > 0.
• :eps accuracy with which the solution is to be found (default 1.0e-5).
• :xtol estimate of the machine precision (default 1.0e-16).
• :iprint pair [i1 i2] to specify the output generated by lbfgs (default [-1 0]).
  • i1 specifies the frequency of the output:
    • i1 < 0: no output is generated,
    • i1 = 0: output only at first and last iteration,
    • i1 > 0: output every i1 iterations.
  • i2 specifies the type of output generated:
    • i2 = 0: iteration count, number of function evaluations, function value, norm of the gradient, and steplength,
    • i2 = 1: same as i2 = 0, plus vector of variables and gradient vector at the initial point,
    • i2 = 2: same as i2 = 1, plus vector of variables,
    • i2 = 3: same as i2 = 2, plus gradient vector.

Override the defaults like this:

    (lbfgs f x0 {:m 3})

The original LBFGS also has other options, such as allowing to specify ones own Hk0 (Hessian diagonal elements), but they are not (yet) exposed in bozo.

How does it work?

If you want to learn more about the algorithm, you could check the Java source code, which contains a lot of comments (including original comments from the Fortran code).

Recommended reading:

D. C. Liu and J. Nocedal, ''On the limited memory BFGS method for large scale optimization methods'' Mathematical Programming 45 (1989), pp. 503-528. (Postscript file of this paper is available via anonymous ftp to eecs.nwu.edu in the directory pub/lbfgs/lbfgs_um.)

Why is it called Bozo?

Let "Bozo" Find a Good Solution to your optimization problem...

License

Authors:

• Jorge Nocedal: original Fortran version (including comments), July 1990.
• Robert Dodier: Java translation, August 1997.
• Antoine Choppin: Clojure wrapper, May 2014.

Licensed under the Apache License, Version 2.0