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

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.