Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2009 / B / 5

A local minimizer of a differentiable function on ${\mathbb{R}}^N$ necessarily satisfies $\boxed{\nabla f(x_{\ast })=0}$. A sufficient condition for a strict local minimum is $\boxed{\nabla f(x_{\ast })=0,{\nabla }^{2}f(x_{\ast })\text{ positive definite}}$. Indeed, the second-order Taylor expansion has a strictly positive quadratic term that dominates its $o(\Vert x-x_{\ast }{\Vert }^2)$ remainder near $x_{\ast }$.

For Newton's method, solve $H_n{s}_n=-g_n$ with $H_n={\nabla }^{2}f(x_n)$, $g_n=\nabla f(x_n)$, and set $x_{n+1}=x_n+s_n$. A positive-definite Hessian makes this a descent direction; general Hessians may need modification or a separate line search for a globally useful method.

The sequence is q-quadratically convergent if there is $C<\infty$ such that $\Vert x_{n+1}-x_{\ast }\Vert \le C\Vert x_n-x_{\ast }{\Vert }^2$ eventually. Sufficient local hypotheses are $\nabla f(x_{\ast })=0$, a nonsingular $H_{\ast }={\nabla }^{2}f(x_{\ast })$, a Lipschitz continuous Hessian near $x_{\ast }$, and $x_0$ sufficiently close. For convergence to a local minimum take $H_{\ast }$ positive definite. Near $x_{\ast }$, inverse Hessians are uniformly bounded, and integration along the error segment givesA Hessian Lipschitz constant $L_H$ yields $\Vert x_{n+1}-x_{\ast }\Vert \le \frac{1}{2}{L}_H\Vert H_n^{-1}\Vert \Vert x_n-x_{\ast }{\Vert }^2$. Choosing a sufficiently small invariant neighborhood proves quadratic convergence. Continuous second derivatives alone do not guarantee this quadratic rate; the Lipschitz hypothesis supplies the needed remainder bound.

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.