Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2007 / B / 7 / iii

The backtracking line search starts with ${\alpha }_{\mathrm{init}}>0$, tests the Armijo condition, and repeatedly replaces a failed step by $\tau \alpha$, with fixed $\tau \in (0,1)$. It accepts the first step that passes. Backtracking makes an overambitious trial step small enough for a local linear model to predict the change reliably; part (ii) ensures finite termination. The Armijo condition guarantees a decrease of at least $-\alpha \beta g^{T}p>0$ along a nonzero descent direction. Merely obtaining some decrease without this quantitative lower bound would not provide the convergence estimate in the following parts.