Exact safeguarded Levenberg-Marquardt iterates approach stationarity on compact sublevels

Let $\mathrm{\Psi }(y)=\mathrm{\parallel }y{\mathrm{\parallel }}_2^2\mathrm{/}2$. The identity $\mathrm{\Psi }(y+z)-\mathrm{\Psi }(y)-⟨y,z⟩=\mathrm{\parallel }z{\mathrm{\parallel }}_2^2\mathrm{/}2=o(\mathrm{\parallel }z{\mathrm{\parallel }}_2)$ gives $D\mathrm{\Psi }(y)[z]=⟨y,z⟩$. Since $r$ is $C^1$ and $J=Dr$, the chain rule yields $D\varphi (x)[h]=⟨r(x),J(x)h⟩=(J(x{)}^{T}r(x){)}^{T}h$, so $\mathrm{\nabla }\varphi =J^{T}r$. At a nonstationary $x_k\in S$, [F2] shows that the iteration either accepts an earlier trial or accepts once $\lambda \ge \mathrm{\Lambda }$, within $N$ attempts. Thus no rejection-budget status occurs. The accepted actual reduction is $\rho \mathrm{pred}\ge {\eta }_1\mathrm{pred}>0$ by [F1], so $\varphi (x_{k+1})<\varphi (x_k)\le \varphi (x_0)$ and $x_{k+1}\in S$. Induction keeps all iterates in $S$.

The damping remains at least ${\lambda }_{\min }$ by [F1]. If ${\lambda }_k\ge \mathrm{\Lambda }$, [F2] accepts the trial with $\mathrm{\parallel }D{p}_k{\mathrm{\parallel }}_2\le \mathrm{\Delta }\mathrm{/}2$, so it is not a boundary step and the damping is unchanged. If ${\lambda }_k<\mathrm{\Lambda }$, every rejection multiplies it by $\gamma$; the first value reaching $\mathrm{\Lambda }$ is less than $\gamma \mathrm{\Lambda }$, and [F2] accepts that interior trial without decreasing the damping. An earlier accepted step either preserves ${\lambda }_k$ or decreases it to at least ${\lambda }_{\min }$. Hence every damping used satisfies ${\lambda }_{\min }\le {\lambda }_k\le {\lambda }_{\max }:=\max \{{\lambda }_0,\gamma \mathrm{\Lambda }\}$.

For an accepted nonstationary step, [F3] gives $\mathrm{pred}\ge {\lambda }_k\mathrm{\parallel }D{p}_k{\mathrm{\parallel }}_2^2\ge {\lambda }_{\min }{d}^2\mathrm{\parallel }{p}_k{\mathrm{\parallel }}_2^2$. Its normal equation is $J^{T}r=-(J^{T}J+{\lambda }_k{D}^{T}D)p_k$; [F6] gives $\mathrm{\parallel }{J}^T{\mathrm{\parallel }}_2=\mathrm{\parallel }J{\mathrm{\parallel }}_2\le M$, so submultiplicativity [F5] gives $\mathrm{\parallel }{J}^{T}r{\mathrm{\parallel }}_2\le (M^2+{\lambda }_{\max }{d}_{+}^2)\mathrm{\parallel }{p}_k{\mathrm{\parallel }}_2$. Combining these inequalities yields $\mathrm{pred}\ge c\mathrm{\parallel }{J}^{T}r{\mathrm{\parallel }}_2^2$ with the stated $c>0$.

Multiplying step 3.1 by $\rho \ge {\eta }_1$ proves the sufficient-decrease inequality in the Statement. Summing it over $k=0,\dots ,K-1$ telescopes and uses $\varphi (x_K)\ge 0$, giving ${\eta }_{1}c{\sum }_{k<K}\mathrm{\parallel }J(x_k{)}^{T}r(x_k){\mathrm{\parallel }}_2^2\le \varphi (x_0)$. The nonnegative series is bounded, so its terms tend to zero. For $y\to x$ in $U$, [F5]–[F6] give $\mathrm{\parallel }J(y{)}^{T}r(y)-J(x{)}^{T}r(x){\mathrm{\parallel }}_2\le \mathrm{\parallel }J(y){\mathrm{\parallel }}_2\mathrm{\parallel }r(y)-r(x){\mathrm{\parallel }}_2+\mathrm{\parallel }J(y)-J(x){\mathrm{\parallel }}_2\mathrm{\parallel }r(x){\mathrm{\parallel }}_2\to 0$ by [F9], since $J(y)$ is locally bounded. Thus if a subsequence $x_{k_j}$ converges to $\bar{x}\in S\subset U$, continuity gives $J(\bar{x}{)}^{T}r(\bar{x})=0$.

To verify the limitation under the hypotheses, take $U=\mathbb{R}$, $r(t)=(t,1)$, and $x_0=0$. Then $\varphi (t)=(t^2+1)\mathrm{/}2$, $S=\{0\}$, $S_1=[-1,1]$, $J=(1,0{)}^T$, and $J^{T}r(0)=0$ while $\mathrm{\parallel }r(0){\mathrm{\parallel }}_2=1$. On $S_1$ take $L=0$, $M=1$, and $R_0=\sqrt{2}$; set $D=1$, $d=d_{+}=1$, ${\lambda }_{\min }={\lambda }_0=1$, $\gamma =2$, ${\eta }_1=1\mathrm{/}4$, ${\eta }_2=3\mathrm{/}4$, and $\mathrm{\Delta }=1$. These bounds give $P=1\mathrm{/}2$, $\mathrm{\Lambda }=2\sqrt{2}$, and finite cap $N=3$. The iteration returns stationary immediately, with nonzero residual. Thus even under the stated compact-sublevel and finite-attempt conditions the conclusion cannot be strengthened to $r(x_k)\to 0$.