Math. J. Okayama Univ. 47 (2005), 175–188

MODIFICATIONS OF THE LIMITED MEMORY BFGSALGORITHM FOR LARGE-SCALE NONLINEAR
OPTIMIZATION
Leong Wah JUNE and Malik Abu HASSAN
Abstract. In this paper we present two new numerical methods forunconstrained large-scale optimization. These methods apply update
formulae, which are derived by considering diﬀerent techniques of approximating the objective function. Theoretical analysis is given to show
the advantages of using these update formulae. It is observed that these
update formulae can be employed within the framework of limited memory strategy with only a modest increase in the linear algebra cost.
Comparative results with limited memory BFGS (L-BFGS) method arepresented.

1. Introduction
Large-scale unconstrained optimization is to minimize a nonlinear function f (x) in a ﬁnite dimensional space, that is(1.1)

minx∈<n f (x)where n is large. We assume throughout that both the gradient g(x) =∇f (x) and the Hessian matrix G(x) = ∇2 f (x) of f exist and are continuous.
In 1980 Nocedal [8] introduced limited memory BFGS (L-BFGS) update
for large-scale unconstrained optimization. Subsequent numerical studies
on large-scale problems have shown that methods based on this updating
scheme can be very eﬀective if the updated inverse Hessian approximation
are rescaled at every iteration [6],[13]. Indeed the L-BFGS method is currently the winner on many classes of problems and competes with truncatedNewton methods on a variety of large-scale nonlinear problems [13].
The L-BFGS method is a matrix secant method speciﬁcally designed forlow storage and linear algebra costs in computation of a Newton-like search
direction. This is done by employing a clever representation for the L-BFGS
update. Recall that the L-BFGS update is obtained by applying BFGS
update to an initial positive deﬁnite diagonal matrix (a scaling matrix) using
data from the few most recent iteration. The search direction is computed bya simple matrix-vector multiplication. Change in the initial scaling matrix
and the data from past iterations can be introduced into the update at low
Mathematics Subject Classiﬁcation. Primary 65; Secondary K10, H10.
Key words and phrases. Large-scale optimization, limited memory methods, BFGS
update.
175

176

L. W. JUNE AND M. A. HASSAN

cost. This is especially true if the initial scaling matrix is a positive multipleof identity matrix as it is usually taken to be in practice. Once the search
direction is computed, an appropriate step-length is obtained from one of
the standard line search procedures.
In this paper we observe that some modiﬁed BFGS update such as
Biggs’[1], [2] BFGS update and Yuan’s[12] BFGS update can be employedwithin the framework of limited memory strategy. Since these modiﬁed updates are known to be quite eﬃcient in minimization of low-dimensional
nonlinear objective functions, such an approach may improve eﬃciency of
the BFGS method in limited memory scheme. Moreover, only a modest
increase in the linear algebra cost when applying these modiﬁed updates.
Therefore, the aim of this paper is to propose an algorithmic framework,
which tries to adopt the previous advantages while still ensuring global convergence towards stationary points. It is based on the simple idea of approximating the objective function by diﬀerent techniques. In Section 2 wewill describe these techniques. The limited memory methods using these
update formulae are given in Section 3 and 4. In Section 5 the results ofour numerical experiments are reported. Convergence results are given in
Section 6, and ﬁnally the conclusions are made in Section 7.
2. Modified BFGS Methods using Different Function
Interpolation
Quasi-Newton methods are a class of numerical methods that are similar
to Newton’s method except that the inverse of Hessian (G(xk ))−1 is replaced
by a n × n symmetric matrix Hk , which satisﬁes the quasi-Newton equation(2.1)

Hk yk−1 = sk−1 ,

where
(2.2)

sk−1 = xk − xk−1 = λk−1 dk−1 , yk−1 = gk − gk−1 ,and λk−1 > 0 is a step-length which satisﬁes some line search conditions.
Assuming Hk nonsingular, we deﬁne Bk = Hk−1 . It is easy to see that thequasi-Newton step
(2.3)

dk = −Hk gk

is a stationary point of the following problem:
1mind∈<n φk (d) = f (xk ) + dT gk + dT Bk d2which is an approximation to problem (1.1) near the current itarate xk , sinceφk (d) ≈ f (xk + d) for small d. In fact, the deﬁnition of φk (·) in (2.4) implies(2.4)

MODIFICATIONS OF THE LIMITED MEMORY BFGS ALGORITHM

