Recall the basic Newton step $p_k^N$ is obtained by solving the symmetric $n\times n$ linear system

$$\nabla^2f(x_k)p_k^N = - \nabla f(x_k).$$

It’s easy to know that once the Hessian $\nabla^2f(x_k)$ is positive definite, we are able to get a descent direction. In this post, we discuss some practical approaches to tackle the situation when $\nabla^2f(x_k)$ is indefinite or close to be singular.

Local linear convergence rate is obtained if the starting point $x_0$ is sufficiently near $x*$ and satisfies the following termination condition $||r_k||\leq \eta_k||\nabla f(x_k)||$. If $\eta_k \to 0$, superlinear convergence rate is obtained and further if $\eta_k=O(||\nabla f(x_k)||)$, quadratic convergence rate is guaranteed.

## Line search Newton-CG method (truncated Newton method)

**Solve the equation by CG method, and terminating if negative curvature is encountered.**

- Choose the starting point for CG iteration $x^{(0)}$ (or the optimal solution of the previous linear system)
- Check whether a search direction $p^{(i)}$ generated by the CG iteration satisfies $$(p^{(i)})^T\nabla f(x^{(i)}) p^{(i)} \leq 0,$$ if so,

- when $i > 0$, stop the CG iteration immediately and return $x^{(i)}$.
- when $i = 0$, choose the steepest descent direction $-\nabla f(x^{(i)})$.

A vector $p^{(i)}$ satisfies the inequality in step 2 strictly, is said to be `a direction of negative curvature`

for $\nabla f(x^{(i)}).$. However, the direction might not be useful to prove a second-order critical convergence, unless it is bounded away from zero.

The following is a general description of the Newton-CG method.

- Given initial point $x_0$;
- for k = 0, 1, 2, …

Compute a search direction $p_k$ as described above. Terminate when $||r_k|| \leq \min(0.5, \sqrt{||\nabla f(x_k)||})||\nabla f(x_k)||$ or a negative curvature is encountered. - Set $x_{k+1} = x_k + \alpha_k p_k$, where $\alpha_k$ is obtained by some line search method.

## Modified Newton method

**Modify the Hessian matrix $\nabla^2f(x_k)$ before or during the solution of the equation**

## Trust-region Newton method

**Exact Hessian matrix is used to solving a trust-region model**

## Cubic regularization methods

to be continue…