Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 6

For a differentiable scalar function of $n$ real variables, its derivative is the linear mapwhere the column gradient is $\nabla f=(\partial f/\partial x_1,\dots ,\partial f/\partial x_n{)}^T$. Its Hessian is the $n\times n$ matrix $H_f=({\partial }^{2}f/\partial x_i\partial x_j{)}_{i,j}$. For a $C^2$ function, equality of mixed partial derivatives makes this matrix symmetric.

Put $\mathbf{z}=(x,y{)}^T$, $r^2={\mathbf{z}}^T\mathbf{z}$ and $f=\sqrt{1+r^2}$. The chain rule yieldsFor every nonzero vector $\mathbf{v}$, the Cauchy-Schwarz inequality givesThus the Hessian is a positive-definite matrix everywhere. The Hessian criterion for convexity implies that $f$ is strictly convex on ${\mathbb{R}}^2$. Its unique global minimum is at $\mathbf{z}=0$, where $f=1$.

Let $P=\mathbf{z}{\mathbf{z}}^T$, so $P^2=r^{2}P$ and $f^2=1+r^2$. Multiplying the proposed inverse matrix by the Hessian givesHence $H_f^{-1}=f(I+\mathbf{z}{\mathbf{z}}^T)=f\left(\begin{array}{cc}1+x^2& xy\\ xy& 1+y^2\end{array}\right)$, as required. Its existence also follows from the Hessian being a positive-definite matrix.

For iterates approaching ${\mathbf{x}}_{\ast }$, write $e_k=\Vert {\mathbf{x}}_k-{\mathbf{x}}_{\ast }\Vert$. Exact order of convergence $p$ means $e_{k+1}/e_k^p\to C$ for a finite constant $C>0$, with nonzero errors. Thus quadratic convergence has $p=2$, and cubic convergence has $p=3$. The weaker eventual bound $e_{k+1}\le C{e}_k^p$ means at least order $p$. Finite termination is a separate case.^[ref]

The assertion about being always faster is false. For example, the fixed-point iterations with errors $e_{k+1}=e_k^2$ and $d_{k+1}=50d_k^3$ have exact quadratic convergence and cubic convergence, respectively. Starting both at $0.1$, their next errors are $0.01$ and $0.05$: the cubic convergence method is worse on that step, although both converge. Error constants, starting points, and work per step all matter. The higher order of convergence describes asymptotic behavior within a convergence region, not a uniform comparison of all computations.

The update in Newton's method in optimization is ${\mathbf{z}}_{k+1}={\mathbf{z}}_k-H_f({\mathbf{z}}_k{)}^{-1}\nabla f({\mathbf{z}}_k)$. Substituting the previous formulas givesThus the distance from the unique minimum obeys $r_{k+1}=r_k^3$, where $r_k=\Vert {\mathbf{z}}_k\Vert$. In particular,For $0<r_0<1$, the error ratio $r_{k+1}/r_k^3$ is exactly $1$, proving exact cubic convergence. If $r_0=0$, the initial point already attains the minimum. All updates are defined because the Hessian is invertible everywhere. This is Newton minimization of the square-root norm; its special update also shows why the given initial condition matters: $r_0=1$ produces an alternating two-cycle, and $r_0>1$ diverges.