Conjugate Gradient Descent

Constructor

ConjugateGradient(; alphaguess = LineSearches.InitialHagerZhang(),
                    linesearch = LineSearches.HagerZhang(),
                    eta = 0.4,
                    P = nothing,
                    precondprep = (P, x) -> nothing)

Description

The ConjugateGradient method implements Hager and Zhang (2006) and elements from Hager and Zhang (2013). Notice, that the default linesearch is HagerZhang from LineSearches.jl. This line search is exactly the one proposed in Hager and Zhang (2006). The constant $eta$ is used in determining the next step direction, and the default here deviates from the one used in the original paper ($0.01$). It needs to be a strictly positive number.

Example

Let's optimize the 2D Rosenbrock function. The function and gradient are given by

f(x) = (1.0 - x[1])^2 + 100.0 * (x[2] - x[1]^2)^2
function g!(storage, x)
    storage[1] = -2.0 * (1.0 - x[1]) - 400.0 * (x[2] - x[1]^2) * x[1]
    storage[2] = 200.0 * (x[2] - x[1]^2)
end

we can then try to optimize this function from x=[0.0, 0.0]

julia> optimize(f, g!, zeros(2), ConjugateGradient())
Results of Optimization Algorithm
 * Algorithm: Conjugate Gradient
 * Starting Point: [0.0,0.0]
 * Minimizer: [1.000000002262018,1.0000000045408348]
 * Minimum: 5.144946e-18
 * Iterations: 21
 * Convergence: true
   * |x - x'| ≤ 0.0e+00: false
     |x - x'| = 2.09e-10
   * |f(x) - f(x')| ≤ 0.0e+00 |f(x)|: false
     |f(x) - f(x')| = 1.55e+00 |f(x)|
   * |g(x)| ≤ 1.0e-08: true
     |g(x)| = 3.36e-09
   * stopped by an increasing objective: false
   * Reached Maximum Number of Iterations: false
 * Objective Calls: 54
 * Gradient Calls: 39

We can compare this to the default first order solver in Optim.jl

 julia> optimize(f, g!, zeros(2))

 Results of Optimization Algorithm
  * Algorithm: L-BFGS
  * Starting Point: [0.0,0.0]
  * Minimizer: [0.9999999999373614,0.999999999868622]
  * Minimum: 7.645684e-21
  * Iterations: 16
  * Convergence: true
    * |x - x'| ≤ 0.0e+00: false
      |x - x'| = 3.48e-07
    * |f(x) - f(x')| ≤ 0.0e+00 |f(x)|: false
      |f(x) - f(x')| = 9.03e+06 |f(x)|
    * |g(x)| ≤ 1.0e-08: true
      |g(x)| = 2.32e-09
    * stopped by an increasing objective: false
    * Reached Maximum Number of Iterations: false
  * Objective Calls: 53
  * Gradient Calls: 53

We see that for this objective and starting point, ConjugateGradient() requires fewer gradient evaluations to reach convergence.

References

• W. W. Hager and H. Zhang (2006) Algorithm 851: CG_DESCENT, a conjugate gradient method with guaranteed descent. ACM Transactions on Mathematical Software 32: 113-137.
• W. W. Hager and H. Zhang (2013), The Limited Memory Conjugate Gradient Method. SIAM Journal on Optimization, 23, pp. 2150-2168.