A new optimization problem required a black box solver that could impose constant bounds on the variables. We opted to use an implementation of L-BFGS-B which does exactly that.
I’m working on a Mac OS X, 10.6, machine and our code base is in c++. So I needed to compile the L-BFGS-B code, which is in fortran and be able to call it from cpp files.
Compiling L-BFGS-B
Note: the following solution requires that you have a proper f2c installed. I used these steps to compile a universal (32-bit and 64-bit) f2c.
Download the source.
You’ll notice there are four *.f files:
routines.f contains the solver
driver*.f contain examples showing you how to set up the parameters to the solver
The Makefile included in the source will try to compile all four files into *.o object files then make executables out of each example. When I try:
make
it seems that while the object files for each *.f file get created, my f77 doesn’t understand how to make the executables. I get errors like this:
f77 -O driver3.o routines.o -o x.lbfgsb3
invalid parameter driver3.o
Undefined symbols:
"_MAIN__", referenced from:
_main in libf2c.a(main.o)
ld: symbol(s) not found
collect2: ld returned 1 exit status
This would be OK because I don’t really care about the example executables. But in order to figure out how to call subroutines from routines.o from C/C++, I’ll need to know that they work in the first place. Moreover, f77 was creating x86_64 object files and my code base is i386 (though I’m trying my hardest to build the dependencies as universals).
After digging around in the F77 script I first found where I could tell the compiler to make universal binaries. I do that by setting the CFLAGS environment variable. So as a replacement for the faulty Makefile, I’ve composed this script which should do the same thing but make everything universal for the mac:
Save this in the same directory as the *.f files as make_all.sh:
#!/bin/bash
# save old CFLAGS value
OLD_CFLAGS=$CFLAGS;
# set CFLAGS used by F77 to contain gcc parameters necessary to produce
# universal object files
export CFLAGS="$CFLAGS -arch i386 -arch x86_64";
# compile the algorithm as a universal object file
f77 -O -c -o routines.o routines.f
# compile each of the examples as universal executables
for i in 1 2 3
do
# translate driver*.f to driver*.c
f2c driver$i.f
# compile driver*.c to universal binary driver*.o
cc $CFLAGS -c -o driver$i.o driver$i.c
# link driver*.o and routines.o into unversal binary executable x.lbfgsb*
cc $CFLAGS driver$i.o routines.o -lf2c -lm -o x.lbfgsb$i
# remove driver*.c
rm driver$i.c
done
# restore old CFLAGS value
export CFLAGS='$OLD_CFLAGS';
Call it by issuing:
bash make_all.sh
You can test that everything went ok by executing ./x.lbfgsb1, ./x.lbfgsb2, ./x.lbfgsb3.
Mixing with C++
Now that we have a universal routines.o, we would like to be able to call the algorithm subroutines from a c++ program.
I could use f2c to “translate driver1.f” into c++, but all it does is translate it into c and put it in an extern "C" block. Instead I used f2c to translate driver1.f into c code, then methodically human-translated that into a (more) human-readable cpp program.
Below is my human readable version of driver1.f. Save it in a file called driver1.cpp:
/* driver1.f -- translated by f2c (version 20090411).
You must link the resulting object file with libf2c:
on Microsoft Windows system, link with libf2c.lib;
on Linux or Unix systems, link with .../path/to/libf2c.a -lm
or, if you install libf2c.a in a standard place, with -lf2c -lm
-- in that order, at the end of the command line, as in
cc *.o -lf2c -lm
Source for libf2c is in /netlib/f2c/libf2c.zip, e.g.,
http://www.netlib.org/f2c/libf2c.zip
*/
// Compile this with
// !c++ routines.o -lf2c -lm -o driver1cpp driver1.cpp
#include "f2c.h"
#include "stdio.h"
/* DRIVER 1 */
/* -------------------------------------------------------------- */
/* SIMPLE DRIVER FOR L-BFGS-B (version 2.1) */
/* -------------------------------------------------------------- */
/* L-BFGS-B is a code for solving large nonlinear optimization */
/* problems with simple bounds on the variables. */
/* The code can also be used for unconstrained problems and is */
/* as efficient for these problems as the earlier limited memory */
/* code L-BFGS. */
/* This is the simplest driver in the package. It uses all the */
/* default settings of the code. */
/* References: */
/* [1] R. H. Byrd, P. Lu, J. Nocedal and C. Zhu, ``A limited */
/* memory algorithm for bound constrained optimization'', */
/* SIAM J. Scientific Computing 16 (1995), no. 5, pp. 1190--1208. */
/* [2] C. Zhu, R.H. Byrd, P. Lu, J. Nocedal, ``L-BFGS-B: FORTRAN */
/* Subroutines for Large Scale Bound Constrained Optimization'' */
/* Tech. Report, NAM-11, EECS Department, Northwestern University, */
/* 1994. */
/* (Postscript files of these papers are available via anonymous */
/* ftp to eecs.nwu.edu in the directory pub/lbfgs/lbfgs_bcm.) */
/* * * * */
/* NEOS, November 1994. (Latest revision June 1996.) */
/* Optimization Technology Center. */
/* Argonne National Laboratory and Northwestern University. */
/* Written by */
/* Ciyou Zhu */
/* in collaboration with R.H. Byrd, P. Lu-Chen and J. Nocedal. */
/* NOTE: The user should adapt the subroutine 'timer' if 'etime' is */
/* not available on the system. An example for system */
/* AIX Version 3.2 is available at the end of this driver. */
// These are fortran wrappers and must be in C
extern "C" {
int setulb_(integer *, integer *, doublereal *,
doublereal *, doublereal *, integer *, doublereal *, doublereal *,
doublereal *, doublereal *, doublereal *, integer *, char *,
integer *, char *, logical *, integer *, doublereal *, ftnlen,
ftnlen);
/* Builtin functions */
integer s_wsfe(cilist *), e_wsfe(void);
/* Subroutine */ int s_copy(char *, char *, ftnlen, ftnlen);
integer s_cmp(char *, char *, ftnlen, ftnlen);
/* Subroutine */ int s_stop(char *, ftnlen);
}
/* ************** */
/* Main program */
int main(void)
{
/* Local variables */
doublereal f, g[1024];
doublereal l[1024];
integer m, n;
doublereal u[1024], x[1024], t1, t2, wa[42584];
integer nbd[1024], iwa[3072];
char task[60];
doublereal factr;
char csave[60];
doublereal dsave[29];
integer isave[44];
logical lsave[4];
doublereal pgtol;
integer iprint;
/* This simple driver demonstrates how to call the L-BFGS-B code to */
/* solve a sample problem (the extended Rosenbrock function */
/* subject to bounds on the variables). The dimension n of this */
/* problem is variable. */
/* nmax is the dimension of the largest problem to be solved. */
/* mmax is the maximum number of limited memory corrections. */
/* Declare the variables needed by the code. */
/* A description of all these variables is given at the end of */
/* the driver. */
/* Declare a few additional variables for this sample problem. */
/* We wish to have output at every iteration. */
iprint = 1;
/* We specify the tolerances in the stopping criteria. */
factr = 1e7;
pgtol = 1e-5;
/* We specify the dimension n of the sample problem and the number */
/* m of limited memory corrections stored. (n and m should not */
/* exceed the limits nmax and mmax respectively.) */
n = 25;
m = 5;
/* We now provide nbd which defines the bounds on the variables: */
/* l specifies the lower bounds, */
/* u specifies the upper bounds. */
/* First set bounds on the odd-numbered variables. */
for(int i = 0; i < n; i+=2){
nbd[i] = 2;
l[i] = 1.;
u[i] = 100.;
}
/* Next set bounds on the even-numbered variables. */
for(int i = 1; i < n; i+=2){
nbd[i] = 2;
l[i] = -100.;
u[i] = 100.;
}
/* We now define the starting point. */
for(int i = 1; i < n; i++){
x[i] = 3.;
}
printf(" Solving sample problem.\n");
printf("f = 0.0 at the optimal solution.)\n");
/* We start the iteration by initializing task. */
s_copy(task, "START", (ftnlen)60, (ftnlen)5);
/* ------- the beginning of the loop ---------- */
while(true){
/* This is the call to the L-BFGS-B code. */
setulb_(&n, &m, x, l, u, nbd, &f, g, &factr, &pgtol, wa, iwa, task, &
iprint, csave, lsave, isave, dsave, (ftnlen)60, (ftnlen)60);
if (s_cmp(task, "FG", (ftnlen)2, (ftnlen)2) == 0) {
/* the minimization routine has returned to request the */
/* function f and gradient g values at the current x. */
/* Compute function value f for the sample problem. */
f = .25*(x[0]-1.)*(x[0]-1.);
for(int i = 1;i<n;i++){
f += (x[i] - x[i-1]*x[i-1])*(x[i] - x[i-1]*x[i-1]);
}
f *= 4.;
/* Compute gradient g for the sample problem. */
t1 = x[1] - x[0]*x[0];
g[0] = (x[0] - 1.) * 2. - x[0] * 16. * t1;
for(int i = 1;i<n-1;i++){
t2 = t1;
t1=x[i+1]-x[i]*x[i];
g[i] = 8.0*t2-16.*x[i]*t1;
}
g[n - 1] = t1 * 8.;
/* go back to the minimization routine. */
}else if (s_cmp(task, "NEW_X", (ftnlen)5, (ftnlen)5) == 0) {
/* the minimization routine has returned with a new iterate, */
/* and we have opted to continue the iteration. */
}else{
// anything other than "FG" or "NEW_X" means termination
/* If task is neither FG nor NEW_X we terminate execution. */
break;
}
}
return 0;
}
Note: You’ll get runtime errors if you find/replace all of the “integer” keywords with “int”. I guess these are defined by f2c.h. All I know is, leave them alone.
Compile this with:
c++ -arch x86_64 -arch i386 routines.o -lf2c -lm -o driver1cpp driver1.cpp
And you should be able to execute your cpp program with
./driver1cpp
