Page 63 - Applied Probability

3. Newton’s Method and Scoring
46
turbation satisfying a secant condition. The secant condition originates
from the first-order Taylor’s approximation
t
2
If we set dL(θ n ) − dL(θ n+1 ) t ≈ d L(θ n+1 )(θ n − θ n+1 ).
t
= dL(θ n ) − dL(θ n+1 ) t
g n
= θ n − θ n+1 ,
s n
then the secant condition is −A n+1 s n = g n. The unique symmetric, rank-
one update to A n satisfying the secant condition is furnished by Davidon’s
formula [5]
t
= A n − c n v n v , (3.9)
A n+1
n
with constant c n and vector v n specified by
1
= (3.10)
c n
t
(g n + A n s n ) s n
v n = g n + A n s n .
Until recently, symmetric rank-two updates such as those associated with
Davidon, Fletcher, and Powell (DFP) or with Broyden, Fletcher, Gold-
farb, and Shanno (BFGS) were considered superior to the more parsimo-
nious update (3.9). However, numerical analysts [4, 11] are now beginning
to appreciate the virtues of Davidon’s formula. To put it into successful
practice, monitoring A n for positive definiteness is necessary. An immedi-
ate concern is that the constant c n is undefined when the inner product
t
t
(g n + A n s n ) s n = 0. In such situations, or when (g n + A n s n ) s n is small
t
compared to v v n , one can ignore the secant requirement and simply take
n
A n+1 = A n .
If A n is positive definite and c n ≤ 0, then A n+1 is certainly positive
definite. If c n > 0, then it may be necessary to shrink c n to maintain positive
definiteness. In order for A n+1 to be positive definite, it is necessary that
t
t
t
t
v A −1 [A n − c n v n v ]A −1 = v A −1 v n [1 − c n v A −1 v n ]
n n n n v n n n n n
> 0.
t
In other words, 1 − c n v A −1 v n > 0 must hold. Conversely, this condition
n
n
is sufficient to insure positive definiteness of A n+1 . This fact can be most
easily demonstrated by noting the Sherman-Morrison formula [15]
t
t −1
[A n − c n v n v ] = A −1 + c n −1 A −1 v n [A −1 v n ] . (3.11)
n
n
n
n
t
1 − c n v A n v n
n
t −1
Formula (3.11) shows that [A n − c n v n v ] exists and is positive definite
n
under the stated condition. Since the inverse of a positive definite matrix