# A New BFGS Algorithm Using the Decomposition Matrix of the Correction Matrix to Obtain the Search Directions

Authors: Li Liu
Journal: Journal of Control Science and Engineering
 (2015)

---

## Abstract

We present an improved method for determining the search direction in the BFGS algorithm. Our approach uses the equal inner product decomposition method for positive-definite matrices. The decomposition of an approximated Hessian matrix expresses a correction formula that is independent from the exact line search. This decomposed matrix is used to compute the search direction in a new BFGS algorithm.


---

## Body

## 1. Introduction

Using the equal inner product decomposition algorithm [1–3] for positive-definite matrices with a vector, a novel quasi-Newton method has been proposed [4, 5]. In this algorithm, the equal inner product decomposition matrix of the correction matrix is utilized to obtain the search directions. That is, for the unrestricted optimization problem
(1)
min
⁡
f
x
,
x
∈
R
n
,
where f
:
R
n
→
R
1 is a continuously differentiable function; the equal inner product decomposition correction formula for the approximate Hessian matrix with the objective function gradient vector is used to compute the search directions.The BFGS (Broyden-Fletcher-Goldfarb-Shanno) algorithm [6–9] is a typical quasi-Newton method. If we consider x
k to be an iteration point, and s
k
=
x
k
+
1
-
x
k, and y
k
=
g
k
+
1
-
g
k, g
k
=
∇
f
(
x
k
), then the correction formulae for the approximate Hessian matrix B and its inverse H can be expressed as
(2)
B
k
+
1
=
B
k
-
B
k
s
k
s
k
T
B
k
s
k
T
B
k
s
k
+
y
k
y
k
T
s
k
T
y
k
,
(3)
H
k
+
1
=
I
-
s
k
y
k
T
s
k
T
y
k
H
k
I
-
y
k
s
k
T
s
k
T
y
k
+
s
k
s
k
T
s
k
T
y
k
.
In computing the search direction d
k
+
1 at the iteration point x
k
+
1, we generally solve the equation:
(4)
B
k
+
1
d
k
+
1
=
-
g
k
+
1
,
but we would rather avoid using (3) to calculate
(5)
d
k
+
1
=
-
H
k
+
1
g
k
+
1
.
There are clearly more computations involved in (4) than in (5). We take this apparently more complex route because H
k
+
1 may appear to be non-positive-definite or even singular when we calculate (3). Equation (2) can be transformed to
(6)
B
k
+
1
=
B
k
+
d
k
T
g
k
-
1
g
k
g
k
T
+
α
k
d
k
T
y
k
-
1
y
k
y
k
T
.
Using this form, Gill and Murray [10] developed a method for solving (4) by Cholesky decomposition. First, they found the Cholesky decomposition of  B
k
+
1:
(7)
B
k
+
1
=
L
k
+
1
D
k
+
1
L
k
+
1
T
,
where L
k
+
1 is a unit lower triangular matrix and D
k
+
1 is a diagonal matrix, and then they successively solved
(8)
L
k
+
1
v
=
-
g
k
+
1
,
L
k
+
1
T
d
k
+
1
=
D
k
+
1
-
1
v
.
Because (6) establishes the iterative formula from L
k and D
k to L
k
+
1 and D
k
+
1, the Cholesky decomposition of B
k need not be repeated on each iteration. The detailed calculation method is described in [10–12].Unlike the above approach, the algorithm proposed in [4, 5] utilizes the equal inner product decomposition algorithm for a positive-definite matrix with a vector. In this improved technique, the matrix C
k
+
1
-
1 is computed. This is the equal inner product decomposition matrix of B
k
+
1 with g
k
+
1
=
∇
f
(
x
k
+
1
); that is,
(9)
B
k
+
1
=
C
k
+
1
C
k
+
1
T
,
C
k
+
1
-
1
g
k
+
1
=
a
k
+
1
e
,
where a
k
+
1
∈
R
1, e
=
(
1,1
,
…
,
1
)
T
∈
R
n. The search direction at the iteration point x
k
+
1 is then given by
(10)
d
k
+
1
=
-
a
k
+
1
d
1
k
+
1
,
…
,
d
n
k
+
1
T
,
where d
j
k
+
1
(
j
=
1,2
,
…
,
n
) is the sum of the elements in the jth column of C
k
+
1
-
1.Instead of using the correction formula (2), the method of [4, 5] directly establishes the correction formula from C
k
-
1 to C
k
+
1
-
1, which are equal inner product decomposition matrixes of B with the objective function gradient vectors. When the correction matrix C
k
+
1
-
1 is calculated, the search direction d
k
+
1 is immediately given by (10).Thus, [4, 5] presented a novel approach to the computation of search directions. However, all the conclusions in [4, 5] relate to the exact line search condition. Therefore, this algorithm is feasible in theory but has restricted applicability.The BFGS algorithm with the Wolfe line search has global, superlinear convergence [13–15]. Compared with other quasi-Newton methods, BFGS is the most popular and efficient algorithm. In this paper, we focus on the BFGS algorithm and set up a correction formula expressed by the decomposition matrix that is independent of the exact line search. This leads to a new BFGS algorithm that computes the search directions using the equal inner product decomposition matrix of the approximate Hessian matrix.In Section3, the procedures of computing search directions in the usual BFGS and in the new BFGS have been compared by a computing example.


## 2. Correction Formula Expressed by Decomposition Matrix

At the iteration pointx
k, we use the method of [3] to directly compute the equal inner product decomposition matrix C
k
-
1 of  B
k with g
k. However, this decomposition method is computationally expensive. One alternative is to set up a similar correction formula between C
k
-
1 and C
k
+
1
-
1 as that between H
k and H
k
+
1 or between B
k and B
k
+
1.We denoteu
k
=
C
k
-
1
y
k, v
k
=
C
k
-
1
g
k
+
1, and w
k
=
C
k
-
1
g
k. By Theorem 2.2 in [4], if the equal inner product decomposition matrix C
k
-
1 of B
k with g
k has already been computed in the exact line search condition for the BFGS correction formula (2), then the equal inner product decomposition matrix of B
k
+
1 with g
k
+
1 can be expressed as
(11)
C
k
+
1
-
1
=
Q
k
C
k
-
1
I
-
y
k
-
λ
k
g
k
s
k
T
s
k
T
y
k
,
where λ
k
=
s
k
T
y
k
/
w
k
2, Q
k
=
I
-
(
2
/
σ
k
2
)
σ
k
σ
k
T,σ
k
=
w
k
+
t
k
v
k, and t
k
=
w
k
/
v
k. By Theorem 2.3 in [4], the equal inner product decomposition matrix of the initial correction matrix B
0
=
I with g
0 is
(12)
C
0
-
1
=
I
,
g
0
=
-
e
,
I
-
2
σ
0
2
σ
0
σ
0
T
,
g
0
≠
-
e
,
where σ
0
=
n
g
0
+
g
0
e.As defined by (11), C
k
+
1
-
1 only satisfies B
k
+
1
=
C
k
+
1
C
k
+
1
T under the exact line search condition, that is, when v
k
T
w
k
=
0. If the iteration point from x
k to x
k
+
1 is obtained through an inexact line search, then obviously C
k
+
1
-
1 in (11) is no longer the decomposition matrix of B
k
+
1 defined by (2). The following conclusions are independent of the exact line search but are dependent on the correction matrix definition for BFGS.


### 2.1. Main Results

