kkofler / lbfgsb_wrapper

Java wrapper for the Fortran L-BFGS-B algorithm

Java wrapper for the Fortran L-BFGS-B algorithm

by Mateusz Kobos

Introduction

L-BFGS-B is a limited-memory quasi-Newton optimization algorithm for solving large nonlinear optimization problems with simple bounds on the variables [Zhu97]. It employs function's value and gradient information to search for the local optimum. It uses (as the name suggests) the BGFS (Broyden-Goldfarb-Fletcher-Shanno) algorithm to approximate the Hessian. The size of the memory available to store the approximation of the Hessian is limited and is a parameter of the algorithm. Each of the x_i variables of the optimized function can be bounded i.e. we can define such numbers l_i and u_i that l_i <= x_i <= u_i.

The original implementation of the algorithm is written in the Fortran language and is available on the authors' original distribution website. I have developed a Java wrapper library for the Fortran code. The wrapper library uses JNI with SWIG to create the proxy code. A by-product of the Java wrapper is a quite low-level C wrapper for the Fortran code. In short, the structure of the wrapping layers looks as follows: Fortran -> C -> JNI by SWIG -> Java.

If you have any comments, questions, bug reports, bug fixes, etc., please contact the author.

Download

The current version of the library can be downloaded as a binary (64-bit or 32-bit version) or source package from https://github.com/mkobos/lbfgsb_wrapper/downloads.

The stable version of the source can be also retrieved straight from the Git repository: git clone [email protected]:mkobos/lbfgsb_wrapper.git.

Reliability

• I compared the behavior of the original Fortran algorithm and Java wrapper using a couple of popular minimization problems. Apparently, sometimes there are some minor differences in the results (starting for example from 5th significant digit). I suspect that the reason of such discrepancies is a different machine precision that is automatically set by the Fortran program when the code is called natively from Fortran and when it's called by Java wrapper. E.g. on my computer, the machine precision set by the program when called natively from Fortran is 1.084E-19, but when called by Java wrapper: 2.220E-16.
• The code was tested on some benchmark minimization problems (see JUnit tests in the source package). Test functions for unbounded optimization (along with starting points and expected optimal points) were taken from [More81]. The bounds and expected function values for bounded optimization problem were taken from [Neumaier08]. It seems that program is able to find appropriate minima for all of the tested functions except of the Powell Badly Scaled Function. My guess is that it might be related to an insufficient machine precision when called from Java wrapper as the function is very flat near the minimum (cf. [Kuntsevich08]).

License and conditions of use

• The wrapper program is available under simplified BSD license (see file license.txt in the distribution package for the text of the license).
• The wrapper uses the original Fortran implementation which is included in the distribution packages. This Fortran code can be used in accordance with conditions available on the authors' original distribution website.

Requirements

• Linux operating system (the code was tested on Ubuntu 8.10, 9.04, 9.10, 10.04, 10.10, 11.10 and 12.04 systems)
• gcc and gfortran compilers (Ubuntu packages: build-essential and gfortran)
• SWIG program/library (Ubuntu package: swig)
• Java JDK 6 (the code should also work with JDK 1.5) with environmental variable JAVA_HOME properly set
• Apache Ant

Example usage

In the following code (see SampleRun.java file in the source package), we want to minimize simple quadratic function (x+4)^2. Only the lower bound is set and it is set to x=10. The start point is x=40.

package lbfgsb;

import java.util.ArrayList;

public class SampleRun {
	public static void main(String[] args){
		try {
			QuadraticFun fun = new QuadraticFun();
			Minimizer alg = new Minimizer();
			ArrayList<Bound> bounds = new ArrayList<Bound>();
			bounds.add(new Bound(new Double(10), null));
			alg.setBounds(bounds);
			Result result = alg.run(fun, new double[]{40});
			System.out.println("The final result: "+result);
		} catch (LBFGSBException e) {
			e.printStackTrace();
		}
	}
}

class QuadraticFun implements DifferentiableFunction{
	public FunctionValues getValues(double[] point){
		double p = point[0];
		System.out.println("Calculating function for x="+p);
		return new FunctionValues(Math.pow(p+4, 2), 
				new double[]{2*(p+4)});
	}
}

After executing the code, we obtain the following output:

Calculating function for x=40.0
Calculating function for x=39.0
Calculating function for x=35.0
Calculating function for x=10.0
The final result: point=[10.0], functionValue=196.0, gradient=[28.0], 
	iterationsInfo=(iterations=2, functionEvaluations=4, stopType=OTHER_STOP_CONDITIONS, 
		stateDescription=CONVERGENCE: NORM OF PROJECTED GRADIENT <= PGTOL)

Handling source package

The most important files

See:

• run1.sh and run2.sh scripts for an example of how to execute some simple code that uses the library
• changes.mkd for list of changes in subsequent releases
• license.txt for the text of the BSD license for this library

Building from source files

• ant - create the library and javadocs
• ant test - run tests using some popular minimization problems

Warning: the JAVA_HOME environment variable has to be properly set since it is used while compiling the liblbfgsb_wrapper.so library.

MacOSX

On OSX, these are the additional steps you may need to execute before building the project with ant succeeds:

• Install gfortran from http://hpc.sourceforge.net or http://sourceforge.net/projects/hpc/files/hpc/g95/gfortran-mlion.tar.gz
• sudo port install swig
• sudo port install swig-java
• If building the project with ant fails with a message "jni.h can't be found", execute the following steps:
  • make sure that JAVA_HOME is set properly, i.e. that JAVA_HOME=/Library/Java/Home,
  • execute: ln -s /System/Library/Frameworks/JavaVM.framework/Headers /Library/Java/Home/include (this is because jni.h lives in /System/Library/Frameworks/JavaVM.framework/Headers).
• Build the project with ant and rename .so file to .dylib: mv liblbfgsb_wrapper.so liblbfgsb_wrapper.dylib

References

• [More81] Jorge J. Moré, Burton S. Garbow, Kenneth E. Hillstrom, "Testing Unconstrained Optimization Software", ACM Transactions on Mathematical Software, 1981
• [Neumaier08] Arnold Neumaier, Minimum Function Values for the Moré et al. Test Set access time: 2008-12-23
• [Kuntsevich08] Alexei Kuntsevich, Franz Kappel, Moré set of test functions, access time: 2008-12-23
• [Zhu97] C. Zhu, R. H. Byrd and J. Nocedal. L-BFGS-B: Algorithm 778: L-BFGS-B, FORTRAN routines for large scale bound constrained optimization (1997), ACM Transactions on Mathematical Software, Vol 23, Num. 4, pp. 550 - 560