5
$\begingroup$

I am a student self-studying Optimization, and I am reading about the Conjugate Gradient Method in Numerical Optimization by Nocedal & Wright, and they present two different algorithms for it. First they present Algorithm 5.1 which is the way you might first implement the Conjugate Gradient Method based on the mathematical theory. Then, they do a few mathematical tricks to change the formula for some variables, and claim that the new Algorithm 5.2 is more efficient.

I tried comparing the algorithms, and I don't see why the second is significantly more efficient than the first. The only formulas which are different are the ones for $\alpha_k, r_{k+1},$ and $\beta_{k+1}.$

In the formula for $\alpha_k$, the only change is that we have replaced the inner product $-r_k^Tp_k$ with $r_k^T r_k$, and I don't see why this would make a difference.

In the formula for $r_{k+1}$, I guess I see one efficiency. Instead of computing the matrix product $Ax_{k+1},$ we can use $Ap_k$, a quantity which we already had to calculate in computing $\alpha_k$.

In the formula for $\beta_{k+1}$, we first replaced $r_{k+1}^TAp_k$ with $r_{k+1}^Tr_{k+1}$. Since, as discussed above, we already know the product $Ap_k$, I don't see why this is more efficient. Second, we replaced $p_k^TAp_k$ by $r_k^Tr_k$, which, for the same reason, doesn't appear to be more efficient.

There must be something I'm missing; could you please help me identify it?

Thank you!

enter image description here

enter image description here

$\endgroup$
  • $\begingroup$ In the wikipedia article en.m.wikipedia.org/wiki/Conjugate_gradient_method they talk about this $\endgroup$ – user3680510 Aug 1 at 16:15
  • $\begingroup$ It would help if you stated the problem being solved. $\endgroup$ – prubin Aug 1 at 18:01
  • 2
    $\begingroup$ The book says that Algorithm 5.2 is a 'slightly more economical form of the conjugate gradient method'. The fact that $Ax_{k+1}$ does not need to be calculated may be sufficient for that. Another efficiency could be that the value of $r_{k+1}^\top r_{k+1}$ can be reused in the next iteration as $r_k^\top r_{k}$ after $k$ is incremented by one. But I don't know if this saving is any significant in practice. $\endgroup$ – Kevin Dalmeijer Aug 2 at 13:33
  • $\begingroup$ @prubin Oh I'm sorry, the Conjugate Gradient Method is used to solve the linear system $Ax = b$ with $A$ symmetric and positive definite (or equivalently) minimizing the function $\varphi(x) = \frac 12 x^TAx - b^Tx$, again with $A$ symmetric and positive definite. $\endgroup$ – Blue Aug 2 at 15:49
  • 1
    $\begingroup$ Maybe I'm misreading something but I tried coding both versions in R and running them on a small test problem, and the first method converged much faster than the second. $\endgroup$ – prubin Aug 3 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.