 Solution

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

The descent lemma follows by integrating the gradient along the line and using its Lipschitz continuity:

f (x + α p) \leq f (x) + αg (x)^{T} p + \frac{γ}{2} α^{2} ∥ p ∥_{2}^{2}, α \geq 0.

This upper bound is at most the right side of the Armijo condition when

α [(1 - β) g^{T} p + γ α ∥ p ∥_{2}^{2} /2] \leq 0

. Since

g^{T} p < 0

, it holds for

0 \leq α \leq α_{m a x} = \frac{2 ( 1 - β ) ( - g ^{T} p )}{γ ∥ p ∥ _{2}^{2}} = \frac{2 ( β - 1 ) g ^{T} p}{γ ∥ p ∥ _{2}^{2}} .

The zero step gives equality; every positive step in this interval satisfies the prescribed sufficient-decrease test.

 New to topics? Read the docs here!