6.13 Quasi-Newton Methods 351
have been suggested in the literature for the computation of [Bi] as the iterative process
progresses(i.e., for the computation of [Bi+ 1 ] once [Bi] is known). A major concern
is that in addition to satisfying Eq. (6.102), the symmetry and positive definiteness of
the matrix [Bi] is to be maintained; that is, if [Bi] is symmetric and positive definite,
[Bi+ 1 ] must remain symmetric and positive definite.
6.13.1 Rank 1 Updates
The general formula for updating the matrix [Bi] can be written as
[Bi+ 1 ]=[Bi] +[ Bi] (6.103)
where [
Bi] can be considered to be the update (or correction) matrix add ed to [Bi].
Theoretically, the matrix [
Bi] can have its rank as high asn.However, in practice,
most updates, [
Bi], are only of rank 1 or 2. To derive a rank 1 update, we simply
choose a scaled outer product of a vectorzfor [
Bi] as
[ Bi] =czzT (6.104)
where the constantcand then-component vectorzare to be determined. Equations
(6.103) and (6.104) lead to
[Bi+ 1 ]=[Bi] +czzT (6.105)
Byforcing Eq. (6.105) to satisfy the quasi-Newton condition, Eq. (6.102),
di=[Bi+ 1 ]gi (6.106)
we obtain
di=([Bi] +czzT)gi=[Bi]gi+cz(zTgi) (6.107)
Since(zTgi) n Eq. (6.107) is a scalar, we can rewrite Eq. (6.107) asi
cz=
di−[Bi]gi
zTgi
(6.108)
Thus a simple choice forzandcwould be
z=di−[Bi]gi (6.109)
c=
1
zTgi
(6.110)
This leads to the unique rank 1 update formula for [Bi+ 1 ]:
[Bi+ 1 ]=[Bi] +[ Bi]≡[Bi]+
(di−[Bi]gi)(di−[Bi]gi)T
(di−[Bi]gi)Tgi
(6.111)
This formula has been attributed to Broyden [6.16]. To implement Eq. (6.111), an initial
symmetric positive definite matrix is selected for [B 1 ] at the start of the algorithm, and
the next pointX 2 is computed using Eq. (6.94). Then the new matrix [B 2 ] is computed
