I am studying optimization methods and I was able to understand and derive the search direction

$$ p_k = r_{k-1} + \beta p_{k-1} $$

for Conjugate Gradient Method, with

$$ \beta = -\frac{p_{k-1}^TAr_{k-1}}{p_{k-1}^TAp_{k-1}}. $$

In this expression $p_k$ is the search direction and $r_k$ the residual. Nevertheless, in a paper [1] I found the following expression ($d$ is the direction, $g$ is the gradient and $y_{k-1} = (g_k-g_{k-1}))$:

$$ d_1 = -Hg_1,\\ d_k = -Hg_k + \frac{y_{k-1}^THg_k}{y_{k-1}^Td_{k-1}}d_{k-1} .$$

I am not able to understand if this is the same as $p_k$. In the paper the author writes that the basic CG is with $H$ being the identity matrix.

Is $\frac{y_{k-1}^THg_k}{y_{k-1}^Td_{k-1}} = \beta$?

[1] A Relationship between the BFGS and Conjugate Gradient Algorithms and Its Implications for New Algorithms, L. Nazareth.

  • 2
    $\begingroup$ They are only equivalent if you include the BFGS $H$ update, and only if you perform an exact line search along each search direction. I can assure you the fact that BFGS becomes equivalent to CG is not at all obvious, nor is it supposed to be. $\endgroup$ – Richard Zhang Apr 8 '17 at 15:24
  • $\begingroup$ @RichardZhang Thanks a lot. But I was concerned with CG alone: in all the textbooks the expression for the search direction is the one I wrote first. But in the paper they write it in a, apparently, different way that I cannot relate to the first one. $\endgroup$ – wrong_path Apr 8 '17 at 15:27
  • 1
    $\begingroup$ @sensitive_scientist Be aware that in CG for optimization (as opposed to CG for linear systems -- the former is often referred to as NCG (N for "nonlinear") to avoid confusion), there is no longer a single correct choice of $\beta$, and there is a wide variety of variants of algorithms based on this choice. You can find a (far from exhaustive and up-to-date) list here: people.cs.vt.edu/~asandu/Public/Qual2011/Optim/… $\endgroup$ – Christian Clason Apr 9 '17 at 17:59

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.