Limited-Memory BFGS with Variations

This web page is a companion to:

Tamara Gibson (Kolda), Dianne P. O'Leary, and Larry Nazareth, "BFGS with Update Skipping and Varying Memory", Technical Report CS-TR-3663, Department of Computer Science, University of Maryland College Park, 1996. Also listed as Technical Report UMIACS-TR-96-49.

Index

• FORTRAN code and CUTE interface for variations described in Section 4 of the TR.
• Maple notebooks from Section 1 of the TR.
• Detailed numerical results from Section 4 of the TR.

The L-BFGS with variations subroutine may be used in any program. We have also included the linesearch that we used, needed blas subroutines, and a sample Makefile.

Additionally, you may want to interface L-BFGS with variations with the CUTE testing environment for optimization software. We have also included directions and extra needed files for this.

lbfgsvar.F

L-BFGS with variations subroutine. Documentation is given in the file.

blas.f

Selected BLAS subroutines from Netlib.

linesearch.f

MINPACK linesearch subroutine by Jorge J. More' and David J. Thuente.

Makefile

A sample makefile.

lbfgsvar.README

Directions for interfacing lbfgsvar with CUTE.

lbfgsvarma.f

Interface program for CUTE and lbfgsvar.

lbfgsvar.script

Script file for use with CUTE.

lbfgsvar.tar.gz

All the files listed above.

The following two maple notebook files correspond to examples given in Section 2. Both examples are performed in exact arithmetic. You have the option of either downloading the original MAPLE notebooks or viewing the output text generated by the notebooks.

The first notebook implements limited-memory DFP with limited-memory constant M=1 on a simple three-dimensional quadratic function. Even after 20 iterations, the algorithm does not terminate. In contrast, limited-memory BFGS with M=1 would terminate in three iterations or less.

• L-DFP with limited-memory constant M=1 example as a MAPLE notebook or MAPLE output text.

The second notebook implements limited-memory BFGS with limited-memory constant M=1 and skips every other update of the quasi-Newton matrix. We use a three-dimensional example and show that even after 20 iterations, the algorithm has not terminated. In contrast, full-memory BFGS with update skipping would terminate in at most seven iterations.

• L-BFGS-SKIP with limited-memory constant M=1 example as a MAPLE notebook or MAPLE output text

The file results.mat is a mat-file which can be read into MATLAB by the command load results. It contains the following variables:

• The variables exp0 thru exp21 are strings containing the compile line options used to create each experiment. The lbfgsvar.F code contains descriptions of these options. The numbered experiments are described in detail in the TR.

  exp1 = '-DVARYMG=0'

• The variables prob1 thru prob22 are strings containing the problem names, and the variables size1 thru size22 are numbers which list the size of each problem.

  prob1='EXTROSNB'
  size1 = 10

• Each problem name is mapped to a unique number. For example,

  EXTROSNB = 1

• The results of each experiment. A matrix A is defined which contains the following information in its columns:
  1. Experiment Number
  2. Problem Number
  3. M
  4. Exit Code (Nonzero Indicates Failure)
  5. Iterations
  6. Function Evaluations
  7. Final Function Value
  8. Final Norm of Gradient
  9. Compute Time

  Example: a single row of A might be ...

  0 3 5 0 102 107 0.1374D+04 0.1150D-03 0.09

The following m-files are available for processing the data in the results.mat file. We also give usage statements. We assume that the matlab variable M is the M-value of 5,10,15, or 50, the variable EXP is an experiment number between 0 and 21, and the variable PROB is a problem number between 1 and 22.

listprob.m

Lists the problem numbers, names and sizes.
>> listprob

listexp.m

Lists the experiment numbers and compile line options.
>> listexp

expsum.m

Lists the results a particular experiment for a particular value of M.
>> expsum(M,EXP);

basecomp.m

Compares a given experiment to L-BFGS with no options for a given value of M and graphs the results. You may also specify a particular range of problems to be considered. You must also download expsum.m to use this function.
>> basecomp(M,EXP);

probsum.m

Summarizes the results for a particular problem with a particular value of M.
>> probsum(M,PROB);

rankit.m

Ranks the algorithms according to how well they do on a particular problem for a particular value of M with respect to either iterations (1), function evaluations (2) or time (3). You must also download probsum.m to use this function.
>> rankit(M,PROB,1);

allmbasecomp

Compares an experiment for all four possible values of M and graphs the results.
>> allmbasecomp(EXP);