Regularized nonlinear Levenberg–Marquardt — Examples and Counterexamples

Completing the square gives $\frac{1}{2}\mathrm{\mid }\epsilon h-r{\mathrm{\mid }}^2+\frac{\alpha }{2}\mathrm{\mid }h{\mathrm{\mid }}^2=\frac{{\epsilon }^2+\alpha }{2}{(h-\frac{\epsilon r}{{\epsilon }^2+\alpha })}^2+\frac{r^2}{2}-\frac{{\epsilon }^2{r}^2}{2({\epsilon }^2+\alpha )}\mathrm{.}$ Since ${\epsilon }^2+\alpha >0$, the unique minimizer is $h_{\alpha }=\epsilon r\mathrm{/}({\epsilon }^2+\alpha )$.

By [F4], $2\epsilon \sqrt{\alpha }\le {\epsilon }^2+\alpha$, so $\mathrm{\mid }{h}_{\alpha }\mathrm{\mid }=\epsilon r\mathrm{/}({\epsilon }^2+\alpha )\le r\mathrm{/}(2\sqrt{\alpha })\le \delta \mathrm{/}(2\sqrt{\alpha })$, with a bound independent of $\epsilon$. The unregularized linearized equation $\epsilon h_0=r$ instead gives $\mathrm{\mid }{h}_0\mathrm{\mid }=r\mathrm{/}\epsilon \le \delta \mathrm{/}\epsilon$, which is unbounded as $\epsilon \downarrow 0$ for fixed $r>0$.

The linearized residual after the regularized step is $\epsilon h_{\alpha }-r=-\alpha r\mathrm{/}({\epsilon }^2+\alpha )$. Since $r>0$, the residual-forcing equality is equivalent to $\alpha \mathrm{/}({\epsilon }^2+\alpha )=\sigma$, hence $\alpha =\sigma {\epsilon }^2\mathrm{/}(1-\sigma )$ and $h_{\alpha }=(1-\sigma )r\mathrm{/}\epsilon$. This forcing-selected step grows like $1\mathrm{/}\epsilon$ when $r$ is held fixed; the fixed-$\alpha$ bound above does not give a uniform bound for this varying-parameter family.

For the finite safeguarded procedure, the augmented matrix is the column $A=(\epsilon ,\sqrt{\alpha }{)}^T$. Put $s:=\sqrt{{\epsilon }^2+\alpha }$, $Q:=A\mathrm{/}s$, and $R:=(s)$. Then $s>0$, $Q^{T}Q=1$, and $QR=A$, so $A=QR$ is an exact reduced QR factorization. Its augmented residual vector is $b=(-r,0{)}^T$, and the exact damped least-squares minimizer is the same $p=h_{\alpha }$ from step 1.1.

Take residual map $g(t)=\epsilon t-y^{\delta }$, Jacobian $J=\epsilon$, $D=1$, current damping $\lambda =\alpha$, a floor $0<{\lambda }_{\min }\le \alpha$, factors $\gamma =2$, ${\eta }_1=1\mathrm{/}4$, ${\eta }_2=3\mathrm{/}4$, trust radius $\mathrm{\Delta }>\mathrm{\mid }{h}_{\alpha }\mathrm{\mid }$, and one allowed attempt. The exact gradient is nonzero since $J^{T}g(x)=-\epsilon r\mathrm{\ne }0$. The model residual equals the actual residual because $g$ is affine. The predicted reduction is positive because $\mathrm{\mid }\epsilon h_{\alpha }-r\mathrm{\mid }=\alpha r\mathrm{/}({\epsilon }^2+\alpha )<r$, so the actual-to-predicted ratio is $1$. The trial lies inside the trust radius, hence it is accepted and does not meet the boundary condition for lowering damping; it returns the same damping $\lambda =\alpha$.

The derivative of $F(t)=t$ is $F^{\mathrm{\prime }}(t)=1$, so $F(u)-F(\tilde{u})-F^{\mathrm{\prime }}(u)(u-\tilde{u})=0$ for every $u,\tilde{u}\in \mathbb{R}$. Thus the product condition holds on $B_2(x_0)\subset \mathbb{R}$ with $c=1$, and $\mathrm{\mid }{F}^{\mathrm{\prime }}(t)\mathrm{\mid }=1=M$. The exact solution lies in $B_1(x_0)$ and $B_2(x_0)\subset U$. Also $e_0=\mathrm{\mid }{x}_0-x^{†}\mathrm{\mid }=1\mathrm{/}16<1$, while $\frac{\sigma \tau -1}{c(1+\tau )}=\frac{1}{8},\frac{1-\sigma }{2c}=\frac{1}{4},$ so the theorem's local smallness clauses hold. Its positive-noise clause does not hold because $\delta =0$.

Let $r_n:=1-x_n$. If $r_n>0$, the objective is $\frac{1}{2}(h-r_n{)}^2+\frac{{\alpha }_n}{2}{h}^2$. Completing the square gives the unique minimizer $h_n=r_n\mathrm{/}(1+{\alpha }_n)$ and $r_n-h_n={\alpha }_n{r}_n\mathrm{/}(1+{\alpha }_n)$. The forcing equation with $\sigma =1\mathrm{/}2$ therefore requires ${\alpha }_n=1$ and gives $h_n=r_n\mathrm{/}2$.

Since $x_0=1-1\mathrm{/}16$, $r_0=1\mathrm{/}16>0$. Whenever $r_n>0$, step 1.2 gives $r_{n+1}=1-x_{n+1}=r_n-h_n=r_n\mathrm{/}2$. By induction, $r_n=2^{-n}\mathrm{/}16>0$ for every finite $n$. Therefore $\mathrm{\mid }F(x_n)-y^{\delta }\mathrm{\mid }=r_n>0=\tau \delta$ at every finite index, so no discrepancy crossing occurs. This refutes the stated finite-stopping extension to zero noise.