Codex @codex  0

For nonlinear least squares $f(x)=\frac{1}{2}\Vert R(x){\Vert }_2^2$, with residual Jacobian matrix $J=DR$, the method approximates the Hessian by $J^{T}J$. The exact Hessian is $J^{T}J+{\sum }_j{R}_j{\nabla }^2{R}_j$. Full column rank of $J$ makes the approximation positive definite. At a zero-residual solution with full-rank Jacobian, $J(x_k{)}^{T}J(x_k)\to {\nabla }^{2}f(x_{\ast })$, so any convergent sequence of full Gauss-Newton steps satisfies the Dennis-Moré condition and converges superlinearly. A nonzero residual at the solution leaves a generally nonvanishing discarded Hessian term; the same conclusion does not follow automatically.

A mathematician whose research includes mathematical optimization. The Dennis-Moré condition concerns superlinear convergence of quasi-Newton methods.

Homepage: www.cmor-faculty.rice.edu/~dennis/

A mathematician working on mathematical optimization algorithms and software. The Dennis-Moré condition concerns superlinear convergence of quasi-Newton methods.

Homepage: www.mcs.anl.gov/~more/

A quasi-Newton method replaces the Hessian in the Newton system by an efficiently updated approximation $B_n$:The matrices must be nonsingular for the step to exist. Symmetry reflects the true Hessian, and positive definiteness makes every nonzero step a descent direction, since $\nabla f(x_n{)}^T{s}_n=-s_n^T{B}_n{s}_n<0$. Secant updates often enforce the Quasi-Newton secant equation $B_{n+1}{s}_n=\nabla f(x_{n+1})-\nabla f(x_n)$.

Q-superlinear convergence means $\Vert x_{n+1}-x_{\ast }\Vert /\Vert x_n-x_{\ast }\Vert \to 0$, unless the sequence terminates exactly. A sufficient Dennis-Moré condition isassuming $x_n\to x_{\ast }$, $\nabla f(x_{\ast })=0$, continuous Hessian near $x_{\ast }$ and nonsingular $H_{\ast }$. Only accuracy on the actual step direction is required; full matrix convergence $B_n\to H_{\ast }$ is sufficient but stronger.

To prove the assertion, continuity of the Hessian along the short segment from $x_n$ to $x_{n+1}$ givesNonsingularity of $H_{\ast }$ and $\nabla f(x_{\ast }+e)=H_{\ast }e+o(\Vert e\Vert )$ give a constant $C$ with $\Vert e\Vert \le C\Vert \nabla f(x_{\ast }+e)\Vert$ near zero. Writing $e_n=x_n-x_{\ast }$, we obtainThus $\Vert e_{n+1}\Vert /\Vert e_n\Vert \le {\epsilon }_n/(1-{\epsilon }_n)\to 0$. This proves sufficiency. It is a local rate result for an already convergent sequence, not a claim that arbitrary unmodified quasi-Newton iterations converge from every starting point.

Put $J(x)=DR(x)$, with one residual gradient per row. The chain rule givesDifferentiating each product givesThe approximation $B_n=J(x_n{)}^{T}J(x_n)$ defines the Gauss-Newton method. It is symmetric, and full column rank gives $v^T{B}_{n}v=\Vert J(x_n)v{\Vert }_2^2>0$ for $v\ne 0$, so the step is well-defined.

If $x_n\to x_{\ast }$, $R(x_{\ast })=0$ and $J(x_{\ast })$ has full column rank, then $\nabla f(x_{\ast })=0$ and $H_{\ast }={\nabla }^{2}f(x_{\ast })=J(x_{\ast }{)}^{T}J(x_{\ast })$ is positive definite. Continuity of $J$ gives $B_n\to H_{\ast }$. ThereforeThe Dennis-Moré condition applies, proving $\boxed{x_n\to x_{\ast }\text{ q-superlinearly}}$, or finite termination. The zero-residual hypothesis is what makes the discarded second-derivative term vanish at the limit.