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

The quadratic model has gradient $g(x_k)+B_{k}p$ and positive-definite Hessian matrix $B_k$. Its unique minimizer is thereforeIf $g(x_k)\ne 0$, then $p_k\ne 0$ and $g(x_k{)}^T{p}_k=-p_k^T{B}_k{p}_k<0$, proving that it is a descent direction.

Backtracking line search starts with a trial step and repeatedly reduces it until the Armijo condition holds. Part (ii) guarantees finite termination because sufficiently small steps are acceptable. The test guarantees a specified positive fraction of the decrease predicted by the linear model, namely $f(x_k+\alpha p_k)\le f(x_k)+\alpha \beta g(x_k{)}^T{p}_k<f(x_k)$ for an accepted positive step. It does not require solving the line-minimization problem exactly.