177

that
(2.5)

φk (0) = f (xk ), ∇φk (0) = g(xk ),and the quasi-Newton condiiton (2.1) is equivalent to∇φk (xk−1 − xk ) = g(xk−1 ).

(2.6)

Thus, φk (x − xk ) is a quadratic interpolation of f (x) at xk and xk−1 , satisfying conditions (2.5)-(2.6). The matrix Bk (or Hk ) can be updated so thatthe quasi-Newton equation is satisﬁed.
One well known update formula is the BFGS formula which updates Bk+1
from Bk , sk and yk in the following way:
(2.7)

Bk+1 = Bk −Bk sk sTk Bk
yk ykT+.
sTk Bk sk
sTk ykIn Yuan [12], approximate function φk (d) in (2.4) is required to satisfy theinterpolation condition
φk (xk−1 − xk ) = f (xk−1 )(2.8)

instead of (2.6). This change was inspired from the fact that for onedimensional problem, using (2.8) gives a slightly faster local convergence
if we assume λk = 1 for all k. Equation (2.8) can be rewritten as
[
]
(2.9)
sTk−1 Bk sk−1 = 2 f (xk−1 ) − f (xk ) + sTk−1 gk .
In order to satisfy (2.9), the BFGS formula is modiﬁed as follows:(2.10)

