# Convergence of Truncated Newton for non-convex Hessian

I was wondering if anyone could enlighten me about the convergence properties of the truncated newton method in case of a non-positive definite hessian $$\nabla^2 f = H$$. From the Book 'Numerical Optimization' from Nocedal & Wright, the Algorithm consists of two loops, one inner to compute the (Newton-)search direction $$p_k$$ by using the conjugate gradient method (CG) and one outer loop to compute the stepwise $$\alpha_k$$.

The algorithm roughly looks like this:

• Outer Loop For $$k = 0,1,2,...$$:
• Given some initial $$x_0$$, $$r_0 = \nabla f_k$$ and $$p_0 = -\nabla f_k$$
• Define stopping tolerance of CG $$\eta_k=min$$ $$(0.5,\sqrt \Vert \nabla f \Vert)$$ $$\Vert \nabla f \Vert$$ for superlinear convergence.
• Inner Loop For $$j = 0,1,2,...$$:
• Compute $$p_k$$ by solving $$Hp_k$$ = $$-\nabla f$$ using the CG.
• If $$\Vert r_j \Vert \leq \eta_k$$, stopping criteria is fulfilled and $$p_k$$ is found.
• If during CG the Hessian loses positive definiteness $$p_j^T H p_j \leq 0$$ than use last valid computed direction $$p_{j-1}$$ where $$p_j^T H p_j > 0$$. If that happens during first iteration $$j=0$$, use the gradient as new direction $$p_k = -\nabla f$$.
• Apply some line search to determine $$\alpha_k$$ and set $$x_{k+1} = x_k + \alpha_k p_k$$

Now as mentioned, since $$\underset{k \rightarrow \infty}{lim}\eta_k = 0$$ the convergence of truncated newton method is q-superlinear if $$H$$ is positive definite. But if the inner loop gets disrupted by $$H$$ becoming non-positive definite, CG will not fullfill the stopping criteria. Especially if non-convexity gets detected in the first iteration and $$p_k = -\nabla f$$, truncated newton method basically becomes method of greatest descent which has only linear convergence properties. Am I therefore right to assume that truncated newton only has superlinear convergence if $$H$$ stays positive definite for all times ($$k=0,1,2,...$$)?

• That seems right, but If I recall my optimization correctly, can't you define an objective function such that H is guaranteed to be SPD? – EMP Jul 23 '20 at 14:37
• The Hessian will be positive semidefinite in a neighborhood of a local minimum. The superlinear convergence result is an asymptotic convergence rate that only holds in the limit as you get sufficiently close to a minimum. Keep in mind that asymptotic convergence rates say nothing about what happens far away from a minimum. – Brian Borchers Jul 23 '20 at 15:26
• Thanks for the correction. – EMP Jul 23 '20 at 16:56