Lemma 1.
Supposeu
,
v
∈
R
n. If  β
≠
0, γ
≠
0, v
T
u
=
β
-
1
+
γ
-
1, then the matrix I
-
β
u
v
T is nonsingular and
(13)
I
-
β
u
v
T
-
1
=
I
-
γ
u
v
T
.The proof is simple and is therefore omitted from this paper.Lemma 2.
For the BFGS correction formula (11), if  C
k
-
1 is the equal inner product decomposition matrix of  B
k with g
k, we denote
(14)
N
k
=
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
C
k
.
Then, B
k
+
1
=
N
k
N
k
T and
(15)
N
k
-
1
=
C
k
-
1
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
w
k
s
k
T
y
k
.Proof.
Becauses
k
=
x
k
+
1
-
x
k
=
α
k
d
k, where α
k is the step length, we have B
k
s
k
=
-
α
k
g
k. By a direct calculation, we have
(16)
N
k
N
k
T
=
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
·
B
k
I
+
w
k
s
k
T
y
k
s
k
T
g
k
s
k
y
k
T
-
s
k
g
k
T
s
k
T
g
k
=
B
k
-
α
k
w
k
s
k
T
y
k
s
k
T
g
k
y
k
g
k
T
+
α
k
g
k
g
k
T
s
k
T
g
k
·
I
+
w
k
s
k
T
y
k
s
k
T
g
k
s
k
y
k
T
-
s
k
g
k
T
s
k
T
g
k
=
B
k
+
α
k
g
k
g
k
T
s
k
T
g
k
-
α
k
w
k
2
s
k
T
y
k
s
k
T
g
k
y
k
y
k
T
=
B
k
+
α
k
g
k
g
k
T
s
k
T
g
k
+
y
k
y
k
T
s
k
T
y
k
=
B
k
-
B
k
s
k
s
k
T
B
k
s
k
T
B
k
s
k
+
y
k
y
k
T
s
k
T
y
k
.
Therefore, B
k
+
1
=
N
k
N
k
T holds. Since
(17)
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
=
I
-
-
w
k
s
k
T
y
k
s
k
T
g
k
y
k
+
1
s
k
T
g
k
g
k
s
k
T
,
Lemma 1 implies
(18)
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
-
1
=
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
w
k
s
k
T
y
k
.
Thus, we have N
k
-
1
=
C
k
-
1
(
I
-
(
y
k
s
k
T
/
s
k
T
y
k
)
+
(
g
k
s
k
T
/
w
k
s
k
T
y
k
)
). This completes the proof.Lemma 3.
WritingQ
k
=
I
-
(
2
σ
k
σ
k
T
/
σ
k
2
), where σ
k
=
δ
k
+
(
δ
k
/
w
k
)
w
k, if 0
≠
δ
k
∈
R
n, one has Q
k
δ
k
=
-
(
δ
k
/
w
k
)
w
k.Proof.
A direct computation gives2
σ
k
T
δ
k
=
σ
k
2. Thus, we have
(19)
Q
k
δ
k
=
δ
k
-
2
σ
k
T
δ
k
σ
k
2
σ
k
=
δ
k
-
σ
k
=
-
δ
k
w
k
w
k
.
This completes the proof.Writing(20)
δ
k
=
N
k
-
1
g
k
+
1
=
p
k
v
k
+
q
k
w
k
,
where p
k
=
-
s
k
T
g
k
/
s
k
T
y
k, q
k
=
(
w
k
+
s
k
T
y
k
)
s
k
T
g
k
+
1
/
w
k
s
k
T
y
k, we can state the following results.Theorem 4.
For the BFGS correction formula (2), if the equal inner product decomposition matrix C
k
-
1 of Β
k with g
k has already been obtained, then the equal inner product decomposition matrix of  B
k
+
1 with g
k
+
1 is
(21)
C
k
+
1
-
1
=
Q
k
C
k
-
1
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
w
k
s
k
T
y
k
,
where Q
k
=
I
-
(
2
/
σ
k
2
)
σ
k
σ
k
T and σ
k
=
δ
k
+
(
δ
k
/
w
k
)
w
k.Proof.
By Lemma2 and (21), we have
(22)
C
k
+
1
=
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
C
k
Q
k
-
1
.
Because Q
k is the Householder matrix, Q
k
Q
k
T
=
I. Thus, we have
(23)
C
k
+
1
C
k
+
1
T
=
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
·
B
k
I
+
w
k
s
k
T
y
k
s
k
T
g
k
s
k
y
k
T
-
s
k
g
k
T
s
k
T
g
k
.
Therefore, Lemma 2 gives B
k
+
1
=
C
k
+
1
C
k
+
1
T. By Lemma 3, we get
(24)
C
k
+
1
-
1
g
k
+
1
=
Q
k
δ
k
=
-
δ
k
w
k
w
k
=
a
k
+
1
e
,
where a
k
+
1
=
-
(
δ
k
/
w
k
)
a
k. Thus, C
k
+
1
-
1 defined by (21) is the equal inner product decomposition matrix of B
k
+
1 with g
k
+
1. This completes the proof.From the above proof, it can be found thatC
k
+
1
-
1 in (21) is the equal inner product decomposition matrix of B
k
+
1 defined by (2), which is independent of the exact line search.Corollary 5.
Under the exact line search condition, (21) is equivalent to (11); that is, (11) is a special case for (21).Proof.
Under the exact line search condition, we haves
k
T
g
k
+
1
=
0 and s
k
T
g
k
=
-
s
k
T
y
k.
From (20), we have
(25)
δ
k
=
N
k
-
1
g
k
+
1
=
v
k
.
Thus, σ
k
=
δ
k
+
(
δ
k
/
w
k
)
w
k
=
(
v
k
/
w
k
)
(
w
k
+
t
k
v
k
)
=
(
v
k
/
w
k
)
σ
~
k, where σ
~
k
=
w
k
+
t
k
v
k.
Therefore,Q
k
=
I
-
(
2
σ
k
σ
k
T
/
σ
k
2
)
=
I
-
(
2
σ
~
k
σ
~
k
T
/
σ
~
k
2
). Under the exact line search condition, w
k
s
k
T
y
k
=
(
1
/
λ
k
)
s
k
T
y
k. From the above results, (11) can be directly deduced from (21). This completes the proof.


### 2.2. Extension

