Newton's method has local quadratic convergence under a Lipschitz Hessian

By [F2]–[F3], $H(x^{\ast })$ has an orthonormal eigenbasis with positive eigenvalues. Let $\lambda >0$ be its smallest eigenvalue. Choose $r<R\mathrm{/}2$ with $Kr\le \lambda \mathrm{/}2$. For $\mathrm{\parallel }x-x^{\ast }\mathrm{\parallel }\le r$ and any vector $v$, $v^{T}H(x)v\ge v^{T}H(x^{\ast })v-\mathrm{\parallel }H(x)-H(x^{\ast }){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\mathrm{\parallel }v{\mathrm{\parallel }}^2\ge \frac{\lambda }{2}\mathrm{\parallel }v{\mathrm{\parallel }}^2\mathrm{.}$ Thus $H(x)$ is positive definite there and [F4] makes each Newton solve well-defined.

Put $M_0:=\mathrm{\parallel }H(x^{\ast }){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}+Kr$, $M:=\sqrt{d}{M}_0$, and $m:=\lambda \mathrm{/}2$. Along the segment $x^{\ast }+te$, where $e=x-x^{\ast }$ and $\mathrm{\parallel }e\mathrm{\parallel }\le r$, apply [F5] to each coordinate of the gradient map $t\mapsto \mathrm{\nabla }f(x^{\ast }+te)$. Its derivative is the corresponding coordinate of $H(x^{\ast }+te)e$; the integrand is continuous and hence integrable by [F6]. Newton–Leibniz [F7] and $\mathrm{\nabla }f(x^{\ast })=0$ give $\mathrm{\nabla }f(x)={\int }_0^{1}H(x^{\ast }+te)edt\mathrm{.}$ For every $t\in [0,1]$, $\mathrm{\parallel }H(x^{\ast }+te){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le M_0$, so each coordinate of $H(x^{\ast }+te)e$ is bounded in absolute value by $M_0\mathrm{\parallel }e\mathrm{\parallel }$. Apply [F11] to each coordinate integral; this gives $\mathrm{\mid }\mathrm{\nabla }f(x{)}_i\mathrm{\mid }\le M_0\mathrm{\parallel }e\mathrm{\parallel }$ and hence $\mathrm{\parallel }\mathrm{\nabla }f(x)\mathrm{\parallel }\le M\mathrm{\parallel }e\mathrm{\parallel }$. Each coordinate of $(H(x)-H(x^{\ast }+te))e$ is bounded in absolute value by $K(1-t)\mathrm{\parallel }e{\mathrm{\parallel }}^2$, using the operator-norm Lipschitz bound and [F10]. Applying [F11] to these coordinate integrals gives $\mathrm{\parallel }H(x)e-\mathrm{\nabla }f(x)\mathrm{\parallel }\le \frac{\sqrt{d}K}{2}\mathrm{\parallel }e{\mathrm{\parallel }}^2\mathrm{.}$

Let $p=-H(x{)}^{-1}\mathrm{\nabla }f(x)$ be the Newton direction and $e_{+}:=x+p-x^{\ast }$. Since $e_{+}=H(x{)}^{-1}(H(x)e-\mathrm{\nabla }f(x))$ and $\mathrm{\parallel }H(x{)}^{-1}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 1\mathrm{/}m=2\mathrm{/}\lambda$ by step 1.1 and the orthonormal eigenbasis in [F3], step 2.1 gives $\mathrm{\parallel }{e}_{+}\mathrm{\parallel }\le C\mathrm{\parallel }e{\mathrm{\parallel }}^2,C:=\sqrt{d}K\mathrm{/}\lambda \mathrm{.}$ Also $\mathrm{\parallel }p\mathrm{\parallel }\le D\mathrm{\parallel }e\mathrm{\parallel }$ with $D:=M\mathrm{/}m=2M\mathrm{/}\lambda$, because $\mathrm{\parallel }p\mathrm{\parallel }\le m^{-1}\mathrm{\parallel }\mathrm{\nabla }f(x)\mathrm{\parallel }$.

Choose $\rho \le r\mathrm{/}(1+D)$ and, if $K>0$, also choose $D\rho \le (1\mathrm{/}2-\alpha )\lambda \mathrm{/}K$; decrease $\rho$ further so $C\rho \le 1\mathrm{/}2$. For $x\in B(x^{\ast },\rho )$ the segment from $x$ to $x+p$ lies in $B(x^{\ast },r)$. If $\mathrm{\nabla }f(x)=0$, step 3.1 gives $\mathrm{\parallel }e\mathrm{\parallel }\le C\mathrm{\parallel }e{\mathrm{\parallel }}^2$, so the choice $C\rho \le 1\mathrm{/}2$ forces $e=0$.

Whenever a nonzero Newton direction is sent to line search, apply [F8] with $k=1$ on the segment $x+[0,1]p$. For some $\theta \in (0,1)$, $f(x+p)=f(x)+⟨\mathrm{\nabla }f(x),p⟩+\frac{1}{2}{p}^{T}H(x+\theta p)p\mathrm{.}$ Write $A:=p^{T}H(x)p\ge m\mathrm{\parallel }p{\mathrm{\parallel }}^2$ by step 1.1. Since $\mathrm{\nabla }f(x)=-H(x)p$ and $H$ is $K$-Lipschitz, $f(x+p)-f(x)-\alpha ⟨\mathrm{\nabla }f(x),p⟩\le -(1\mathrm{/}2-\alpha )A+\frac{K}{2}\mathrm{\parallel }p{\mathrm{\parallel }}^3\le 0$ by the choice of $\rho$ in step 4.1. If $K=0$, the same inequality holds with its cubic term zero. Therefore the full step passes the Armijo test and [F1] accepts $t=1$. This is conditional on the decrement test not stopping before line search.

At any generated iterate in $B(x^{\ast },\rho )$, a nonstationary point has a positive-definite Hessian by step 1.1, so the unavailable-solve status cannot occur. If its decrement test stops the method, no update is attempted. Otherwise step 5.1 gives a unit step, and steps 3.1 and 5.1 give the quadratic bound and $\mathrm{\parallel }{e}_{+}\mathrm{\parallel }\le C\rho \mathrm{\parallel }e\mathrm{\parallel }\le \mathrm{\parallel }e\mathrm{\parallel }\mathrm{/}2$, so the next generated iterate remains in the ball. If an iterate is stationary, step 4.1 shows it is $x^{\ast }$. Induction over generated iterates proves the local statement, with the rate asserted exactly for updates the algorithm attempts. No claim outside this neighborhood follows.