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

The derivative is represented by the gradient, and the Hessian matrix contains the second partial derivatives:Equivalently the derivative as a linear map is $Df(x,y)(u,v)=(4x^3-4y)u+(4y-4x)v$.

The stationary point equations give $y=x$ and $x^3=x$, hence $(0,0),(1,1),(-1,-1)$. At $(0,0)$ the Hessian matrix has negative determinant $-16$, so $(0,0)$ is a saddle point. At each of $(1,1)$ and $(-1,-1)$, the Hessian matrix has positive leading minors $12$ and $32$, proving a strict local minimum. More strongly,Thus $(1,1)$ and $(-1,-1)$ are exactly the global minima, with value $3$. There are no local maxima, since any differentiable interior local maximum would be a stationary point, and all three have been classified.

For the equality-constrained minimization problem, $y=8/x$ and $x\ne 0$. Put $t=x^2>0$. The restricted objective isThe only zero has $t^3=64$, so $t=4$. Since $F^{\prime \prime }(t)=2+256/t^3>0$, the second-derivative criterion for convexity proves a unique minimizing $t$. Consequently the equality constraint has minimizers $(2,4)$ and $(-2,-4)$, with minimum $20$.

For the inequality-constrained minimization problem, the identity $f=(x^2-1{)}^2+2(y-x{)}^2+3$ supplies the universal lower bound $3$. Both equality points for that bound, $(1,1)$ and $(-1,-1)$, satisfy $xy=1\le 8$. Hence the inequality constraint has exactly these two minimizers, with minimum $3$.

For Newton's method in optimization, let $\Delta =H(f{)}^{-1}\nabla f$. Its second row equation is $-4{\Delta }_x+4{\Delta }_y=4y-4x$, so ${\Delta }_y={\Delta }_x+y-x$. Therefore $y_{n+1}=y_n-{\Delta }_y=x_n-{\Delta }_x=x_{n+1}$. The given first coordinate yieldsThe Newton step is defined where $\det H(f)=16(3x^2-1)\ne 0$; both coordinates after any defined step are equal.

By the diagonal reduction in a two-variable Newton iteration, $y_n=x_n$ for $n\ge 1$. Put $e_n=x_n-1$. Direct factorization gives the exact Newton map in optimization error identityThe assumed convergence $x_n\to 1$ makes the final factor tend to $3/2$, so it is bounded for all sufficiently large $n$. Hence $|e_{n+1}|\le C|e_n{|}^2$. For the Euclidean norm error $E_n=\Vert (x_n,y_n)-(1,1)\Vert =\sqrt{2}|e_n|$, this becomes $E_{n+1}\le (C/\sqrt{2})E_n^2$, proving quadratic convergence. Unless the exact limit is reached in finitely many steps, $E_{n+1}/E_n^2\to 3/(2\sqrt{2})$.