4
$\begingroup$

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?

$\endgroup$
  • 9
    $\begingroup$ Have you looked at a textbook on optimization such as Nocedal and Wright? These explain the (N)CG method specifically for optimization, which should answer all your questions. (If not, you can make this question more specific.) TL;DR: You use $\nabla f(x^k)$ in place of $A$, and use a backtracking line search to find the smallest $\alpha_k>0$ such that $\nabla f(x^k+\alpha_k p_k)^Td^k = 0$. If the functional is not quadratic, there is no single correct choice of $\beta_k$, and there exist many variants of NCG based on this choice (Polak-Ribière, Fletcher-Reeves, Hager-Zhang,...). $\endgroup$ – Christian Clason Mar 11 '17 at 12:28
2
$\begingroup$

(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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.