2
$\begingroup$

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,...$)?

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ – EMP Jul 23 '20 at 14:37
  • 2
    $\begingroup$ 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. $\endgroup$ – Brian Borchers Jul 23 '20 at 15:26
  • $\begingroup$ Thanks for the correction. $\endgroup$ – EMP Jul 23 '20 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.