55. lbfgs

55.1 Introduction to lbfgs

lbfgs is an implementation of the L-BFGS algorithm [1] to solve unconstrained minimization problems via a limited-memory quasi-Newton (BFGS) algorithm. It is called a limited-memory method because a low-rank approximation of the Hessian matrix inverse is stored instead of the entire Hessian inverse. The program was originally written in Fortran [2] by Jorge Nocedal, incorporating some functions originally written by Jorge J. Moré and David J. Thuente, and translated into Lisp automatically via the program f2cl. The Maxima package lbfgs comprises the translated code plus an interface function which manages some details.

References:

[1] D. Liu and J. Nocedal. "On the limited memory BFGS method for large scale optimization". Mathematical Programming B 45:503-528 (1989)

[2] http://netlib.org/opt/lbfgs_um.shar

55.2 Definitions for lbfgs

Function: lbfgs (FOM, X, X0, epsilon, iprint)

Finds an approximate solution of the unconstrained minimization of the figure of merit FOM over the list of variables X, starting from initial estimates X0, such that norm grad FOM < epsilon max(1, norm X).

The algorithm applied is a limited-memory quasi-Newton (BFGS) algorithm [1]. It is called a limited-memory method because a low-rank approximation of the Hessian matrix inverse is stored instead of the entire Hessian inverse.

iprint controls progress messages printed by lbfgs.

iprint[1]

iprint[1] controls the frequency of progress messages.

iprint[1] < 0

No progress messages.

iprint[1] = 0

Messages at the first and last iterations.

iprint[1] > 0

Print a message every iprint[1] iterations.

iprint[2]

iprint[2] controls the verbosity of progress messages.

iprint[2] = 0

Print out iteration count, number of evaluations of FOM, value of FOM, norm of the gradient of FOM, and step length.

iprint[2] = 1

Same as iprint[2] = 0, plus X0 and the gradient of FOM evaluated at X0.

iprint[2] = 2

Same as iprint[2] = 1, plus values of X at each iteration.

iprint[2] = 3

Same as iprint[2] = 2, plus the gradient of FOM at each iteration.

See also lbfgs_nfeval_max and lbfgs_ncorrections.

References:

[1] D. Liu and J. Nocedal. "On the limited memory BFGS method for large scale optimization". Mathematical Programming B 45:503-528 (1989)

Example:

(%i1) load (lbfgs); (%o1) /usr/share/maxima/5.10.0cvs/share/lbfgs/lbfgs.mac (%i2) FOM : '((1/length(X))*sum((F(X[i]) - Y[i])^2, i, 1, length(X))); 2 sum((F(X ) - Y ) , i, 1, length(X)) i i (%o2) ----------------------------------- length(X) (%i3) X : [1, 2, 3, 4, 5]; (%o3) [1, 2, 3, 4, 5] (%i4) Y : [0, 0.5, 1, 1.25, 1.5]; (%o4) [0, 0.5, 1, 1.25, 1.5] (%i5) F(x) := A/(1 + exp(-B*(x - C))); A (%o5) F(x) := ---------------------- 1 + exp((- B) (x - C)) (%i6) ''FOM; A 2 A 2 (%o6) ((----------------- - 1.5) + (----------------- - 1.25) - B (5 - C) - B (4 - C) %e + 1 %e + 1 A 2 A 2 + (----------------- - 1) + (----------------- - 0.5) - B (3 - C) - B (2 - C) %e + 1 %e + 1 2 A + --------------------)/5 - B (1 - C) 2 (%e + 1) (%i7) estimates : lbfgs (FOM, '[A, B, C], [1, 1, 1], 1e-4, [1, 0]); ************************************************* N= 3 NUMBER OF CORRECTIONS=25 INITIAL VALUES F= 1.348738534246918D-01 GNORM= 2.000215531936760D-01 ************************************************* I NFN FUNC GNORM STEPLENGTH 1 3 1.177820636622582D-01 9.893138394953992D-02 8.554435968992371D-01 2 6 2.302653892214013D-02 1.180098521565904D-01 2.100000000000000D+01 3 8 1.496348495303005D-02 9.611201567691633D-02 5.257340567840707D-01 4 9 7.900460841091139D-03 1.325041647391314D-02 1.000000000000000D+00 5 10 7.314495451266917D-03 1.510670810312237D-02 1.000000000000000D+00 6 11 6.750147275936680D-03 1.914964958023047D-02 1.000000000000000D+00 7 12 5.850716021108205D-03 1.028089194579363D-02 1.000000000000000D+00 8 13 5.778664230657791D-03 3.676866074530332D-04 1.000000000000000D+00 9 14 5.777818823650782D-03 3.010740179797255D-04 1.000000000000000D+00 THE MINIMIZATION TERMINATED WITHOUT DETECTING ERRORS. IFLAG = 0 (%o7) [A = 1.461933911464101, B = 1.601593973254802, C = 2.528933072164854] (%i8) plot2d ([F(x), [discrete, X, Y]], [x, -1, 6]), ''estimates; (%o8)

Variable: lbfgs_nfeval_max

Default value: 100

Variable: lbfgs_ncorrections

Default value: 25

This document was generated by Robert Dodier on Dezembro, 21 2006 using texi2html 1.76.