Exact line search for a positive-definite quadratic (source code)

= Exact line search for a positive-definite quadratic

For $f(x)=x^TAx/2-b^Tx$ with a real <symmetric positive-definite matrix> $A$ and nonzero <linear-system residual> $r=b-Ax$, exact line search along $r$ uses
$$
t=\frac{r^Tr}{r^TAr}.
$$
The objective error contracts by
$$
1-\frac{(r^Tr)^2}{(r^TA^{-1}r)(r^TAr)}
\leq 1-\frac{\lambda_{\min}(A)}{\lambda_{\max}(A)}.
$$

The objective gap is $f(x)-f(x_*)=r^TA^{-1}r/2$, so the first ratio is exact. The spectral bounds $r^TA^{-1}r\leq\|r\|_2^2/\lambda_{\min}$ and $r^TAr\leq\lambda_{\max}\|r\|_2^2$ prove the displayed inequality. At $r=0$, the solution is already reached and the step quotient should not be evaluated.