We can extend the conclusion of Theorem4 to the following BFGS correction formula using self-scaling [16–18]:
(26)
B
k
+
1
=
η
k
B
k
-
B
k
s
k
s
k
T
B
k
s
k
T
B
k
s
k
+
y
k
y
k
T
s
k
T
y
k
,
where η
k
=
θ
(
s
k
T
y
k
/
s
k
T
B
k
s
k
)
+
(
1
-
θ
)
(
y
k
T
B
k
-
1
y
k
/
s
k
T
y
k
) and θ
∈
[
0,1
]. When θ
=
1, η
k
=
s
k
T
y
k
/
s
k
T
B
k
s
k, so (26) can be written as
(27)
B
k
+
1
=
s
k
T
y
k
s
k
T
B
k
s
k
B
k
-
B
k
s
k
s
k
T
B
k
s
k
T
B
k
s
k
+
y
k
y
k
T
s
k
T
y
k
.
Equation (27) is well known for its practical applicability. Here, we have only transformed (27) into the form expressed by the decomposition correction matrix. When θ
≠
1, similar methods can be used.Applying the Sherman-Morrison formula [13] to (27), we can deduce the correction matrix for H:
(28)
H
k
+
1
=
s
k
T
B
k
s
k
s
k
T
y
k
I
-
s
k
y
k
T
s
k
T
y
k
H
k
I
-
y
k
s
k
T
s
k
T
y
k
+
s
k
s
k
T
s
k
T
y
k
.
Writing δ
~
k
=
p
~
k
v
k
+
q
~
k
w
k, where p
~
k
=
-
s
k
T
g
k
/
s
k
T
y
k and q
~
k
=
(
s
k
T
g
k
+
1
)
2
/
s
k
T
y
k
s
k
T
g
k, we can state the following for the inexact line search condition.Theorem 6.
For the self-scaling BFGS correction formula (27), if the equal inner product decomposition matrix C
k
-
1 of B
k with g
k is already known, then the equal inner product decomposition matrix of  B
k
+
1 with g
k
+
1 is
(29)
C
k
+
1
-
1
=
α
k
w
k
s
k
T
y
k
Q
k
C
k
-
1
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
s
k
T
g
k
,
where Q
k
=
I
-
(
2
/
σ
k
2
)
σ
k
σ
k
T, σ
k
=
δ
~
k
+
(
δ
~
k
/
w
k
)
w
k, and a
k
+
1
=
-
(
α
k
δ
~
k
/
s
k
T
y
k
)
a
k for step length α
k.Proof.
The proof is similar to that for Theorem4.
Using (29), we have
(30)
C
k
+
1
-
1
T
C
k
+
1
-
1
=
α
k
2
w
k
2
s
k
T
y
k
I
-
s
k
y
k
T
s
k
T
y
k
+
s
k
g
k
T
s
k
T
g
k
·
H
k
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
s
k
T
g
k
.
Because of
(31)
α
k
2
w
k
2
=
α
k
2
C
k
-
1
g
k
T
(
C
k
-
1
g
k
)
=
α
k
2
g
k
T
H
k
g
k
=
-
α
k
g
k
T
-
α
k
H
k
g
k
=
s
k
T
B
k
s
k
,
s
k
g
k
T
s
k
T
g
k
H
k
I
-
y
k
s
k
T
s
k
T
y
k
=
-
s
k
s
k
T
α
k
s
k
T
g
k
I
-
y
k
s
k
T
s
k
T
y
k
=
0
,
s
k
T
B
k
s
k
g
k
T
H
k
g
k
s
k
T
g
k
2
=
α
k
2
g
k
T
H
k
g
k
2
s
k
T
g
k
2
=
1
,(30) gives
(32)
C
k
+
1
-
1
T
C
k
+
1
-
1
=
s
k
T
B
k
s
k
s
k
T
y
k
I
-
s
k
y
k
T
s
k
T
y
k
H
k
I
-
y
k
s
k
T
s
k
T
y
k
+
s
k
s
k
T
s
k
T
y
k
=
H
k
+
1
.
Therefore, B
k
+
1
=
C
k
+
1
C
k
+
1
T and we have
(33)
C
k
+
1
-
1
g
k
+
1
=
α
k
w
k
s
k
T
y
k
Q
k
δ
~
k
=
α
k
w
k
s
k
T
y
k
-
δ
~
k
w
k
w
k
=
-
α
k
δ
~
k
s
k
T
y
k
a
k
e
;
that is, C
k
+
1
-
1
g
k
+
1
=
a
k
+
1
e, where a
k
+
1
=
-
(
α
k
δ
~
k
/
s
k
T
y
k
)
a
k. This completes the proof.Theorem6 admits the following corollary.Corollary 7.
Under the exact line search condition, if the equal inner product decomposition matrixC
k
-
1 of B
k with g
k for the self-scaling BFGS correction formula (27) is already known, then the equal inner product decomposition matrix of  B
k
+
1 with g
k
+
1 is
(34)
C
k
+
1
-
1
=
α
k
Q
k
C
k
-
1
I
+
g
k
+
1
s
k
T
s
k
T
g
k
,
where Q
k
=
I
-
(
2
/
σ
k
2
)
σ
k
σ
k
T, σ
k
=
v
k
+
(
v
k
/
w
k
)
w
k, and a
k
+
1
=
-
α
k
(
v
k
/
w
k
)
a
k  for step length α
k.Proof.
The proof is simple and is therefore omitted.


## 2.1. Main Results

Lemma 1.
Supposeu
,
v
∈
R
n. If  β
≠
0, γ
≠
0, v
T
u
=
β
-
1
+
γ
-
1, then the matrix I
-
β
u
v
T is nonsingular and
(13)
I
-
β
u
v
T
-
1
=
I
-
γ
u
v
T
.The proof is simple and is therefore omitted from this paper.Lemma 2.
For the BFGS correction formula (11), if  C
k
-
1 is the equal inner product decomposition matrix of  B
k with g
k, we denote
(14)
N
k
=
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
C
k
.
Then, B
k
+
1
=
N
k
N
k
T and
(15)
N
k
-
1
=
C
k
-
1
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
w
k
s
k
T
y
k
.Proof.
Becauses
k
=
x
k
+
1
-
x
k
=
α
k
d
k, where α
k is the step length, we have B
k
s
k
=
-
α
k
g
k. By a direct calculation, we have
(16)
N
k
N
k
T
=
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
·
B
k
I
+
w
k
s
k
T
y
k
s
k
T
g
k
s
k
y
k
T
-
s
k
g
k
T
s
k
T
g
k
=
B
k
-
α
k
w
k
s
k
T
y
k
s
k
T
g
k
y
k
g
k
T
+
α
k
g
k
g
k
T
s
k
T
g
k
·
I
+
w
k
s
k
T
y
k
s
k
T
g
k
s
k
y
k
T
-
s
k
g
k
T
s
k
T
g
k
=
B
k
+
α
k
g
k
g
k
T
s
k
T
g
k
-
α
k
w
k
2
s
k
T
y
k
s
k
T
g
k
y
k
y
k
T
=
B
k
+
α
k
g
k
g
k
T
s
k
T
g
k
+
y
k
y
k
T
s
k
T
y
k
=
B
k
-
B
k
s
k
s
k
T
B
k
s
k
T
B
k
s
k
+
y
k
y
k
T
s
k
T
y
k
.
Therefore, B
k
+
1
=
N
k
N
k
T holds. Since
(17)
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
=
I
-
-
w
k
s
k
T
y
k
s
k
T
g
k
y
k
+
1
s
k
T
g
k
g
k
s
k
T
,
Lemma 1 implies
(18)
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
-
1
=
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
w
k
s
k
T
y
k
.
Thus, we have N
k
-
1
=
C
k
-
1
(
I
-
(
y
k
s
k
T
/
s
k
T
y
k
)
+
(
g
k
s
k
T
/
w
k
s
k
T
y
k
)
). This completes the proof.Lemma 3.
WritingQ
k
=
I
-
(
2
σ
k
σ
k
T
/
σ
k
2
), where σ
k
=
δ
k
+
(
δ
k
/
w
k
)
w
k, if 0
≠
δ
k
∈
R
n, one has Q
k
δ
k
=
-
(
δ
k
/
w
k
)
w
k.Proof.
A direct computation gives2
σ
k
T
δ
k
=
σ
k
2. Thus, we have
(19)
Q
k
δ
k
=
δ
k
-
2
σ
k
T
δ
k
σ
k
2
σ
k
=
δ
k
-
σ
k
=
-
δ
k
w
k
w
k
.
This completes the proof.Writing(20)
δ
k
=
N
k
-
1
g
k
+
1
=
p
k
v
k
+
q
k
w
k
,
where p
k
=
-
s
k
T
g
k
/
s
k
T
y
k, q
k
=
(
w
k
+
s
k
T
y
k
)
s
k
T
g
k
+
1
/
w
k
s
k
T
y
k, we can state the following results.Theorem 4.
For the BFGS correction formula (2), if the equal inner product decomposition matrix C
k
-
1 of Β
k with g
k has already been obtained, then the equal inner product decomposition matrix of  B
k
+
1 with g
k
+
1 is
(21)
C
k
+
1
-
1
=
Q
k
C
k
-
1
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
w
k
s
k
T
y
k
,
where Q
k
=
I
-
(
2
/
σ
k
2
)
σ
k
σ
k
T and σ
k
=
δ
k
+
(
δ
k
/
w
k
)
w
k.Proof.
By Lemma2 and (21), we have
(22)
C
k
+
1
=
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
C
k
Q
k
-
1
.
Because Q
k is the Householder matrix, Q
k
Q
k
T
=
I. Thus, we have
(23)
C
k
+
1
C
k
+
1
T
=
I
+
w
k
s
k
T
y
k
s
k
T
g
k
y
k
s
k
T
-
g
k
s
k
T
s
k
T
g
k
·
B
k
I
+
w
k
s
k
T
y
k
s
k
T
g
k
s
k
y
k
T
-
s
k
g
k
T
s
k
T
g
k
.
Therefore, Lemma 2 gives B
k
+
1
=
C
k
+
1
C
k
+
1
T. By Lemma 3, we get
(24)
C
k
+
1
-
1
g
k
+
1
=
Q
k
δ
k
=
-
δ
k
w
k
w
k
=
a
k
+
1
e
,
where a
k
+
1
=
-
(
δ
k
/
w
k
)
a
k. Thus, C
k
+
1
-
1 defined by (21) is the equal inner product decomposition matrix of B
k
+
1 with g
k
+
1. This completes the proof.From the above proof, it can be found thatC
k
+
1
-
1 in (21) is the equal inner product decomposition matrix of B
k
+
1 defined by (2), which is independent of the exact line search.Corollary 5.
Under the exact line search condition, (21) is equivalent to (11); that is, (11) is a special case for (21).Proof.
Under the exact line search condition, we haves
k
T
g
k
+
1
=
0 and s
k
T
g
k
=
-
s
k
T
y
k.
From (20), we have
(25)
δ
k
=
N
k
-
1
g
k
+
1
=
v
k
.
Thus, σ
k
=
δ
k
+
(
δ
k
/
w
k
)
w
k
=
(
v
k
/
w
k
)
(
w
k
+
t
k
v
k
)
=
(
v
k
/
w
k
)
σ
~
k, where σ
~
k
=
w
k
+
t
k
v
k.
Therefore,Q
k
=
I
-
(
2
σ
k
σ
k
T
/
σ
k
2
)
=
I
-
(
2
σ
~
k
σ
~
k
T
/
σ
~
k
2
). Under the exact line search condition, w
k
s
k
T
y
k
=
(
1
/
λ
k
)
s
k
T
y
k. From the above results, (11) can be directly deduced from (21). This completes the proof.