Bk+1 = Bk −where
(2.11)tk =Bk sk sTk Bk
yk ykT+t,k T
sTk Bk sk
sk yk

]
2 [
T
f
(x
)
−
f
(x
)
+
s
.
g
k
k+1
k+1
k
sTk ykIf Hk+1 is the inverse of Bk+1 , then][()
ykT Hk yk
1TT
T(2.12) Hk+1 = Hk + T
αk + Tsk sk − sk yk Hk − Hk yk sk
sk yk
sk yk
with
(2.13)

αk =

1
.
tk

Assume that Bk is positive deﬁnite and that sTk yk > 0, Bk+1 deﬁned by(2.10) is positive deﬁnite if and only if tk > 0. The inequality tk > 0 is trivial
if f is strictly convex, and it is also true if the step-length λk is chosen by
an exact line search, which requires sTk gk+1 = 0. For a uniformly convex
function, it can be easily shown that there exists a constant δ > 0 such

178

L. W. JUNE AND M. A. HASSAN

that tk ∈ [δ, 2] for all k, and consequently global convergence proof of the
BFGS method for convex functions with inexact line searches, which wasgiven by Powell [10]. However, for a general nonlinear function f , inexact
line searches do not imply the positivity of tk , hence Yuan [12] truncatedtk to the interval [0.01, 100], and showed that the global convergence of themodiﬁed BFGS algorithm is preserved for convex functions. If the objectivefunction f is cubic along the line segment between xk−1 and xk then we
have the following relation(2.14)

sTk−1 G(xk )sk−1 = 4sTk−1 gk + 2sTk−1 gk+1 − 6 [f (xk−1 ) − f (xk )] ,by considering the Hermit interpolation on the line between xk−1 and xk .
Hence it is reasonable to require that the new approximate Hessian satisﬁes
condition(2.15)

sTk−1 Bk sk−1 = 4sTk−1 gk + 2sTk−1 gk+1 − 6 [f (xk−1 ) − f (xk )]instead of (2.11). Biggs [1], [2] gives the update of (2.12) with the value tk
chosen so that (2.15) holds. The respected value of tk is given by]
6 [f (xk ) − f (xk+1 ) + sTk gk+1 − 2.
(2.16)
tk = Tsk yk
For one-dimensional problems, Wang and Yuan [11] showed that (2.10)
with (2.16) and without line searches (that is λk = 1 for all k) implies
R−quadratic convergence, and except some special cases (2.10) with (2.16)
also give Q−convergence.
It is well known that the convergence rate of√secant method is (1 + 5)/2 which is approximately 1.618 and less than 2.
3. Limited Memory BFGS Method
The limited memory BFGS method is described by Nocedal [8], where
it is called the SQN method. The user speciﬁes the number m of BFGS
corrections that are to be kept, and provides a sparse symmetric and positivedeﬁnite matrix H0 , which approximates the inverse Hessian of f . During theﬁrst m iterations the method is identical to the BFGS method. For k > m,
Hk is obtained by applying m BFGS updates to H0 using information fromthe m previous iterations. The method uses the inverse BFGS formula in
the form(3.1)

Hk+1 = VkT Hk Vk + ρk sk sTk ,

where
(3.2)

ρk = 1/ykT sk , Vk = I − ρk yk sTk .

( see Dennis and Schnabel [4].)Algorithm 3.1. L-BFGS method

MODIFICATIONS OF THE LIMITED MEMORY BFGS ALGORITHM

179(1) Choose x0 , 0 < β 0 < 1/2, β 0 < β < 1, and initial matrix H0 = I. Set
k = 0.
(2) Computedk = −Hk gk
andxk+1 = xk + λk dk
where λk satisﬁes(3.3)

f (xk + λk dk ) ≤ f (xk ) + β 0 λk gkT dk ,(3.4)

g(xk + λk dk )T dk ≥ βgkT dk(the step-length λ = 1 is tried ﬁrst).
(3) Let m̂ = min{k, m − 1}. Update H0 for m̂ + 1 times by using thepairs {yj , sj }kj=k−m̂ , i.e. letT
Hk+1 = (VkT . . . Vk−m̂ )H0 (Vk−m̂ . . . Vk )TT+ ρk−m̂ (VkT . . . Vk−m̂+1 )sk−m̂ sk−m̂ (Vk−m̂+1 . . . Vk )

(3.5)

T
T
+ ρk−m̂+1 (VkT . . . Vk−m̂+2 )sk−m̂+1 sk−m̂+1 (Vk−m̂+2 . . . Vk )..
.
+ ρk sk sTk(4) Set k := k + 1 and go to Step 2.
4. Modified L-BFGS Algorithms
In practice, it is noted that the performances of Biggs and Yuan’s updates
are better than the original BFGS update for normal quasi-Newton methods(see, for instance, Phua and Setiono [9] for the performance of Biggs’ update
and Yuan [12] for Yuan’s update).
To improve the performance of the L-BFGS algorithm, one possibility is
to use the Biggs and Yuan’s updates instead of the BFGS update. We notethat the modiﬁed BFGS update (2.12) can also be expressed in the form
(4.1)

Hk+1 = VkT Hk Vk + αk ρk sk sTk .

Therefore, the major steps of the new limited memory methods are similar to
the L-BFGS algorithm, except that (3.5) in Step 3 of the L-BFGS algorithm
will be replaced by the following formula:T
Hk+1 = (VkT . . . Vk−m̂ )H0 (Vk−m̂ . . . Vk )T
T+ αk−m̂ ρk−m̂ (VkT . . . Vk−m̂+1 )sk−m̂ sk−m̂ (Vk−m̂+1 . . . Vk )

(4.2)

T
T
+ αk−m̂+1 ρk−m̂+1 (VkT . . . Vk−m̂+2 )sk−m̂+1 sk−m̂+1 (Vk−m̂+2 . . . Vk )..
.
+ αk ρk sk sTk .

180

L. W. JUNE AND M. A. HASSAN

However, for the following reasons we do not use the above mentioned formula for our limited memory scheme:(1) In order to use (4.2) replacing (3.5), we need to calculate and storeαk−m̂ , αk−m̂+1 , . . . , αk , which will require an additional ofm̂=min{k, m − 1} storage. Resource in storage is the most crucial factor to determine the successfulness of a method when applied
to large-scale problems.
(2) So far, the convergence rate of the modiﬁed BFGS updates in alimited memory scheme is not established. Convergence analysis ofthese updates was only given for standard quasi-Newton under certain conditions. On the other hand, Liu and Nocedal [6] establishedthe convergence of the L-BFGS method.
(3) For n−dimensional problems, Dennis and Moré [3] showed that thestandard BFGS method converged Q−superlinearly using an inexact line search if the current iterate xk is suﬃciently close to x∗ .
Therefore, the BFGS update should be preferred if xk happened tobe so.
For reasons that we have discussed,we shall not use the fully modiﬁed BFGS
update (4.2) to replace (3.5). Instead a partially modiﬁed BFGS update will
be applied in Step 3 of the L-BFGS algorithm. The users will specify the
number m̃ < min{k, m − 1} of modiﬁed BFGS corrections that are to be
used. During the ﬁrst m̃ iterations the method is identical to the modiﬁed
BFGS method and Hk is obtained by applying m̃ modiﬁed BFGS update to
H0 . After m̃ iteration, BFGS update will be used instead of the modiﬁed
BFGS update, the method is then identical to the L-BFGS method proposedby Nocedal [8]. We shall described the above steps in details:
Step 3. Given an integer m̃ < min{k, m − 1} and Let m̂ = min{k, m − 1}.
Update H0 for m̂ + 1 times by using the pairs {yj , sj }m̃
j=0 , i.e. letT
Hk+1 = (VkT . . . Vk−m̂ )H0 (Vk−m̂ . . . Vk )T
T+ αk−m̂ ρk−m̂ (VkT . . . Vk−m̂+1 )sk−m̂ sk−m̂ (Vk−m̂+1 . . . Vk )T
T+ αk−m̂ ρk−m̂+1 (VkT . . . Vk−m̂+2 )sk−m̂+1 sk−m̂+1 (Vk−m̂+2 . . . Vk )
..
.

(4.3)

T
+ αk−m̂+m̃ ρk−m̂+m̃ (VkT . . . Vk−m̂+m̃+1 )sk−m̂+m̃

× sTk−m̂+m̃ (Vk−m̂+m̃+1 . . . Vk )T
+ ρk−m̂+m̃+1 (VkT . . . Vk−m̂+m̃+2 )sk−m̂+m̃+1..
.
+ ρk sk sTk

× sTk−m̂+m̃+1 (Vk−m̂+m̃+2 . . . Vk )

MODIFICATIONS OF THE LIMITED MEMORY BFGS ALGORITHM

181

with αk = 0.01 if αk ≤ 0.01, and αk = 100 if αk ≥ 100.
5. Computational Results
In this section, we present and discuss some numerical experiments thatwere conducted in order to test the performance of limited memory quasiNewton methods for unconstrained optimization using the modiﬁed BFGS
formulae againt those using BFGS update.
The algorithms used for limited memory methods are from L-BFGS,
which provides the line search strategy for calculating global step. Theline search is based on backtracking, using quadratic and cubic modeling off (x) in the direction of search.
Five test functions, with variable dimensions, have been chosen from literature of optimization. The description of these test problems can be found,for instance, in Moré et al. [7]. Each function is tested with three diﬀerent
dimensions, namely n = 8, 200 and 1000. All test functions are tested witha single standard starting point.
All algorithms are implemented in Fortran77. The runs were performed
with a double precision arithmetic, for which the unit roundoﬀ is approximately 10−16 . In all cases, convergence is assumed if(5.1)

k gk k< 10−5 max{1, k xk k}.

In all tables, nI is the number of iterations and nf is the number of function/gradient evaluations required by that algorithm in solving each test
problem. The numbers of modiﬁcation made, m̃ is listed by the interger
numbers in bracket ( ) for Biggs’ and Yuan’s limited memory BFGS methods. For our case, m̃ varies from 2 to 5.
Numerical results obtained by applying the above algorithms are given in
Tables 1-3.
Comparing the performance of all these algorithms, Tables 1-3 show thatin terms of the total number of iterations, limited memory algorithms using
Yuan’s BFGS update scored the best while Bigg’s BFGS is the second best,with L-BFGS the last. In terms of the total number of function/gradientevaluations, Biggs’ BFGS requires the lowest number of function/gradientcalls, Yuan’s BFGS is the second, with again L-BFGS the last. The improvements of limited memory Biggs’ BFGS and Yuan’s BFGS methods
are 11% in terms of the numbers of iterations, and saving of 10.7% and6.4% respectively, in terms of the number of functon/gradient evaluations
over L-BFGS method for m = 5. For m = 10, a savings of 9.4% and 9.3%
respectively, in terms of the number of function/gradient evaluations over LBFGS method. Finally, the improvements of limited memory Biggs’ BFGS

182

L. W. JUNE AND M. A. HASSAN

Table 1. Comparative results of limited memory Biggs’
BFGS, Yuan’s BFGS and L-BFGS methods with m = 5
Test Problems
Trigonometricn=8
n = 200
n = 1000
Rosenbrookn=8
n = 200
n = 1000
Powelln=8n = 200
n = 1000Beale
n=8n = 200
n = 1000
Wood
n=8
n = 200
n = 1000
Total

Biggs’
nI

BFGS
nf

Yuan’snI

BFGS
nf

L-BFGS
nI

nf

24(3)
39(3)
46(5)

28
46
52

22(3)
46(4)
46(5)

29
52
54

24
40
48

31
45
45

35(3)
34(3)
34(3)

47
46
44

32(3)
34(2)
35(3)

41
46
51

38
36
37

49
45
48

31(3)
42(3)
37(3)

35
48
40

35(3)
34(4)
33(3)

38
43
56

46
37
67

54
46
78

14(3)
14(3)
14(2)

16
16
17

14(3)
14(3)
14(3)

16
17
19

15
15
15

17
16
16

83(3)
81(3)
94(3)
622

103
104
123
765

90(4)
84(2)
88(3)
621

118
108
114
802

91
91
99
699

118
121
128
857

and Yuan’s BFGS methods over L-BFGS method are 5.4% and 7.4% respectively, in terms of the number of function/gradient evaluations. On theother hand, the increments of memory requirement is only of maximum 5
units (m̃ = 5), which is less than 0.5% for n = 200 or 1000.

6. Analysis of Convergence
Consider methods with an update of the form
(6.1)

Hk+1 = δk PkT H0 Qk +k∑T
wik zik
.

i=1

Here,
(1) H0 is an n × n symmetric positive deﬁnite matrix that remains constant for all k, and δk is a nonzero scalar that can be thought of as
an iterative rescaling of H0 ;

MODIFICATIONS OF THE LIMITED MEMORY BFGS ALGORITHM

183

Table 2. Comparative results of limited memory Biggs’
BFGS, Yuan’s BFGS and L-BFGS methods with m = 10
Test Problems
Trigonometricn=8
n = 200
n = 1000
Rosenbrookn=8
n = 200
n = 1000
Powelln=8n = 200
n = 1000Beale
n=8n = 200
n = 1000
Wood
n=8
n = 200
n = 1000
Total

Biggs’
nI

BFGS
nf

Yuan’snI

BFGS
nf

L-BFGS
nI

nf

21(3)
37(3)
45(3)

25
42
52

22(3)
45(5)
44(3)

27
52
52

24
48
50

29
55
61

33(3)
34(3)
34(3)

42
48
41

32(3)
35(3)
35(3)

40
49
47

37
37
35

44
49
44

32(3)
43(2)
39(3)

37
48
45

35(3)
34(4)
33(3)

39
46
39

38
31
51

43
33
58

14(3)
13(3)
15(5)

16
15
17

14(3)
14(3)
14(3)

16
17
19

14
16
15

16
17
16

80(3)
86(3)
73(3)
598

99
108
91
726

79(3)
81(3)
82(3)
599

95
101
98
737

89
89
86
690

118
118
117
818

(2) Pk is an n × n matrix that is the product of projection matrices ofthe form
(6.2)

I−

uv T
,
uT v

where u ∈ span{y0 , . . . , yk } and v ∈ span{s0 , . . . , sk+1 }1, and Qk is
an n × n matrix that is the product of projection matrices of thesame form where u is any n−vector and v ∈ span{s0 , . . . , sk };(3) mk is a nonnegative integer, wik (i = 1, . . . , k) is any n−vector, andzik (i = 1, . . . , k) is any vector in span{s0 , . . . , sk }.
This form of updates is discussed by Kolda et al. [5], and is referred as
the general form. The general form ﬁts many known methods, including the
L-BFGS method and the proposed limited memory modiﬁed BFGS. The
limited memory modiﬁed update with limited memory constant m can be
1The vector s

k+1 has not yet been explicitly calculated but is needed here only for thetheoretical framework, not for the computational algorithms.

184

L. W. JUNE AND M. A. HASSAN

Table 3. Comparative results of limited memory Biggs’
BFGS, Yuan’s BFGS and L-BFGS methods with m = 30
Test Problems
Trigonometricn=8
n = 200
n = 1000
Rosenbrookn=8
n = 200
n = 1000
Powelln=8n = 200
n = 1000Beale
n=8n = 200
n = 1000
Wood
n=8
n = 200
n = 1000
Total

Biggs’
nI

BFGS
nf

Yuan’snI

BFGS
nf

L-BFGS
nI

nf

20(3)
43(3)
44(5)

25
52
52

21(3)
43(5)
43(5)

26
49
51

23
46
45

28
55
53

32(3)
34(3)
34(3)

42
48
41

32(3)
34(2)
34(2)

40
45
45

37
37
35

44
49
44

31(3)
43(3)
37(5)

33
46
46

32(3)
30(3)
36(2)

33
31
41

36
45
36

39
46
41

14(3)
13(3)
14(5)

16
15
17

14(3)
14(3)
14(3)

16
17
19

14
16
15

16
17
16

86(5)
85(5)
79(3)
609

99
98
95
724

82(5)
85(5)
82(3)
596

98
106
102
719

87
87
85
644

113
115
114
780

witten as(6.3)

T
Hk+1 = Vk−m
H0 Vk−mk +1,k +k +1,kk∑T
Vi+1,ki=k−mk +1

sTi si
Vi+1,kti sTi yi

where mk = min{k + 1, m}.
The above method ﬁts the general form (6.1) if at iteration k we chooseδk = 1(without scaling), mk = min{k + 1, m},T
Pk = Qk = Vk−m
, andk +1,kwik = zik = √

T
Vk−m
s
k +i+1,k k−mk +i.

tk−mk +i sTk−mk +i yk−mk +i

We show that methods ﬁtting the general form (6.1) produce conjugate search directions (see Theorem 6.1) and terminate in n iterations (seeCorollary 6.2) if and only if Pk maps the vector y0 through yk into span{y0 , . . . , yk−1 } for each k = 1, 2, . . . , n.

MODIFICATIONS OF THE LIMITED MEMORY BFGS ALGORITHM

185

Theorem 6.1. Suppose that we apply a quasi-Newton (QN) method withan update of the form (2.11) to minimize an n-dimensional strictly convex
quadratic function. Then for each k before ternmination (i.e., gk+1 6= 0),
T
gk+1
sj = 0, for all j = 0, 1, . . . , k,sTk+1 Asj = 0, for all j = 0, 1, . . . , k, andspan{s0 , . . . , sk+1 } = span{H0 g0 , . . . , H0 gk+1 },if and only if(6.4)

Pj yi ∈ span{y0 , . . . , yk+1 } for all i = 0, 1, . . . , k, j = 0, 1, . . . , k.

Proof. See Theorem 2.2 in Kolda et al. [5].

¤When a method produces conjugate search directions, we can say something about termination.
Corollary 6.2. Suppose we have a method of the type described in Theorem
6.1 satisfying (2.11). Suppose further that Hk gk 6= 0 whenever gk 6= 0. Thenthe scheme reproduces the iterates from the conjugate gradient method withpreconditioner H0 and terminates in no more than n iteration.
Proof. See Corollary 2.3 in Kolda et al. [5].

¤Note that we require that Hk gk be nonzero whenever gk is nonzero; thisrequirement is equivalent to positive deﬁnite updates and is necessary since
not all methods produce positive deﬁnite updates. It is possible to construct
an update that maps gk to zero even it is not positive deﬁnite. If this were
to happen, we would have a breakdown in the method. In our case, positivedeﬁniteness is trivial if tk > 0.
The next corollary gives some ideas for methods that relate to L-BFGS
and also will terminate in at most n iterations on strictly convex quadratics.
Corollary 6.3. The L-BFGS method with exact line search will terminate
in n iteration on an n−dimensional strictly convex quadratic function even
if any of the following modiﬁcation is made to the update:(1) Every BFGS updates in (3.5) are replaced by (4.1).
(2) Any m BFGS updates before the method is restarted are replaced by(4.1).
(3) Replacing any m̂ ≤ min{m, k + 1} BFGS updates by (4.1) before themethod is restarted.
Proof. For each variant, we show that the method ﬁts the general formin (6.1), satisﬁes condition (6.4) of Theorem 6.1, and hence terminates by
Corollary 6.2.

186

L. W. JUNE AND M. A. HASSAN(1) Let m > 0 be any integer, which is preset by users or may change
from iteration, and deﬁne
Vik =

k
∏
(
j=i

I−

yj sTj )sTj yj.

Chooseδk = 1, mk = min{k + 1, m},T
Pk = Qk = Vk−m
, andk +1,kwik = zik = √

T
Vk−m
s
k +i+1,k k−mk +i

tk−mk +i sTk−mk +i yk−mk +iwith all tk > 0.

These choices clearly ﬁt the general form. Furthermore,{
0, if j = k − mk , k − mk + 1, . . . , k,
Pk yi =
yj , if j = 0, 1, . . . , k − mk − 1
so this variation satisﬁes condition (6.1) of Theorem 6.1.
(2) This is a special case of the ﬁrst variant. Note that the BFGS update
is equals to tk = 1.
(3) This is a special case of the second variant with the choices:δk = 1, m̂ = min{k + 1, mk },T
Pk = Qk = Vk−m̂k +1,k , andwik = zik = √TVk−m̂k +i+1,k sk−m̂k +i

tk−m̂k +i sTk−m̂k +i yk−m̂k +iwith all tk > 0.

These choices will also ﬁt the general form. Moreover,{
0, if j = k − m̂k , k − m̂k + 1, . . . , k.
Pk yi =
yj , if j = 0, 1, . . . , k − m̂k − 1
After m̂ iterations, choose m̂ =min{k + 1, m} and ti = 1 for i =m̂, m̂ + 1, . . . , mk .
¤Note that the considered cases in Corollary 6.3 cover both limited memory
methods with full of partially modiﬁed BFGS updates.

MODIFICATIONS OF THE LIMITED MEMORY BFGS ALGORITHM

187

7. Conclusions
We have attempted, in this paper, to develop two numerical methods forlarge-scale unconstrained optimization that are based on diﬀerent techniqueof approximating the objective function. We applied both the Biggs’ andYuan’s BFGS updates partially in the limited memory scheme replacing thestandard BFGS update.
We tested these methods on a set of standard test functions from Moréet al. [7]. Our test results show that on the set of problems we tried,
our partially modiﬁed L-BFGS methods require fewer iterations and function/gradient evaluations than L-BFGS by Nocedal [8]. Numerical tests alsosuggest that these partially modiﬁed L-BFGS methods are more superior
than the standard L-BFGS method.
Thus for large problems where space limitations do not preclude using
the full quasi-Newton updates, these methods are recommended.

References[1] Biggs, M.C. Minimization algorithms making use of non-quadratic properties of theobjective function. Journal of the Institute of Mathematics and Its Applications, 8:315327, 1971.
[2] Biggs, M.C. A note on minimization algorithms making use of non-quadratic propertiesof the objective function. Journal of the Institute of Mathematics and Its Applications,
12:337-338, 1973.
[3] Dennis, J.E.Jr. and Moré, J.J. Quasi-Newton method, motivation and theory. SIAM
Review, 19:46-89, 1977.
[4] Dennis, J.E.Jr. and Schnabel, R.B. Numerical Methods for Nonlinear Equations andUnconstrained Optimization. Prentice-Hall, New Jersey, 1983.
[5] Kolda, T.G., Dianne, P.O. and Nazareth, L. BFGS with update skipping and varying
memory. SIAM Journal on Optimization, 8/4: 1060-1083, 1998.
[6] Liu, D.C. and Nocedal, J. On the limited memory BFGS method for large-scale optimization. Mathematical Programming, 45:503-528, 1989.
[7] Moré, J.J., Garbow, B.S. and Hillstrom, K.E. Testing unconstrained optimization software. ACM Transactions on Mathematical Software, 7:17-41, 1981.
[8] Nocedal, J. Updating quasi-Newton matrices with limited storage. Mathematics of Computation, 35:773-782, 1980.
[9] Phua, P.K.H. and Setiono, R. Combined quasi-Newton updates for unconstrained optimization. National University of Singapore, Dept. of Information Systems and Computer Science, TR 41/92, 1992.
[10] Powell, M.J.D. Some global convergence properties of a variable metric algorithm
for minimization without exact line searches, in: R.W. Cottle and C.E. Lemke, eds.,
Nonlinear Programming SIAM-AMS Proceeding, SIAM Publications, 9:53-72, 1976.
[11] Wang, H.J. and Yuan, Y. A quadratic convergence method for one-dimensional optimization. Chinese Journal of Operations Research, 11:1-10, 1992.
[12] Yuan, Y. A modiﬁed BFGS algorithm for unconstrained optimization. IMA Journal
Numerical Analysis, 11:325-332, 1991.

188

L. W. JUNE AND M. A. HASSAN[13] Nash, S.G. and Nocedal, J. A numerical study of a limited memory BFGS method
and the truncated Newton method for large-scale optimization. SIAM J. Optimization,
1:358-372, 1991.
Leong Wah June
Department of Mathematics
Faculty of Science
University Putra Malaysia
Serdang, 43400 Malaysia
e-mail address: leongwj@putra.upm.edu.my
Malik Abu Hassan
Department of Mathematics
Faculty of Science
University Putra Malaysia
Serdang, 43400 Malaysia
e-mail address: malik@fsas.upm.edu.my(Received April 26, 2005 )