Сопряженный градиентный спуск

Конструктор

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

Описание

Метод ConjugateGradient реализует элементы, описанные в работах Хагера (Hager) и Жанга (Zhang) 2006 и 2013 гг. Обратите внимание, что linesearch по умолчанию — это HagerZhang из LineSearches.jl. Этот линейный поиск в точности соответствует тому, который был предложен в работе Хагера и Жанга (2006). Константа используется при определении направления следующего шага, и значение по умолчанию здесь отличается от того, которое применяется в оригинальной статье ( ). Оно должно быть строго положительным числом.

Пример

Оптимизируем двумерную функцию Розенброка. Функция и градиент заданы следующим образом

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

мы можем попытаться оптимизировать эту функцию из 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

Мы можем сравнить это с решателем первого порядка по умолчанию в 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

Мы видим, что для этой цели и начальной точки ConjugateGradient() требуется меньше вычислений градиента для достижения сходимости.

Справочные материалы

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.