## 2.2. Extension

We can extend the conclusion of Theorem4 to the following BFGS correction formula using self-scaling [16–18]:
(26)
B
k
+
1
=
η
k
B
k
-
B
k
s
k
s
k
T
B
k
s
k
T
B
k
s
k
+
y
k
y
k
T
s
k
T
y
k
,
where η
k
=
θ
(
s
k
T
y
k
/
s
k
T
B
k
s
k
)
+
(
1
-
θ
)
(
y
k
T
B
k
-
1
y
k
/
s
k
T
y
k
) and θ
∈
[
0,1
]. When θ
=
1, η
k
=
s
k
T
y
k
/
s
k
T
B
k
s
k, so (26) can be written as
(27)
B
k
+
1
=
s
k
T
y
k
s
k
T
B
k
s
k
B
k
-
B
k
s
k
s
k
T
B
k
s
k
T
B
k
s
k
+
y
k
y
k
T
s
k
T
y
k
.
Equation (27) is well known for its practical applicability. Here, we have only transformed (27) into the form expressed by the decomposition correction matrix. When θ
≠
1, similar methods can be used.Applying the Sherman-Morrison formula [13] to (27), we can deduce the correction matrix for H:
(28)
H
k
+
1
=
s
k
T
B
k
s
k
s
k
T
y
k
I
-
s
k
y
k
T
s
k
T
y
k
H
k
I
-
y
k
s
k
T
s
k
T
y
k
+
s
k
s
k
T
s
k
T
y
k
.
Writing δ
~
k
=
p
~
k
v
k
+
q
~
k
w
k, where p
~
k
=
-
s
k
T
g
k
/
s
k
T
y
k and q
~
k
=
(
s
k
T
g
k
+
1
)
2
/
s
k
T
y
k
s
k
T
g
k, we can state the following for the inexact line search condition.Theorem 6.
For the self-scaling BFGS correction formula (27), if the equal inner product decomposition matrix C
k
-
1 of B
k with g
k is already known, then the equal inner product decomposition matrix of  B
k
+
1 with g
k
+
1 is
(29)
C
k
+
1
-
1
=
α
k
w
k
s
k
T
y
k
Q
k
C
k
-
1
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
s
k
T
g
k
,
where Q
k
=
I
-
(
2
/
σ
k
2
)
σ
k
σ
k
T, σ
k
=
δ
~
k
+
(
δ
~
k
/
w
k
)
w
k, and a
k
+
1
=
-
(
α
k
δ
~
k
/
s
k
T
y
k
)
a
k for step length α
k.Proof.
The proof is similar to that for Theorem4.
Using (29), we have
(30)
C
k
+
1
-
1
T
C
k
+
1
-
1
=
α
k
2
w
k
2
s
k
T
y
k
I
-
s
k
y
k
T
s
k
T
y
k
+
s
k
g
k
T
s
k
T
g
k
·
H
k
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
s
k
T
g
k
.
Because of
(31)
α
k
2
w
k
2
=
α
k
2
C
k
-
1
g
k
T
(
C
k
-
1
g
k
)
=
α
k
2
g
k
T
H
k
g
k
=
-
α
k
g
k
T
-
α
k
H
k
g
k
=
s
k
T
B
k
s
k
,
s
k
g
k
T
s
k
T
g
k
H
k
I
-
y
k
s
k
T
s
k
T
y
k
=
-
s
k
s
k
T
α
k
s
k
T
g
k
I
-
y
k
s
k
T
s
k
T
y
k
=
0
,
s
k
T
B
k
s
k
g
k
T
H
k
g
k
s
k
T
g
k
2
=
α
k
2
g
k
T
H
k
g
k
2
s
k
T
g
k
2
=
1
,(30) gives
(32)
C
k
+
1
-
1
T
C
k
+
1
-
1
=
s
k
T
B
k
s
k
s
k
T
y
k
I
-
s
k
y
k
T
s
k
T
y
k
H
k
I
-
y
k
s
k
T
s
k
T
y
k
+
s
k
s
k
T
s
k
T
y
k
=
H
k
+
1
.
Therefore, B
k
+
1
=
C
k
+
1
C
k
+
1
T and we have
(33)
C
k
+
1
-
1
g
k
+
1
=
α
k
w
k
s
k
T
y
k
Q
k
δ
~
k
=
α
k
w
k
s
k
T
y
k
-
δ
~
k
w
k
w
k
=
-
α
k
δ
~
k
s
k
T
y
k
a
k
e
;
that is, C
k
+
1
-
1
g
k
+
1
=
a
k
+
1
e, where a
k
+
1
=
-
(
α
k
δ
~
k
/
s
k
T
y
k
)
a
k. This completes the proof.Theorem6 admits the following corollary.Corollary 7.
Under the exact line search condition, if the equal inner product decomposition matrixC
k
-
1 of B
k with g
k for the self-scaling BFGS correction formula (27) is already known, then the equal inner product decomposition matrix of  B
k
+
1 with g
k
+
1 is
(34)
C
k
+
1
-
1
=
α
k
Q
k
C
k
-
1
I
+
g
k
+
1
s
k
T
s
k
T
g
k
,
where Q
k
=
I
-
(
2
/
σ
k
2
)
σ
k
σ
k
T, σ
k
=
v
k
+
(
v
k
/
w
k
)
w
k, and a
k
+
1
=
-
α
k
(
v
k
/
w
k
)
a
k  for step length α
k.Proof.
The proof is simple and is therefore omitted.


