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. This is 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.

Download

The source code of the current version of the library can be downloaded from https://github.com/mkobos/lbfgsb_wrapper or retrieved straight from the Git repository with 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

• The library was developed with Linux operating system in mind (the code was tested on Ubuntu 16.04 system and on some older versions of Ubuntu) but it can also be made to work on MacOS and Windows (see the section "Building from source files" for details).
• gcc and gfortran compilers (Ubuntu packages: build-essential and gfortran)
• SWIG program/library (Ubuntu package: swig)
• Java JDK 8 (but the code should work with slightly older versions of JDK as well) 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)

The most important source files

• bin - directory with scripts that show how to run 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

General commands:

• 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.

Linux

On Linux, it should work out of the box if the required tools are present (see the "Requirements" section).

MacOSX

On MacOSX, 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

Windows

If you want build the sources on Linux so the resulting binaries work on Windows (tested on Ubuntu 16.04 and Windows 10), this is what you need to do (for a case of a 64-bit Ubuntu system and a 64-bit Windows system):

• Install package gfortran-mingw-w64 (some other required packages should be automatically pulled as dependencies).

• Download Windows JNI headers (because these are usually not packaged) to the root directory of the project:

    if [ ! -d jni_include ] ; then
      mkdir -p jni_include/win32 || exit 1
      cd jni_include/win32
      wget http://hg.openjdk.java.net/jdk6/jdk6/jdk/raw-file/ac1d168048bd/src/windows/javavm/export/jni_md.h || exit 1
      wget http://hg.openjdk.java.net/jdk6/jdk6/jdk/raw-file/ac1d168048bd/src/windows/javavm/export/jawt_md.h || exit 1
      cd ../..
    fi
  

• Set an environment variable to be used later: JNI_ARCH_DIR=$(pwd)/jni_include/win32

• Compile the library using cross-compilers (these are given as CC and FC parameters): ant -Diswindows=1 -DCC=x86_64-w64-mingw32-gcc -DFC=x86_64-w64-mingw32-gfortran -DJNI_ARCH_DIR="$JNI_ARCH_DIR" -DLIB_DEPENDENCIES="-Wl,-Bstatic -lgfortran -lquadmath -lpthread -static-libgcc"

  • Note that this command compiles a number of libraries statically using the -Wl,-Bstatic switch. This is done so you don't have to put Windows versions of these libraries (as *.dll files) in PATH environmental variable under Windows for the library to work.
  • If you want easily distributable binaries, you can avoid linking statically libquadmath using the following trick: -DLIB_DEPENDENCIES="-Wl,--defsym,${UNDERSCORE}quadmath_snprintf=${UNDERSCORE}abort -Wl,-Bstatic -lgfortran -lpthread -static-libgcc" where UNDERSCORE= (i.e. empty) on x86_64, UNDERSCORE=_ on i*86, which means you don't have to ship the whole LGPLed libquadmath sources with your binaries (and actually, also the source code of everything else that you statically linked, including libgfortran, to allow for relinking with a modified libquadmath) just for a single function that is never even actually called (libgfortran and libgcc are under the GPL with GCC runtime exception, and winpthread under a BSD license, which means you are not obligated to ship any sources for those libraries with statically-linked binaries.).

If you want to build the tests on Linux and then run them on Windows you need to:

1. On Linux: compile the tests for Windows: ant -Diswindows=1 -DCC=x86_64-w64-mingw32-gcc -DFC=x86_64-w64-mingw32-gfortran -DJNI_ARCH_DIR="$JNI_ARCH_DIR" -DLIB_DEPENDENCIES="-Wl,-Bstatic -lgfortran -lquadmath -lpthread -static-libgcc" test-compile
2. On Windows: run compiled tests from the root directory of the project: bin/windows_test_without_compiling.bat dist/lbfgsb_wrapper-1.1.3-SNAPSHOT.jar (you need to change the name of the JAR file appropriately)

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