prove newton quadratic convergence

Question

Trying to prove Newton's method quadratic convergence given the following:

Assume:

1. f is real valued function on open convex set S

2. ||$\nabla^2 f(x) - \nabla^2 f(y)$|| <= L||x-y||, Hessian is Lipschitz continuous on S

3. Sequence $x_k$ is generated by: $x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} * \nabla f(x_k)$

The first part of the proof states:

Prove that:

$x_{k+1} - x* = \nabla^2 f(x_k)^{-1} * [\nabla^2 f(x_k)(x_k - x*) - (\nabla f(x_k) - \nabla f(x*)]$

I'm not sure how to go about proving the above. I tried expanding $\nabla f(x_{k+1})$ about x* using Taylor approximation but that did not yield the above result. I'm also not quite clear what the equation is saying.

Answer 1

Since $S$ is open and convex, the minimizer of $f$ will satisfy $\nabla f(x_*) = 0$.

Then, starting from the update $x_{k+1} = x_k - (\nabla^2 f(x_k))^{-1} \nabla f(x_k)$, we can substract $x_* $ from both sides:

\begin{aligned} x_{k+1} - x_* &= x_k - x_* - (\nabla^2 f(x_k))^{-1} \nabla f(x_k) \\ &= \color{blue}{\nabla^2 f(x_k)^{-1} \nabla^2 f(x_k) (x_k - x_*)} - (\nabla^2 f(x_k))^{-1} \nabla f(x_k) \\ &= \color{blue}{\nabla^2 f(x_k)^{-1} \nabla^2 f(x_k) (x_k - x_*)} - (\nabla^2 f(x_k))^{-1} (\nabla f(x_k) - \color{green}{\nabla f(x_*)}), \end{aligned}

The part in blue is just rewriting $x_k - x_*$, and the part in green is due to $\nabla f(x_*) = 0$.