Past exam of the mathematics course of the University of Cambridge / 2024 / ib / Paper 4 / 18H (Optimisation)

Newton's method for minimization usesFor a quantitative local bound, suppose on a convex neighbourhood containing the iterates thatwith $m>0$, and let $x^{\ast }$ be the minimizer. The integral form of the gradient and the Hessian Lipschitz bound give the quadratic convergence bound for Newton's methodIf $q=M\Vert x_0-x^{\ast }\Vert /(2m)<1$, induction yieldsSince $f(x)-f(x^{\ast })\le L\Vert x-x^{\ast }{\Vert }^2/2$,

If $x_k\ge 1$, then positivity and the arithmetic-geometric mean inequality giveThus all iterates remain in $[1,\infty )$.

Consider the strictly convex functionon $[1,\infty )$. Since $f^{\prime }(x)=x^2-a$ and $f^{\prime \prime }(x)=2x$, its Newton minimization step isIts unique minimizer is $x^{\ast }=\sqrt{a}$.

Every $x_0\in [1,\infty )$ works. Indeed, $x_1\ge \sqrt{a}$, and whenever $x_k\ge \sqrt{a}$,The iterates from $k=1$ onward therefore decrease to a limit, and the recurrence forces that limit to be $\sqrt{a}$.

There is also an explicit error bound. PutA direct calculation givesHence, for $k\ge 1$,This double-exponential decay is consistent with the Newton bound in part (a). For the chosen objective, the supplied factorization also givesso convergence of the objective and convergence of the iterates are equivalent on $[1,\infty )$.