Finite-budget inexact Newton–Krylov with a descent safeguard

Let $n\ge 1$, let $U\subseteq {\mathbb{R}}^n$ be open, and let $f:U\to \mathbb{R}$ be twice continuously differentiable, meaning that $f$ is $C^1$ and its gradient is $C^1$. Write $g(x):=\mathrm{\nabla }f(x)$ and $H(x):={\mathrm{\nabla }}^{2}f(x)$ using The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case and The Hessian matrix and critical points of a scalar field. The identity matrix $I_n$ and matrix-vector products have the convention of Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes. Use the matrix-free access model of The matrix-free access model for Krylov methods for products $v\mapsto (H(x)+\lambda I_n)v$.

Linear-solver input: a fixed deterministic Krylov procedure $K$ which accepts a matrix-free linear operator $A$, a right-hand side $b$, a tolerance $\tau \ge 0$, and a finite inner-iteration budget $M\in {\mathbb{N}}_0$. It returns either no-candidate or candidate with a vector $p$ and an iteration count $m\in \{0,1,\dots ,M\}$ satisfying $p\in K_m(A,b)$, where $K_m$ is as defined by The Krylov subspace $K_m(A,b)=\mathrm{span}\{b,Ab,\dots ,A^{m-1}b\}$. A candidate's residual status is never trusted: this algorithm recomputes the requested residual using the supplied operator. Other inputs: $x_0\in U$, outer update budget $N\in {\mathbb{N}}_0$, forcing values ${\eta }_k\in [0,\bar{\eta }]$ for a fixed $0\le \bar{\eta }<1$, descent parameter $\sigma \in (0,1)$, regularization factor $\gamma >1$, initial shift ${\lambda }_0>0$, shift cap ${\lambda }_{\max }\ge {\lambda }_0$, regularized-attempt budget $J\in {\mathbb{N}}_0$, inner budget $M$, and the parameters and finite expansion/zoom budgets of Finite-budget bracketing and zoom for a strong Wolfe step. Output: the last valid iterate and one of stationary, iteration-budget-exhausted, no-descent-direction, or line-search-failure; in the last case also return the underlying line-search failure cause.

At iteration $k=0,1,\dots ,N$:

1. Compute $g_k:=g(x_k)$. If $g_k=0$, return $(x_k,\mathtt{\text{stationary}})$. If $k=N$, return $(x_k,\mathtt{\text{iteration-budget-exhausted}})$.
2. Set $\lambda :=0$. For $j=0,1,\dots ,J$, call $K$ on $A_{\lambda }v:=H(x_k)v+\lambda I_{n}v$, right-hand side $-g_k$, tolerance ${\eta }_k\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2$, and budget $M$. A no-candidate result is a rejected attempt. If it returns a candidate $p$, compute $r:=(H(x_k)+\lambda I_n)p+g_k$. Accept this linear solve only when $\mathrm{\parallel }r{\mathrm{\parallel }}_2\le {\eta }_k\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2$ and $⟨g_k,p⟩<-\sigma \mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{\parallel }p{\mathrm{\parallel }}_2$; otherwise reject it. If the attempt is accepted, retain this $p$ and immediately leave the regularization loop. If the attempt is rejected and either $j=J$ or $\lambda ={\lambda }_{\max }$, stop the regularization loop. Otherwise set $\lambda :=\min \{{\lambda }_{\max },{\lambda }_0\}$ when $\lambda =0$, and $\lambda :=\min \{{\lambda }_{\max },\gamma \lambda \}$ when $\lambda >0$; then continue with the next $j$.
3. If no attempt in step 2 was accepted, set $p:=-g_k$ and check $⟨g_k,p⟩<-\sigma \mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{\parallel }p{\mathrm{\parallel }}_2$. If this check fails, return no-descent-direction. For the stated $\sigma$ and $g_k\mathrm{\ne }0$ it passes, but the check remains part of the procedure.
4. Call Finite-budget bracketing and zoom for a strong Wolfe step at $x_k$ in direction $p$. If it returns failure, return $(x_k,\mathtt{\text{line-search-failure}},s)$, where $s$ is the returned line-search failure cause. Otherwise, for its returned strong Wolfe step $t_k$, set $x_{k+1}:=x_k+t_{k}p$ and continue.

The first unregularized system uses the forcing residual $\mathrm{\parallel }H(x_k)p+g_k{\mathrm{\parallel }}_2\le {\eta }_k\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2$. A regularized attempt checks the residual for the shifted system instead. Finite inner, regularization, and line-search budgets can return failure; the procedure makes no global convergence claim. The local rate theorem applies only to an unshifted $\lambda =0$ sequence taking full steps $t_k=1$ and remaining in its stated local tube. This algorithm does not assert that every run enters that branch.