TransWikia.com

Convergence of Truncated Newton for non-convex Hessian

Computational Science Asked by RockedSalad121 on June 19, 2021

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP