Сопряженный градиентный спуск
Описание
Метод 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.