Conjugated gradient method

The conjugation gradient method [41] is a very efficient method to find a local minimum near an arbitrary initial point $\vec x_0$. It begins with the calculation of the gradient:

$$\vec h_0=\vec g_0=-\nabla f(\vec x_0).$$

We then minimize the function in its conjugate gradient direction $\vec h_{k+1}$, which is given as follows:

$$\vec g_{k+1}=-\nabla f(\vec x_{k+1})$$

and

$$\vec h_{k+1}=\vec g_{k+1}+\gamma _k \vec h_{k}$$

where $\gamma$ is updated with the Fletcher-Reeves formula, by

$$\gamma _k={ {\vec g_{k+1} \cdot \vec g_{k+1} }\over {\vec g_{k} \cdot \vec g_{k}}}$$

or with the Polak-Ribiere formula, by

$$\gamma _k={ {(\vec g_{k+1} - \vec g_{k} )\cdot \vec g_{k+1} }\over {\vec g_{k} \cdot \vec g_{k}}}$$

where $\vec x_{k+1}$ is the minimal point along the direction $\vec h_k$. A one-dimensional minimization routine (e.g. the exact line-search algorithm) can be used to find the minimum $\vec x_{k+1}$.