Past exam of the mathematics course of the University of Cambridge / 2024 / ib / Paper 4 / 18H / a

Table of contents
- Solution a

Solution

Newton's method for minimization uses

x_{k + 1} = x_{k} - [\nabla^{2} f (x_{k})]^{- 1} \nabla f (x_{k}) .

For a quantitative local bound, suppose on a convex neighbourhood containing the iterates that

m I ⪯ \nabla^{2} f (x) ⪯ L I, ∥ \nabla^{2} f (x) - \nabla^{2} f (y) ∥ \leq M ∥ x - y ∥,

with

m > 0

, and let

x^{*}

be the minimizer. The integral form of the gradient and the Hessian Lipschitz bound give the quadratic convergence bound for Newton's method

∥ x_{k + 1} - x^{*} ∥ \leq \frac{M}{2 m} ∥ x_{k} - x^{*} ∥^{2} .

If

q = M ∥ x_{0} - x^{*} ∥/ (2 m) < 1

, induction yields

∥ x_{k} - x^{*} ∥ \leq \frac{2 m}{M} q^{2^{k}} .

Since

f (x) - f (x^{*}) \leq L ∥ x - x^{*} ∥^{2} /2

,

f (x_{k}) - f (x^{*}) \leq \frac{2 L m ^{2}}{M ^{2}} q^{2^{k + 1}} .

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version