 Solution

ID: past-exam-of-the-numerical-linear-algebra-and-continuous-optimisation-course-of-the-university-of-oxford/2007/b/5/iv/solution

The true quadratic has

g (x) = c + H x

and the exact expansion

f (x + s) = f (x) + g (x)^{T} s + \frac{1}{2} s^{T} Hs .

Subtracting the model with Hessian

I

yields

f (x + s) - m (s) = \frac{1}{2} s^{T} (H - I) s

. Since

H

is symmetric positive definite and

∥ H ∥_{2} = 1

, its eigenvalues lie in

(0, 1]

, so

∥ H - I ∥_{2} \leq 1

. Therefore

∣ f (x + s) - m (s) ∣ \leq \frac{1}{2} ∥ s ∥_{2}^{2} \leq \frac{1}{2} Δ^{2} \leq Δ^{2} .

In fact the stated assumptions give a factor one-half better than the requested bound.

 New to topics? Read the docs here!