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.