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!
Best Answer
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. $$