Some approximate Newton methods. The cost of Newton's method is dominated by the cost of evaluating the Hessian ∇2f(x) and the cost of solving the Newton system. For large problems, it is sometimes useful to replace the Hessian by a positive definite approximation that makes it easier to form and solve for the search step. In this problem we explore some common examples of this idea.
For each of the approximate Newton methods described below, test the method on some instances of the analytic centering problem described in exercise 9.30, and compare the results to those obtained using the Newton method and gradient method.
((a)) Re-using the Hessian. We evaluate and factor the Hessian only every N iterations, where N>1, and use the search step Δx=−H−1∇f(x), where H is the last Hessian evaluated. (We need to evaluate and factor the Hessian once every N steps; for the other steps, we compute the search direction using back and forward substitution.)
((b)) Diagonal approximation. We replace the Hessian by its diagonal, so we only have to evaluate the n second derivatives ∂2f(x)/∂xi2, and computing the search step is very easy.