## 3. A New BFGS Algorithm

### 3.1. Algorithm

Replacing the corresponding steps of the BFGS algorithm by (12), (21), and (10) establishes a new BFGS algorithm that uses the decomposition correction matrix to determine the search direction.The New BFGS AlgorithmStep 1.
Choose a start pointx
0, ε
≥
0, and compute g
0
=
g
(
x
0
). If g
0
≤
ε, terminate the algorithm; otherwise, go to Step 2.Step 2.
Letk
=
0. For the initial matrix B
0
=
I, form the equal inner product decomposition with g
0 to give the decomposition matrix C
0
-
1 and a
0
=
-
g
0
/
n.Step 3.
Compute the search directiond
k as
(35)
d
k
=
-
a
k
d
1
k
,
…
,
d
n
k
T
,
where d
j
k, (
j
=
1,2
,
…
,
n
) is the sum of the elements in the jth column of  C
k
-
1.Step 4.
Perform a one-dimensional line search (exact line search or Wolfe line search), and compute the step length factorα
k.Step 5.
Letx
k
+
1
=
x
k
+
α
k
d
k. Compute g
k
+
1
=
g
(
x
k
+
1
). If g
k
+
1
≤
ε, terminate the algorithm; otherwise, go to Step 6.Step 6.
Using (21), calculate the equal inner product decomposition matrix C
k
+
1
-
1 of B
k
+
1 with g
k
+
1 and the coefficient a
k
+
1
=
-
(
δ
k
/
w
k
)
a
k.Step 7.
Letk
=
k
+
1 and go to Step 3.


### 3.2. Example

Here, by an example, we compare the two methods of computing the search directions between the usual BFGS algorithm [10–12] and the new BFGS algorithm. Considering the optimization problem [19],
(36)
min
⁡
x
∈
R
2
f
(
x
)
=
2
x
1
2
+
x
2
2
-
4
x
1
+
2
,
when solving the problems withBFGS algorithm, from the second iterative computation, all the following iteration procedures are similar, so the difference of the two algorithms can be clearly seen by one iterative computing procedure. Here we assume that the first iterative computing procedure is finished and at the first iterative computing, we choose the initial point x
0
=
(
2,1
)
T, the initial matrix B
0
=
1
0
0
1. Noting g
(
x
)
=
∇
f
(
x
)
=
4
(
x
1
-
1
)
2
x
2, the initial searching direction is
(37)
d
0
=
-
g
0
=
-
g
(
x
0
)
=
-
4
,
-
2
T
.
At the point x
0, we have done theWolfe-Powell search along the d
0 and obtained the step length α
0
=
1
/
3 which satisfies theWolfe-Powell conditions [13]. Thus we get
(38)
x
1
=
x
0
+
α
0
d
0
=
2
3
,
1
3
T
,
g
1
=
g
(
x
1
)
=
-
4
3
,
2
3
T
,
s
0
=
x
1
-
x
0
=
-
4
3
,
-
2
3
T
,
y
0
=
g
1
-
g
0
=
-
16
3
,
-
4
3
T
.Now we compare the two different algorithms of computing search directions by the second iterative computation.We first compute the search directiond
1 with the usual BFGS algorithm.Step 1.
ComputeCholesky decomposition of  B
1.
Obviously, theCholesky decomposition of  B
0
=
1
0
0
1 is
(39)
B
0
=
L
0
D
0
L
0
T
=
1
0
l
21
0
1
d
11
0
0
0
d
22
0
1
0
l
21
0
1
T
=
1
0
0
1
1
0
0
1
1
0
0
1
.
LetB
-
1
=
B
0
+
(
1
/
s
0
T
y
0
)
y
0
y
0
T, definite γ
1
=
1
/
s
0
T
y
0
=
1
/
8, and ω
(
1
)
=
y
0
=
(
-
16
/
3
,
-
4
/
3
)
T.
Compute the following in turn [13]:
(40)
l
1
=
ω
1
(
1
)
=
-
16
3
,
d
-
11
=
d
11
(
0
)
+
γ
1
l
1
2
=
1
+
1
8
×
-
16
3
2
=
41
9
,
β
1
=
l
1
γ
1
d
-
11
=
-
6
41
,
γ
2
=
d
11
(
0
)
γ
1
d
-
11
=
9
328
,
ω
2
(
2
)
=
ω
2
(
1
)
-
l
1
l
21
0
=
-
4
3
-
-
16
3
×
0
=
-
4
3
,
l
-
21
=
l
21
(
0
)
+
β
1
ω
2
(
2
)
=
0
+
-
6
41
-
4
3
=
8
41
,
d
-
22
=
d
22
(
0
)
+
γ
2
l
2
2
=
1
+
9
328
-
4
3
2
=
43
41
.
Hence,
(41)
L
-
1
=
1
0
l
-
21
1
=
1
0
8
41
1
,
D
-
1
=
d
-
11
0
0
d
-
22
=
41
9
0
0
43
41
,
B
-
1
=
L
-
1
D
-
1
L
-
1
T
=
1
0
8
41
1
41
9
0
0
43
41
1
8
41
0
1
.
Then let B
1
=
B
-
1
-
(
B
0
s
0
s
0
T
B
0
/
s
0
T
B
0
s
0
)
=
B
-
1
-
(
1
/
s
0
2
)
s
0
s
0
T. Computing the equation
(42)
L
-
1
z
=
1
s
0
s
0
,
we get z
=
z
1
,
z
2
T
=
(
-
2
/
5
,
-
5
5
/
41
)
T.
Compute the following in turn [13]:
(43)
t
3
=
1
-
z
T
D
-
1
-
1
z
=
1
-
-
2
5
,
-
25
41
5
·
9
41
0
0
41
43
-
2
5
-
25
41
5
=
162
215
,
t
2
=
t
3
+
z
2
2
d
-
22
=
162
215
+
25
/
41
5
2
43
/
41
=
169
205
,
t
1
=
t
2
+
z
1
2
d
-
11
=
169
205
+
-
2
/
5
2
41
/
9
=
1
,
d
11
(
1
)
=
d
-
11
t
2
t
1
=
41
9
×
169
205
=
169
45
,
d
22
(
1
)
=
d
-
22
t
3
t
2
=
162
169
,
β
1
=
-
z
1
d
-
11
t
2
=
-
-
2
/
5
41
/
9
×
169
/
205
=
18
5
169
,
ω
2
(
2
)
=
z
2
=
-
5
5
41
,
l
21
(
1
)
=
l
-
21
+
β
1
ω
2
(
2
)
=
8
41
+
18
5
169
×
-
5
5
41
=
22
169
.
Thus we obtain
(44)
L
1
=
1
0
l
21
(
1
)
1
=
1
0
22
169
1
,
D
1
=
d
11
(
1
)
0
0
d
22
(
1
)
=
169
45
0
0
162
169
.
Therefore, we get theCholesky decomposition of B
1:
(45)
B
1
=
L
1
D
1
L
1
T
=
1
0
22
169
1
169
45
0
0
162
169
1
22
169
0
1
.Step 2.
Solve the following equations:(46)
L
1
v
=
-
g
1
,
L
1
T
d
1
=
D
1
-
1
v
.
From L
1
v
=
-
g
1, there is
(47)
v
1
=
4
3
,
22
169
v
1
+
v
2
=
-
2
3
.
Solving the equations, we get v
=
(
v
1
,
v
2
)
T
=
(
4
/
3
,
-
142
/
169
)
T. Then from L
1
T
d
1
=
D
1
-
1
v, there is
(48)
d
1
1
+
22
169
d
2
1
=
60
169
,
d
2
1
=
-
71
81
.
Solving the equations, we get the search direction
(49)
d
1
=
d
1
1
,
d
2
1
T
=
1
81
38
,
-
71
T
.We then use the new BFGS algorithm to compute the search directiond
1.Step 1.
First compute the initial correction matrixC
0
-
1 and the coefficient a
0.
Forσ
=
2
g
0
+
g
0
e
=
2
2
2
+
5
2
+
5, we get
(50)
C
0
-
1
=
I
-
2
σ
2
σ
σ
T
=
1
10
-
1
-
3
-
3
1
,
a
0
=
-
g
0
2
=
-
10
.Step 2.
ByC
0
-
1, we compute C
1
-
1.
Make use of known data, and we get(51)
s
0
T
g
0
=
-
20
3
,
s
0
T
g
1
=
4
3
,
s
0
T
y
0
=
s
0
T
g
1
-
s
0
T
g
0
=
8
,
w
0
=
C
0
-
1
g
0
=
-
10
1,1
T
,
w
0
=
2
5
,
v
0
=
C
0
-
1
g
1
=
2
3
10
-
1,7
T
.
Thus there is
(52)
p
0
=
-
s
0
T
g
0
s
0
T
y
0
=
5
6
,
q
0
=
(
w
0
+
s
0
T
y
0
)
s
0
T
g
1
w
0
s
0
T
y
0
=
5
+
10
30
.
Therefore we have
(53)
δ
0
=
p
0
v
0
+
q
0
w
0
=
-
1
9
3
+
2
10
,
3
-
2
10
T
,
δ
0
=
7
9
2
.
Because
(54)
σ
0
=
δ
0
+
δ
0
w
0
w
0
=
-
1
9
10
+
2
10
,
10
-
2
10
T
,
σ
0
2
=
280
81
,
we obtain
(55)
Q
0
=
I
-
2
σ
0
2
σ
0
σ
0
T
=
1
7
-
2
10
-
3
-
3
2
10
.
And y
0
s
0
T
=
(
8
/
9
)
8
4
2
1, g
0
s
0
T
=
-
(
4
/
3
)
4
2
2
1, so
(56)
C
1
-
1
=
Q
0
C
0
-
1
I
-
y
0
s
0
T
s
0
T
y
0
+
g
0
s
0
T
w
0
s
0
T
y
0
=
1
126
-
9
10
-
38
-
18
10
+
71
9
10
-
38
18
10
+
71
.
Thus we can obtain d
1
=
a
1
(
d
1
1
,
d
2
1
)
T, in which
(57)
d
1
1
=
1
126
(
-
9
10
-
38
)
+
(
9
10
-
38
)
=
-
38
63
,
d
2
1
=
1
126
(
-
18
10
+
71
)
+
(
18
10
+
71
)
=
71
63
,
a
1
=
-
δ
0
w
0
a
0
=
7
9
.
Therefore, the search direction is
(58)
d
1
=
d
1
1
,
d
2
1
T
=
1
81
38
,
-
71
T
.


