Gauss-Newton and Levenberg-Marquardt methods — Examples

At $x_{\ast }=(2,1)$, the residual components are $r_1=2-2=0$ and $r_2=2e^{-1}-2e^{-1}=0$. By [F2], the Jacobian is $J(a,k)=\left[\begin{array}{cc}1& 0\\ e^{-k}& -a{e}^{-k}\end{array}\right]$, hence $J(x_{\ast })=\left[\begin{array}{cc}1& 0\\ e^{-1}& -2e^{-1}\end{array}\right]$.

Put $c=e^{-1}>0$ and $s=\sqrt{1+c^2}$. Supply the exact reduced QR factorization $Q=\left[\begin{array}{cc}1\mathrm{/}s& c\mathrm{/}s\\ c\mathrm{/}s& -1\mathrm{/}s\end{array}\right]$ and $R=\left[\begin{array}{cc}s& -2c^2\mathrm{/}s\\ 0& 2c\mathrm{/}s\end{array}\right]$, for which $Q^{T}Q=I$ and $QR=J(x_{\ast })$; its diagonal entries are positive. The determinant of $J(x_{\ast })$ is $-2e^{-1}\mathrm{\ne }0$ by [F3], so the parameters are locally identifiable by the linearized model. Since $r(x_{\ast })=0$, the linearized least-squares objective is $\mathrm{\parallel }J(x_{\ast })p{\mathrm{\parallel }}_2^2\mathrm{/}2$, whose unique minimizer is $p=0$. By [F1], the supplied exact QR branch returns this step.

At $(0,0)$, $r=(-1,-2{)}^T$, $J=\left[\begin{array}{cc}1& 1\\ 2& 2\end{array}\right]$, and $J^{T}J=\left[\begin{array}{cc}5& 5\\ 5& 5\end{array}\right]$. The two columns of $J$ coincide, so its rank is $1<2$. Supply the exact reduced QR $Q=\frac{1}{\sqrt{5}}\left[\begin{array}{cc}1& -2\\ 2& 1\end{array}\right]$ and $R=\left[\begin{array}{cc}\sqrt{5}& \sqrt{5}\\ 0& 0\end{array}\right]$, which satisfies $Q^{T}Q=I$ and $QR=J$. The exact QR branch therefore returns rank-deficient. The objective is $\frac{5}{2}(a+b-1{)}^2$, whose minimizers are the full line $a+b=1$; hence the parameters are not separately identifiable. The linearized problem at $(0,0)$ is minimized whenever $p_1+p_2=1$, so it has no unique Gauss-Newton step.

For $D=I$ and $\lambda =1$, the augmented matrix and residual are $A_1=[J;I]$ and $s_1=[r;0]$. Supply the exact reduced QR $Q=\left[\begin{array}{cc}1\mathrm{/}\sqrt{6}& 1\mathrm{/}\sqrt{66}\\ 2\mathrm{/}\sqrt{6}& 2\mathrm{/}\sqrt{66}\\ 1\mathrm{/}\sqrt{6}& -5\mathrm{/}\sqrt{66}\\ 0& 6\mathrm{/}\sqrt{66}\end{array}\right]$ and $R=\left[\begin{array}{cc}\sqrt{6}& 5\mathrm{/}\sqrt{6}\\ 0& \sqrt{66}\mathrm{/}6\end{array}\right]$, which satisfies $Q^{T}Q=I$ and $A_1=QR$. The damped system is $\left[\begin{array}{cc}6& 5\\ 5& 6\end{array}\right]p=(5,5{)}^T$, whose unique solution is $p=(5\mathrm{/}11,5\mathrm{/}11{)}^T$. The linear model residual is $r+Jp=(-1\mathrm{/}11,-2\mathrm{/}11{)}^T$, so $m_0(0)=5\mathrm{/}2$, $m_0(p)=5\mathrm{/}242$, and $\mathrm{pred}=300\mathrm{/}121>0$. Since the residual is affine, the true residual at $(0,0)+p$ equals that linear model residual; therefore $\mathrm{ared}=\mathrm{pred}$ and $\rho =1$. Also $\mathrm{\parallel }p{\mathrm{\parallel }}_2=5\sqrt{2}\mathrm{/}11<1=\mathrm{\Delta }$, so the trial is feasible and is not a boundary step. By [F2]–[F3] it is accepted and $\lambda$ stays $1$.

Here $J(x)=(1,x{)}^T$, so $J(x{)}^{T}J(x)=1+x^2>0$ for every $x$. Also $J(x{)}^{T}r(x)=x+\frac{1}{2}x+\frac{1}{2}{x}^3=\frac{3}{2}x+\frac{1}{2}{x}^3$, which vanishes at $x_{\ast }=0$ while $r(0)=(0,1\mathrm{/}2{)}^T$ has norm $1\mathrm{/}2$.

For each $x$, the exact reduced QR supplied to the algorithm is $Q(x)=\frac{1}{\sqrt{1+x^2}}\left[\begin{array}{c}1\\ x\end{array}\right]$ and $R(x)=\sqrt{1+x^2}$, so $Q(x{)}^{T}Q(x)=1$ and $J(x)=Q(x)R(x)$. The scalar normal equation is $(1+x^2)p=-\frac{3}{2}x-\frac{1}{2}{x}^3$, so $p=-x(3+x^2)\mathrm{/}(2(1+x^2))$; the supplied QR branch returns this unique least-squares step. Adding $x$ gives $x_{+}=x(x^2-1)\mathrm{/}(2(1+x^2))$. For $0<\mathrm{\mid }x\mathrm{\mid }<1$, $\mathrm{\mid }{x}_{+}\mathrm{\mid }\mathrm{/}\mathrm{\mid }x\mathrm{\mid }=(1-x^2)\mathrm{/}(2(1+x^2))<1\mathrm{/}2$, so every such iterate stays in the interval and converges to zero.

The residual is polynomial, hence $C^2$ on $U=\mathbb{R}$, with $n=1$, $m=2$, and stationary point $x_{\ast }=0$ by step 1.1. On $B=[-1\mathrm{/}10,1\mathrm{/}10]$, both $\mathrm{\parallel }J(x){\mathrm{\parallel }}_2$ and $\mathrm{\parallel }J(x{)}^T{\mathrm{\parallel }}_2$ are at most $11\mathrm{/}10$, both are $1$-Lipschitz, and $\mathrm{\parallel }J(x)v{\mathrm{\parallel }}_2\ge \mathrm{\mid }v\mathrm{\mid }$; also $S(x)=1\mathrm{/}2+x^2\mathrm{/}2\le 101\mathrm{/}200$. Thus the local contraction theorem [F3] applies with $R=1\mathrm{/}10$, $M=11\mathrm{/}10$, $L=1$, $\sigma =1$, $\kappa =101\mathrm{/}200$, and $q=123\mathrm{/}200<1$.

As $x\to 0$ through nonzero values, $\mathrm{\mid }{x}_{+}\mathrm{\mid }\mathrm{/}\mathrm{\mid }x\mathrm{\mid }\to 1\mathrm{/}2$, whereas $\mathrm{\mid }{x}_{+}\mathrm{\mid }\mathrm{/}\mathrm{\mid }x{\mathrm{\mid }}^2=(1-x^2)\mathrm{/}(2\mathrm{\mid }x\mathrm{\mid }(1+x^2))\to +\mathrm{\infty }$. No finite quadratic error constant can therefore hold near the stationary point. This exact example shows that the linear rate in [F3] cannot generally be strengthened when the residual is nonzero.