 Solution

ID: past-exam-of-the-numerical-linear-algebra-and-continuous-optimisation-course-of-the-university-of-oxford/2010/b/4/v/solution

From

B_{k} p_{k} = - g_{k}

and the matrix 2-norm bound,

∥ g_{k} ∥_{2} \leq κ_{b} ∥ p_{k} ∥_{2}

, so

∥ p_{k} ∥_{2} \geq ∥ g_{k} ∥_{2} / κ_{b}

. Let

C = 2 τ ε (1 - β) / γ > 0

. The summand in the supplied decrease bound satisfies

min (α_{init}, C \frac{∥ g _{k} ∥ _{2}}{∥ p _{k} ∥ _{2}}) ∥ g_{k} ∥_{2} ∥ p_{k} ∥_{2} = min (α_{init} ∥ g_{k} ∥_{2} ∥ p_{k} ∥_{2}, C ∥ g_{k} ∥_{2}^{2}) \geq min (α_{init} / κ_{b}, C) ∥ g_{k} ∥_{2}^{2} .

Thus, with the fixed positive constant

c = βε min (α_{init} / κ_{b}, C)

c \sum_{k = 0}^{j} ∥ g_{k} ∥_{2}^{2} \leq f (x_{0}) - f (x_{j + 1}) \leq f (x_{0}) - in f f < \infty.

The nonnegative series therefore converges, forcing its terms to zero:

k \to \infty lim g (x_{k}) = 0.

The argument uses the given angle condition and upper bound on

∥ B_{k} ∥_{2}

; it does not need an additional uniform lower eigenvalue bound on

B_{k}

 New to topics? Read the docs here!