### 3.3. Analysis

The above example clearly shows the difference between the two algorithms in computing the search directions. In the new algorithm, correction matrixes are directly used to compute search directions. There is no procedure ofCholesky decomposition and no procedure of solving equations. Thus it simplifies the computing procedure of the search directions.To compute the decomposition correction matrixC
k
+
1
-
1 at point x
k
+
1 using the new BFGS algorithm, we first need to compute a Householder matrix Q
k. This increases the computational complexity. However, the search direction d
k
+
1 can be directly computed by (10) at the same time. Consequently, the two steps of the correction matrix calculation and search direction calculation are performed concurrently. In practice, the computation of  (21) can be simplified using the properties of the Householder matrix.Let then row vectors of N
k
-
1 be denoted as α
k
1
T
,
α
k
2
T
,
…
,
α
k
n
T; that is,
(59)
N
k
-
1
=
C
k
-
1
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
w
k
s
k
T
y
k
=
α
k
1
T
α
k
2
T
⋮
α
k
n
T
.
Thus, we can write
(60)
σ
k
T
N
k
-
1
=
σ
k
1
α
k
1
T
+
⋯
+
σ
k
n
α
k
n
T
=
r
k
T
,
where σ
k
1
,
…
,
σ
k
n are the n components of σ
k. Therefore, we have
(61)
β
k
σ
k
σ
k
T
N
k
-
1
=
β
k
σ
k
1
r
k
T
β
k
σ
k
2
r
k
T
⋮
β
k
σ
k
n
r
k
T
,
where β
k
=
2
/
σ
k
2. Hence,
(62)
C
k
+
1
-
1
=
Q
k
N
k
-
1
=
I
-
β
k
σ
k
σ
k
T
N
k
-
1
=
N
k
-
1
-
β
k
σ
k
σ
k
T
N
k
-
1
=
α
k
1
T
-
β
k
σ
k
1
r
k
T
α
k
2
T
-
β
k
σ
k
2
r
k
T
⋮
α
k
n
T
-
β
k
σ
k
n
r
k
T
.
As a result, after N
k
-
1 and σ
k have been computed, the decomposition correction matrix C
k
+
1
-
1 can be directly obtained from (62), removing the need to compute the Householder matrix Q
k.We can also compare the condition numbers ofH
k and C
k
-
1 in the correction formulae (3) and (21). The condition number is directly related to the possible magnification in relative error of the matrix calculations. Thus, a smaller condition number implies better numerical stability.Because the correction matrixH
k is symmetric and positive-definite, if the eigenvalues μ
k
i, (
1
≤
i
≤
n
) of H
k have size order
(63)
0
<
μ
k
1
≤
μ
k
2
≤
⋯
≤
μ
k
n
,
then the condition number of H
k in terms of the spectral norm [20] is
(64)
cond
H
k
=
H
k
H
k
-
1
=
μ
k
n
μ
k
1
.
Because (
C
k
-
1
)
T
C
k
-
1
=
H
k,
(65)
cond
C
k
-
1
=
μ
k
n
μ
k
1
,
and therefore
(66)
cond
(
C
k
-
1
)
=
cond
(
H
k
)
≤
cond
(
H
k
)
.
Clearly, cond
(
C
k
-
1
)
=
cond
(
H
k
) only when H
k is a diagonal matrix whose diagonal elements are all the same. Otherwise, cond
(
C
k
-
1
)
<
cond
(
H
k
). Furthermore, cond
(
Q
k
)
=
1 and cond
(
Q
k
C
k
-
1
)
=
cond
(
C
k
-
1
), which is beneficial to the calculation stability of (21). Note that (66) holds for all k, so the numerical stability of correction formula (21) should be much better than that of (3).In addition, the iterative calculation of the decomposition correction matrix involves only nonsingular matrices. Thus, the calculation accuracy requirements should be lower than in the original BFGS algorithm, which considers symmetric positive-definite matrices.


