A numerically stable and efficient technique for the maintenance of positive definiteness in the Hessian for Newton-type methods

Unconstrained optimization problems using Newton-type methods sometimes require that the Hessian matrix, G, calculated at each iteration, be modified to G¹ in order to insure that the direction of search is downhill. It is shown that several previously proposed methods modify G in such a manner that G¹ becomes extremely ill-conditioned even when G itself is well conditioned. The method proposed here is a modification of Greenstadt's, where bounds on the eigenvalues of G¹ may be imposed such that G¹ has a spectral condition number identical to G when G is well-conditioned but indefinite. The modification updates G by the addition of rank-one matrices, which are obtained by a partial eigenvalue decomposition of G, rather than a complete one as originally proposed by Greenstadt. The matrix G¹ obtained in this manner is identical to the G¹ obtained by Greenstadt's method, but may be computed in substantially less time.