TITLE: Convergence of Steepest Descent: Proving Orthogonality of Exact Line Search Steps
QUESTION [3 upvotes]: For the following assume that $f(x) = 0.5x^TQx - b^Tx$, where Q is symmetric, positive definite $n$ x $n$ matrix, and $b$ belong to $R^n$. Assume that $x^*$ is the unique local minimizer of $f(x)$ and thus the gradient of $f(x^*) = Qx^*-b =0$
I want to show that if we use exact line search, then successive search "steps" $s_k, s_{k+1}$ are orthogonal; where $s_k = x_{k+1} - x_k$
What I have tried:
Solving for the gradient of $f(x_k + \alpha_kp_k) = 0$ (from minimization of $f(x_k + \alpha_kp_k)$) for $k, k+1$ and then using the solution to prove that $(x_{k+1} - x_k)^T(x_{k+2} - x_{k+1}) = 0$ but I really don't know how to prove orthogonality other than to say that two vectors' dot product is zero.
Any suggestions would be greatly appreciated! Thank you!

REPLY [5 votes]: Since $\alpha_k$ minimizes $\alpha\mapsto f(x_k + \alpha p_k)$ it follows
$$
\nabla f(x_k + \alpha_k p_k)^Tp_k=0.
$$
Now in steepest descent, the search direction is
$$
p_k := - \nabla f(x_k).
$$
Moreover, the new iterate is obtained by
$$
x_{k+1}:=x_k + \alpha_k p_k.
$$
Thus it follows
$$
(x_{k+2}-x_{k+1})^T (x_{k+1}-x_k) = \alpha_{k+1} \alpha_k p_{k+1} ^T p_k
= -\alpha_{k+1} \alpha_k \nabla f(x_{k+1})^Tp_k\\
= -\alpha_{k+1} \alpha_k \nabla f(x_k + \alpha_k p_k)^Tp_k=0.
$$