## 3.1. Algorithm

Replacing the corresponding steps of the BFGS algorithm by (12), (21), and (10) establishes a new BFGS algorithm that uses the decomposition correction matrix to determine the search direction.The New BFGS AlgorithmStep 1.
Choose a start pointx
0, ε
≥
0, and compute g
0
=
g
(
x
0
). If g
0
≤
ε, terminate the algorithm; otherwise, go to Step 2.Step 2.
Letk
=
0. For the initial matrix B
0
=
I, form the equal inner product decomposition with g
0 to give the decomposition matrix C
0
-
1 and a
0
=
-
g
0
/
n.Step 3.
Compute the search directiond
k as
(35)
d
k
=
-
a
k
d
1
k
,
…
,
d
n
k
T
,
where d
j
k, (
j
=
1,2
,
…
,
n
) is the sum of the elements in the jth column of  C
k
-
1.Step 4.
Perform a one-dimensional line search (exact line search or Wolfe line search), and compute the step length factorα
k.Step 5.
Letx
k
+
1
=
x
k
+
α
k
d
k. Compute g
k
+
1
=
g
(
x
k
+
1
). If g
k
+
1
≤
ε, terminate the algorithm; otherwise, go to Step 6.Step 6.
Using (21), calculate the equal inner product decomposition matrix C
k
+
1
-
1 of B
k
+
1 with g
k
+
1 and the coefficient a
k
+
1
=
-
(
δ
k
/
w
k
)
a
k.Step 7.
Letk
=
k
+
1 and go to Step 3.


## 3.2. Example

Here, by an example, we compare the two methods of computing the search directions between the usual BFGS algorithm [10–12] and the new BFGS algorithm. Considering the optimization problem [19],
(36)
min
⁡
x
∈
R
2
f
(
x
)
=
2
x
1
2
+
x
2
2
-
4
x
1
+
2
,
when solving the problems withBFGS algorithm, from the second iterative computation, all the following iteration procedures are similar, so the difference of the two algorithms can be clearly seen by one iterative computing procedure. Here we assume that the first iterative computing procedure is finished and at the first iterative computing, we choose the initial point x
0
=
(
2,1
)
T, the initial matrix B
0
=
1
0
0
1. Noting g
(
x
)
=
∇
f
(
x
)
=
4
(
x
1
-
1
)
2
x
2, the initial searching direction is
(37)
d
0
=
-
g
0
=
-
g
(
x
0
)
=
-
4
,
-
2
T
.
At the point x
0, we have done theWolfe-Powell search along the d
0 and obtained the step length α
0
=
1
/
3 which satisfies theWolfe-Powell conditions [13]. Thus we get
(38)
x
1
=
x
0
+
α
0
d
0
=
2
3
,
1
3
T
,
g
1
=
g
(
x
1
)
=
-
4
3
,
2
3
T
,
s
0
=
x
1
-
x
0
=
-
4
3
,
-
2
3
T
,
y
0
=
g
1
-
g
0
=
-
16
3
,
-
4
3
T
.Now we compare the two different algorithms of computing search directions by the second iterative computation.We first compute the search directiond
1 with the usual BFGS algorithm.Step 1.
ComputeCholesky decomposition of  B
1.
Obviously, theCholesky decomposition of  B
0
=
1
0
0
1 is
(39)
B
0
=
L
0
D
0
L
0
T
=
1
0
l
21
0
1
d
11
0
0
0
d
22
0
1
0
l
21
0
1
T
=
1
0
0
1
1
0
0
1
1
0
0
1
.
LetB
-
1
=
B
0
+
(
1
/
s
0
T
y
0
)
y
0
y
0
T, definite γ
1
=
1
/
s
0
T
y
0
=
1
/
8, and ω
(
1
)
=
y
0
=
(
-
16
/
3
,
-
4
/
3
)
T.
Compute the following in turn [13]:
(40)
l
1
=
ω
1
(
1
)
=
-
16
3
,
d
-
11
=
d
11
(
0
)
+
γ
1
l
1
2
=
1
+
1
8
×
-
16
3
2
=
41
9
,
β
1
=
l
1
γ
1
d
-
11
=
-
6
41
,
γ
2
=
d
11
(
0
)
γ
1
d
-
11
=
9
328
,
ω
2
(
2
)
=
ω
2
(
1
)
-
l
1
l
21
0
=
-
4
3
-
-
16
3
×
0
=
-
4
3
,
l
-
21
=
l
21
(
0
)
+
β
1
ω
2
(
2
)
=
0
+
-
6
41
-
4
3
=
8
41
,
d
-
22
=
d
22
(
0
)
+
γ
2
l
2
2
=
1
+
9
328
-
4
3
2
=
43
41
.
Hence,
(41)
L
-
1
=
1
0
l
-
21
1
=
1
0
8
41
1
,
D
-
1
=
d
-
11
0
0
d
-
22
=
41
9
0
0
43
41
,
B
-
1
=
L
-
1
D
-
1
L
-
1
T
=
1
0
8
41
1
41
9
0
0
43
41
1
8
41
0
1
.
Then let B
1
=
B
-
1
-
(
B
0
s
0
s
0
T
B
0
/
s
0
T
B
0
s
0
)
=
B
-
1
-
(
1
/
s
0
2
)
s
0
s
0
T. Computing the equation
(42)
L
-
1
z
=
1
s
0
s
0
,
we get z
=
z
1
,
z
2
T
=
(
-
2
/
5
,
-
5
5
/
41
)
T.
Compute the following in turn [13]:
(43)
t
3
=
1
-
z
T
D
-
1
-
1
z
=
1
-
-
2
5
,
-
25
41
5
·
9
41
0
0
41
43
-
2
5
-
25
41
5
=
162
215
,
t
2
=
t
3
+
z
2
2
d
-
22
=
162
215
+
25
/
41
5
2
43
/
41
=
169
205
,
t
1
=
t
2
+
z
1
2
d
-
11
=
169
205
+
-
2
/
5
2
41
/
9
=
1
,
d
11
(
1
)
=
d
-
11
t
2
t
1
=
41
9
×
169
205
=
169
45
,
d
22
(
1
)
=
d
-
22
t
3
t
2
=
162
169
,
β
1
=
-
z
1
d
-
11
t
2
=
-
-
2
/
5
41
/
9
×
169
/
205
=
18
5
169
,
ω
2
(
2
)
=
z
2
=
-
5
5
41
,
l
21
(
1
)
=
l
-
21
+
β
1
ω
2
(
2
)
=
8
41
+
18
5
169
×
-
5
5
41
=
22
169
.
Thus we obtain
(44)
L
1
=
1
0
l
21
(
1
)
1
=
1
0
22
169
1
,
D
1
=
d
11
(
1
)
0
0
d
22
(
1
)
=
169
45
0
0
162
169
.
Therefore, we get theCholesky decomposition of B
1:
(45)
B
1
=
L
1
D
1
L
1
T
=
1
0
22
169
1
169
45
0
0
162
169
1
22
169
0
1
.Step 2.
Solve the following equations:(46)
L
1
v
=
-
g
1
,
L
1
T
d
1
=
D
1
-
1
v
.
From L
1
v
=
-
g
1, there is
(47)
v
1
=
4
3
,
22
169
v
1
+
v
2
=
-
2
3
.
Solving the equations, we get v
=
(
v
1
,
v
2
)
T
=
(
4
/
3
,
-
142
/
169
)
T. Then from L
1
T
d
1
=
D
1
-
1
v, there is
(48)
d
1
1
+
22
169
d
2
1
=
60
169
,
d
2
1
=
-
71
81
.
Solving the equations, we get the search direction
(49)
d
1
=
d
1
1
,
d
2
1
T
=
1
81
38
,
-
71
T
.We then use the new BFGS algorithm to compute the search directiond
1.Step 1.
First compute the initial correction matrixC
0
-
1 and the coefficient a
0.
Forσ
=
2
g
0
+
g
0
e
=
2
2
2
+
5
2
+
5, we get
(50)
C
0
-
1
=
I
-
2
σ
2
σ
σ
T
=
1
10
-
1
-
3
-
3
1
,
a
0
=
-
g
0
2
=
-
10
.Step 2.
ByC
0
-
1, we compute C
1
-
1.
Make use of known data, and we get(51)
s
0
T
g
0
=
-
20
3
,
s
0
T
g
1
=
4
3
,
s
0
T
y
0
=
s
0
T
g
1
-
s
0
T
g
0
=
8
,
w
0
=
C
0
-
1
g
0
=
-
10
1,1
T
,
w
0
=
2
5
,
v
0
=
C
0
-
1
g
1
=
2
3
10
-
1,7
T
.
Thus there is
(52)
p
0
=
-
s
0
T
g
0
s
0
T
y
0
=
5
6
,
q
0
=
(
w
0
+
s
0
T
y
0
)
s
0
T
g
1
w
0
s
0
T
y
0
=
5
+
10
30
.
Therefore we have
(53)
δ
0
=
p
0
v
0
+
q
0
w
0
=
-
1
9
3
+
2
10
,
3
-
2
10
T
,
δ
0
=
7
9
2
.
Because
(54)
σ
0
=
δ
0
+
δ
0
w
0
w
0
=
-
1
9
10
+
2
10
,
10
-
2
10
T
,
σ
0
2
=
280
81
,
we obtain
(55)
Q
0
=
I
-
2
σ
0
2
σ
0
σ
0
T
=
1
7
-
2
10
-
3
-
3
2
10
.
And y
0
s
0
T
=
(
8
/
9
)
8
4
2
1, g
0
s
0
T
=
-
(
4
/
3
)
4
2
2
1, so
(56)
C
1
-
1
=
Q
0
C
0
-
1
I
-
y
0
s
0
T
s
0
T
y
0
+
g
0
s
0
T
w
0
s
0
T
y
0
=
1
126
-
9
10
-
38
-
18
10
+
71
9
10
-
38
18
10
+
71
.
Thus we can obtain d
1
=
a
1
(
d
1
1
,
d
2
1
)
T, in which
(57)
d
1
1
=
1
126
(
-
9
10
-
38
)
+
(
9
10
-
38
)
=
-
38
63
,
d
2
1
=
1
126
(
-
18
10
+
71
)
+
(
18
10
+
71
)
=
71
63
,
a
1
=
-
δ
0
w
0
a
0
=
7
9
.
Therefore, the search direction is
(58)
d
1
=
d
1
1
,
d
2
1
T
=
1
81
38
,
-
71
T
.


