Conjugate gradient method to minimize a function

Question

I am having some serious difficulties trying to understand how to use (apply) CG to minimize a function. In all the textbooks and notes, the step size $\alpha$ is give by the following expression

$$ \alpha _k = - \frac{r_k ^T p_k}{p_k ^T A p_k}, $$

where $r$ is the residual and $p$ the search direction. The problem is that I am not trying to find the solution of a linear system, so I do not have a matrix $A$. How can I use CG to minimize a function $f(x,y)$? Can I use a fixed $\alpha$ or implement the Wolfe sufficient condition? I used a fixed step size to minimize the following function

$$ f(x,y) := -\cos(x) \cos(y) \exp(-(x-\pi)^2 - (y-\pi)^2)) $$

but CG does dot converge to one of the minimizers even if the starting point is close enough and using a step size of $1.0$. Is this possible even with CG?

Answer 1

(Disclaimer: I have taken this material from Ref.[1])

For nonlinear CG, three changes are required for the linear algorithm

1. Recursive formula for the stepsize can not be used
2. Time step size $\alpha$ computation is more complicated
3. Several different choices for $\beta$

For nonlinear CG, the residuals are set to negation of gradients of the smooth, differentiable function. i.e. $r_{i} = - f'(x_i)$. As with the linear CG, the value of $\alpha$ is computed such that it minimizes $f(x_i + \alpha_i d_i)$ by ensuring that the gradient is orthogonal to the search direction. So now we need a formula to get zeros of expression $[f'(x_i + \alpha_i d_i)]^T d_i$. Either Newton-Raphson (N-R) method (involves computation of the Hessian matrix $f''(x)$) or Secant (S) method can be used. For both methods, the function needs to be twice continuously differentiable.

A) According to N-R method,

$$\alpha = -\frac{f'^T d}{d^T f'' d}$$

B) According to Secant method,

$$ \alpha = -\sigma \frac{[f'(x)]^T d}{[f'(x+\sigma d)]^T d - [f'(x)]^T d}$$ where, $\sigma$ is an arbitrary small non-zero number. The Secant method performs exact line search without computing $f''(x)$. Both NR and S methods are terminated when $x$ is reasonably close to the exact solution. For a non quadratic function, repeated steps must be taken along the line until $f'^T$ is zero, thus one CG iteration may involve many N-R iterations.

The nonlinear CG algorithm is summarized as

1. Set $d_0 = r_0 = -f'(x_0)$
2. Find $\alpha$ as discussed earlier
3. Find $x_{i+1} = x_i + \alpha_i d_i$
4. set $r_{i+1} = -f'(x_{i+1})$
5. Find $\beta_{i+1}$ by an appropriate method (such as Fletcher-Reeves or Polak-Ribière formula)
6. then, $d_{i+1} = r_{i+1} + \beta_{i+1} d_i$

I have taken most of the material of this answer from an amazing document 'Conjugate Gradients Without Agonizing Pain' edition $1\frac{1}{4}$ [1]. Highly recommended!

Cheers!

References:

[1] Jonathan R. Shewchuk, 'An introduction to the conjugate-gradient method without the agonizing pain', pp.42-43.

Answer 2

You need to update the step size at each iteration instead of using a fixed step size. At each iteration, you need to update the search direction $p$ and residual $r$. So the step size is updated based on the new search direction and residual.

By the way, maybe we are reading different materials. Mine does not have the negative signed for the step size.