3.4 Newton’s Method with Hessian Modification¶

Away from the solution, the Hessian matrix \(\nabla^2 f(x)\) may not be positive definite, so the Newton direction defined by

\[\nabla^2 f(x_k)p_k^N = - \nabla f(x_k)\]

may not be a descent direction.

Algorithm 3.2 (Line Search Newton with Modification).

Given initial point \(x_0\);

for \(k = 0, 1, 2, \dots\)

Factorize the matrix \(B_k = \nabla^2f(x_k) + E_k\), where \(E_k = 0\) if \(\nabla^2f(x_k)\) is sufficiently positive definite; otherwise, \(E_k\) is chosen to ensure that \(B_k\) is sufficiently positive definite;
Solve \(B_kp_k = - \nabla f(x_k)\);
Set \(x_{k+1} = x_k + \alpha_kp_k\), where \(\alpha_k\) satisfies the Wolfe, Goldstein, or Armijo backtracking conditions;

end

We would have fairly satisfactory global convergence results for it, provided that the strategy for choosing \(E_k\) satisfies the bounded modified factorization property. This property is that the matrices in the sequence \(\{B_k\}\) have bounded condition number whenever the sequence of Hessians \(\{ \nabla^2f(x_k) \}\) is bounded; that is,

\[\kappa(B_k) = \lVert B_k \rVert \lVert B_k^{-1} \rVert \leq C, \;\;\; \text{some } C > 0 \text{ and all } k = 0, 1, 2, \dots\]

If this property holds, global convergence of the modified line search Newton method follows from the results of Section 3.2.

Theorem 3.8. Let \(f\) be twice continuously differentiable on an open set \(\mathcal{D}\), and assume that the starting point \(x_0\) of Algorithm 3.2 is such that the level set \(\mathcal{L} = \{ x \in \mathcal{D}: f(x) \leq f(x_0)\}\) is compact. Then if the bounded modified factorization property holds, we have that

\[\lim_{k \to \infty} \nabla f(x_k) = 0\]

For problems in which \(\nabla f^*\) is close to singular, there is no guarantee that the modification \(E_k\) will eventually vanish, and the convergence rate may be only linear. Besides requiring the modified matrix \(B_k\) to be well conditioned, we would like the modification to be as small as possible, so that the second-order information in the Hessian is preserved as far as possible.

3.4 Newton’s Method with Hessian Modification¶

Eigenvalue Modification¶

Adding A Multiple of The Identity¶

Modified Cholesky Factorization¶

Modified Symmetric Indefinite Factorization¶