Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2010 / B / 4 / iv / Solution

If the first trial is accepted, ${\alpha }_k={\alpha }_{\mathrm{init}}$. Otherwise the preceding trial was rejected and so exceeded ${\alpha }_{\max }$, since part (ii) guarantees acceptance below that threshold. The accepted step, reduced by the factor $\tau$, consequently exceeds $\tau {\alpha }_{\max }$. In either case,The angle condition $-g_k^T{p}_k\ge \epsilon \Vert g_k{\Vert }_2\Vert p_k{\Vert }_2$ gives ${\alpha }_{\max }\ge 2\epsilon (1-\beta )\Vert g_k{\Vert }_2/(\gamma \Vert p_k{\Vert }_2)$. Hence the backtracking line search has the lower bound