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

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.

Write $(x^{T}b{)}^2=x^{T}b{b}^{T}x$ and put $C=A-b{b}^T$, which is symmetric. Differentiating this quadratic form givesUnlike $A$, $C$ need not be a positive-definite matrix. Its behaviour must be checked before classifying the stationary point.

The gradient vanishes at $0$. Decompose any vector as $x=tb+w$, with $w\perp b$. Symmetry of $A$ and $Ab=\frac{1}{2}b$ imply $b^{T}Aw=(Ab{)}^{T}w=0$. Since $\Vert b\Vert =1$,If $d\ge 2$, choose a nonzero $w\perp b$. Arbitrarily close to zero, the direction $b$ gives negative values and the direction $w$ gives positive values. Thus $0$ is a saddle point for $d\ge 2$. Equivalently, the Hessian matrix has one negative eigenvalue and all its other eigenvalues positive.

The dimension matters: if $d=1$, the orthogonal complement is zero-dimensional and $g(tb)=-t^2/2$. In that case $0$ is the unique global maximum. This edge case is not excluded by the stated hypotheses. The decomposition is a rank-one downdate along an eigenvector.

The matrix $C=A-b{b}^T$ is an invertible matrix. Indeed, on the line spanned by $b$ it has eigenvalue $-1/2$, and on $b^{\perp }$ it agrees with the positive-definite restriction of $A$. Therefore the full Newton step is well defined and givesThis is the unique stationary point because $C$ is an invertible matrix. The algebra applies to every starting point, but it does not make the answer a minimum: for $d\ge 2$ it is the saddle point just classified, and for $d=1$ it is a maximum. A safeguarded minimization algorithm that replaces an indefinite matrix used as its Hessian matrix or damps the step need not take this exact step; the assertion concerns the ordinary full Newton step formula.

Put $q(x)=x^{T}Ax$ and $t(x)=x^{T}b$. The product rule givesDifferentiate each term. The derivative of $2tAx$ is $2(Ax)b^T+2tA$, while that of $qb$ is $2b(Ax{)}^T$. HenceThe last two terms are transposes of each other, so this Hessian matrix is symmetric, as expected.

At $x=0$, the gradient from the preceding part vanishes and the Hessian matrix is zero. The second-order test is therefore inconclusive. Instead inspect the eigenline:For arbitrarily small positive and negative $t$, these values have opposite signs. Thus $0$ is neither a local maximum nor a local minimum. In dimension at least two it is a degenerate saddle point; in one dimension it is a stationary inflection point. Looking only at the zero Hessian matrix would not determine this classification.

Use mathematical induction on the iteration. Initially $x_0=b=1\cdot b$. If $x_n={\lambda }_{n}b$, then $A{x}_n={\lambda }_{n}b/2$, $x_n^{T}b={\lambda }_n$, and $x_n^{T}A{x}_n={\lambda }_n^2/2$. ThereforeA gradient descent step with any scalar step length ${\alpha }_n$ consequently has the formThus every iterate remains on the same eigenline, withThis proves that gradient descent preserves an eigenline for a cubic product. The statement is invariance, not convergence to a minimum: along the negative direction of this line the cubic polynomial objective is unbounded below.