Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 5 / a

Use compatible dimensions $A\in {\mathbb{R}}^{d\times d}$ and $b,x\in {\mathbb{R}}^d$; the printed “b-by-b” size is read consistently with the displayed products and domain. Take derivatives as column gradients. Symmetry of $A$ givesFor example, the directional differential of $x^{T}Ax$ is $d{x}^{T}Ax+x^{T}Adx=2(Ax{)}^{T}dx$. The linear term contributes $b$ to the gradient and zero to the Hessian matrix.

The eigenvector identity $Ab=\frac{1}{2}b$ gives $\nabla f(-b)=-2Ab+b=0$. Since $H_f=2A$ is a positive-definite matrix, this is a strict local minimum. A global certificate follows by completing the quadratic form:Positive definiteness makes the first term nonnegative, with equality only at $x=-b$. Thus $-b$ is the unique global minimum, with value $-1/2$.

The full, undamped Newton's method in optimization step isThe eigenvector identity gives $A^{-1}b=2b$. Consequently $x_1=-b$ for every starting point. This is a one-step Newton solution of a quadratic stationary equation: its gradient is an affine function, so a single exact Newton solve resolves it completely.