by Mateusz Kobos
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.
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 git@github.com:mkobos/lbfgsb_wrapper.git.
- 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]).
- The wrapper program is available under simplified BSD license (see file
license.txtin 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.
- 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-essentialandgfortran) - SWIG program/library (Ubuntu package:
swig) - Java JDK 6 (the code should also work with JDK 1.5) with environmental variable
JAVA_HOMEproperly set - Apache Ant
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)
See:
run1.shandrun2.shscripts for an example of how to execute some simple code that uses the librarychanges.mkdfor list of changes in subsequent releaseslicense.txtfor the text of the BSD license for this library
ant- create the library and javadocsant test- run tests using some popular minimization problems- on OSX these are the additional things you may need before
antwill succeed.- install gfortran from (http://hpc.sourceforge.net) or (http://sourceforge.net/projects/hpc/files/hpc/g95/gfortran-mlion.tar.gz)
sudo port install swigsudo port install swig-java- jni.h can't be found..
export JAVA_HOME=/Library/Java/Homejni.h lives in: /System/Library/Frameworks/JavaVM.framework/Headersln -s /System/Library/Frameworks/JavaVM.framework/Headers /Library/Java/Home/include - build with ant and rename .so to .dylib:
mv liblbfgsb_wrapper.so liblbfgsb_wrapper.dylib
Warning: the JAVA_PATH environment variable has to be properly set since it is used while compiling the liblbfgsb_wrapper.so library.
- [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