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 / c

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.