## 3.3. Analysis

The above example clearly shows the difference between the two algorithms in computing the search directions. In the new algorithm, correction matrixes are directly used to compute search directions. There is no procedure ofCholesky decomposition and no procedure of solving equations. Thus it simplifies the computing procedure of the search directions.To compute the decomposition correction matrixC
k
+
1
-
1 at point x
k
+
1 using the new BFGS algorithm, we first need to compute a Householder matrix Q
k. This increases the computational complexity. However, the search direction d
k
+
1 can be directly computed by (10) at the same time. Consequently, the two steps of the correction matrix calculation and search direction calculation are performed concurrently. In practice, the computation of  (21) can be simplified using the properties of the Householder matrix.Let then row vectors of N
k
-
1 be denoted as α
k
1
T
,
α
k
2
T
,
…
,
α
k
n
T; that is,
(59)
N
k
-
1
=
C
k
-
1
I
-
y
k
s
k
T
s
k
T
y
k
+
g
k
s
k
T
w
k
s
k
T
y
k
=
α
k
1
T
α
k
2
T
⋮
α
k
n
T
.
Thus, we can write
(60)
σ
k
T
N
k
-
1
=
σ
k
1
α
k
1
T
+
⋯
+
σ
k
n
α
k
n
T
=
r
k
T
,
where σ
k
1
,
…
,
σ
k
n are the n components of σ
k. Therefore, we have
(61)
β
k
σ
k
σ
k
T
N
k
-
1
=
β
k
σ
k
1
r
k
T
β
k
σ
k
2
r
k
T
⋮
β
k
σ
k
n
r
k
T
,
where β
k
=
2
/
σ
k
2. Hence,
(62)
C
k
+
1
-
1
=
Q
k
N
k
-
1
=
I
-
β
k
σ
k
σ
k
T
N
k
-
1
=
N
k
-
1
-
β
k
σ
k
σ
k
T
N
k
-
1
=
α
k
1
T
-
β
k
σ
k
1
r
k
T
α
k
2
T
-
β
k
σ
k
2
r
k
T
⋮
α
k
n
T
-
β
k
σ
k
n
r
k
T
.
As a result, after N
k
-
1 and σ
k have been computed, the decomposition correction matrix C
k
+
1
-
1 can be directly obtained from (62), removing the need to compute the Householder matrix Q
k.We can also compare the condition numbers ofH
k and C
k
-
1 in the correction formulae (3) and (21). The condition number is directly related to the possible magnification in relative error of the matrix calculations. Thus, a smaller condition number implies better numerical stability.Because the correction matrixH
k is symmetric and positive-definite, if the eigenvalues μ
k
i, (
1
≤
i
≤
n
) of H
k have size order
(63)
0
<
μ
k
1
≤
μ
k
2
≤
⋯
≤
μ
k
n
,
then the condition number of H
k in terms of the spectral norm [20] is
(64)
cond
H
k
=
H
k
H
k
-
1
=
μ
k
n
μ
k
1
.
Because (
C
k
-
1
)
T
C
k
-
1
=
H
k,
(65)
cond
C
k
-
1
=
μ
k
n
μ
k
1
,
and therefore
(66)
cond
(
C
k
-
1
)
=
cond
(
H
k
)
≤
cond
(
H
k
)
.
Clearly, cond
(
C
k
-
1
)
=
cond
(
H
k
) only when H
k is a diagonal matrix whose diagonal elements are all the same. Otherwise, cond
(
C
k
-
1
)
<
cond
(
H
k
). Furthermore, cond
(
Q
k
)
=
1 and cond
(
Q
k
C
k
-
1
)
=
cond
(
C
k
-
1
), which is beneficial to the calculation stability of (21). Note that (66) holds for all k, so the numerical stability of correction formula (21) should be much better than that of (3).In addition, the iterative calculation of the decomposition correction matrix involves only nonsingular matrices. Thus, the calculation accuracy requirements should be lower than in the original BFGS algorithm, which considers symmetric positive-definite matrices.



---

*Source: 674617-2015-01-31.xml*