Методы ускорения: N-GMRES и O-ACCEL
Конструкторы
NGMRES(;
alphaguess = LineSearches.InitialStatic(),
linesearch = LineSearches.HagerZhang(),
manifold = Flat(),
wmax::Int = 10,
ϵ0 = 1e-12,
nlprecon = GradientDescent(
alphaguess = LineSearches.InitialStatic(alpha=1e-4,scaled=true),
linesearch = LineSearches.Static(),
manifold = manifold),
nlpreconopts = Options(iterations = 1, allow_f_increases = true),
)OACCEL(;manifold::Manifold = Flat(),
alphaguess = LineSearches.InitialStatic(),
linesearch = LineSearches.HagerZhang(),
nlprecon = GradientDescent(
alphaguess = LineSearches.InitialStatic(alpha=1e-4,scaled=true),
linesearch = LineSearches.Static(),
manifold = manifold),
nlpreconopts = Options(iterations = 1, allow_f_increases = true),
ϵ0 = 1e-12,
wmax::Int = 10)Описание
Эти алгоритмы берут шаг, заданный нелинейным предусловливателем nlprecon, и предлагают ускоренный шаг в подпространстве, охватываемом предыдущими итерациями wmax.
-
Ускорение N-GMRES основано на минимизации аппроксимации к норме градиента.
-
Ускорение O-ACCEL основано на минимизации аппроксимации к цели.
N-GMRES был первоначально разработан для решения нелинейных систем [1] и сводится к GMRES для линейных задач. Применение алгоритма для оптимизации рассматривается, к примеру, в документе [2]. Описание O-ACCEL и его связи с N-GMRES можно найти в документе [3].
Для решения задачи мы рекомендуем сначала попробовать LBFGS и лишь затем N-GMRES или O-ACCEL. Все три алгоритма имеют схожие вычислительные затраты и требования к памяти, однако для многих задач L-BFGS является более эффективным.
Пример
В этом примере показано, как ускорить GradientDescent в расширенной задаче Розенброка. Сначала попытаемся выполнить оптимизацию с помощью GradientDescent.
using Optim, OptimTestProblems
UP = UnconstrainedProblems
prob = UP.examples["Extended Rosenbrock"]
optimize(UP.objective(prob), UP.gradient(prob), prob.initial_x, GradientDescent())Алгоритм не сходится за 1000 итераций.
Results of Optimization Algorithm
* Algorithm: Gradient Descent
* Starting Point: [-1.2,1.0, ...]
* Minimizer: [0.8923389282461412,0.7961268644300445, ...]
* Minimum: 2.898230e-01
* Iterations: 1000
* Convergence: false
* |x - x'| ≤ 0.0e+00: false
|x - x'| = 4.02e-04
* |f(x) - f(x')| ≤ 0.0e+00 |f(x)|: false
|f(x) - f(x')| = 2.38e-03 |f(x)|
* |g(x)| ≤ 1.0e-08: false
|g(x)| = 8.23e-02
* Stopped by an increasing objective: false
* Reached Maximum Number of Iterations: true
* Objective Calls: 2525
* Gradient Calls: 2525
Теперь мы используем OACCEL для ускорения GradientDescent.
# Нелинейный предобусловливатель по умолчанию для `OACCEL`
nlprecon = GradientDescent(alphaguess=LineSearches.InitialStatic(alpha=1e-4,scaled=true),
linesearch=LineSearches.Static())
# Размер подпространства, в котором ускоряется OACCEL, по умолчанию равен `wmax = 10`
oacc10 = OACCEL(nlprecon=nlprecon, wmax=10)
optimize(UP.objective(prob), UP.gradient(prob), prob.initial_x, oacc10)Он значительно улучшает работу алгоритма GradientDescent, так как тот сходится за 87 итераций.
Results of Optimization Algorithm
* Algorithm: O-ACCEL preconditioned with Gradient Descent
* Starting Point: [-1.2,1.0, ...]
* Minimizer: [1.0000000011361219,1.0000000022828495, ...]
* Minimum: 3.255053e-17
* Iterations: 87
* Convergence: true
* |x - x'| ≤ 0.0e+00: false
|x - x'| = 6.51e-08
* |f(x) - f(x')| ≤ 0.0e+00 |f(x)|: false
|f(x) - f(x')| = 7.56e+02 |f(x)|
* |g(x)| ≤ 1.0e-08: true
|g(x)| = 1.06e-09
* Stopped by an increasing objective: false
* Reached Maximum Number of Iterations: false
* Objective Calls: 285
* Gradient Calls: 285
Мы можем еще больше улучшить ускорение, изменив размер подпространства ускорения wmax.
oacc5 = OACCEL(nlprecon=nlprecon, wmax=5)
optimize(UP.objective(prob), UP.gradient(prob), prob.initial_x, oacc5)Теперь алгоритм O-ACCEL ускорил GradientDescent для схождения за 50 итераций.
Results of Optimization Algorithm
* Algorithm: O-ACCEL preconditioned with Gradient Descent
* Starting Point: [-1.2,1.0, ...]
* Minimizer: [0.9999999999392858,0.9999999998784691, ...]
* Minimum: 9.218164e-20
* Iterations: 50
* Convergence: true
* |x - x'| ≤ 0.0e+00: false
|x - x'| = 2.76e-07
* |f(x) - f(x')| ≤ 0.0e+00 |f(x)|: false
|f(x) - f(x')| = 5.18e+06 |f(x)|
* |g(x)| ≤ 1.0e-08: true
|g(x)| = 4.02e-11
* Stopped by an increasing objective: false
* Reached Maximum Number of Iterations: false
* Objective Calls: 181
* Gradient Calls: 181
В качестве последнего сравнения можно проделать то же самое с N-GMRES.
ngmres5 = NGMRES(nlprecon=nlprecon, wmax=5)
optimize(UP.objective(prob), UP.gradient(prob), prob.initial_x, ngmres5)И снова, работа алгоритма GradientDescent значительно улучшается, и он сходится за 63 итерации.
Results of Optimization Algorithm
* Algorithm: Nonlinear GMRES preconditioned with Gradient Descent
* Starting Point: [-1.2,1.0, ...]
* Minimizer: [0.9999999998534468,0.9999999997063993, ...]
* Minimum: 5.375569e-19
* Iterations: 63
* Convergence: true
* |x - x'| ≤ 0.0e+00: false
|x - x'| = 9.94e-09
* |f(x) - f(x')| ≤ 0.0e+00 |f(x)|: false
|f(x) - f(x')| = 1.29e+03 |f(x)|
* |g(x)| ≤ 1.0e-08: true
|g(x)| = 4.94e-11
* Stopped by an increasing objective: false
* Reached Maximum Number of Iterations: false
* Objective Calls: 222
* Gradient Calls: 222