Документация Engee

Линейный поиск

Описание

Функциональность линейного поиска была перенесена в LineSearches.jl.

Линейный поиск используется для определения длины шага в направлении, вычисляемом алгоритмом оптимизации.

Линейный поиск используется в следующих алгоритмах Optim:

  • Ускоренный градиентный спуск

  • (L-)BFGS

  • Сопряженные градиенты

  • Градиентный спуск

  • Градиентный спуск с моментом

  • Алгоритм Ньютона

По умолчанию Optim вызывает алгоритм линейного поиска HagerZhang(), предоставляемый LineSearches. С помощью именованного аргумента linesearch заданному алгоритму можно присваивать различные алгоритмы линейного поиска.

LineSearches также позволяет принимать решение о способе выбора начальной длины шага для алгоритма линейного поиска. Это значение задается именованным аргументом alphaguess для алгоритма Optim. Процедура по умолчанию может отличаться.

Пример

В этом примере сравниваются два различных алгоритма линейного поиска в задаче Розенброка.

Сначала выполним Newton с алгоритмом линейного поиска по умолчанию:

using Optim, LineSearches
prob = Optim.UnconstrainedProblems.examples["Rosenbrock"]

algo_hz = Newton(;alphaguess = LineSearches.InitialStatic(), linesearch = LineSearches.HagerZhang())
res_hz = Optim.optimize(prob.f, prob.g!, prob.h!, prob.initial_x, method=algo_hz)

Получим следующий результат:

 * Algorithm: Newton's Method
 * Starting Point: [0.0,0.0]
 * Minimizer: [0.9999999999999994,0.9999999999999989]
 * Minimum: 3.081488e-31
 * Iterations: 14
 * Convergence: true
   * |x - x'| ≤ 0.0e+00: false
     |x - x'| = 3.06e-09
   * |f(x) - f(x')| ≤ 0.0e+00 |f(x)|: false
     |f(x) - f(x')| = 2.94e+13 |f(x)|
   * |g(x)| ≤ 1.0e-08: true
     |g(x)| = 1.11e-15
   * stopped by an increasing objective: false
   * Reached Maximum Number of Iterations: false
 * Objective Calls: 44
 * Gradient Calls: 44
 * Hessian Calls: 14

Теперь можно попробовать Newton с линейным поиском Мора-Туенте:

algo_mt = Newton(;alphaguess = LineSearches.InitialStatic(), linesearch = LineSearches.MoreThuente())
res_mt = Optim.optimize(prob.f, prob.g!, prob.h!, prob.initial_x, method=algo_mt)

Получим следующий результат с сокращенным количеством вызовов функций и градиентов:

Results of Optimization Algorithm
 * Algorithm: Newton's Method
 * Starting Point: [0.0,0.0]
 * Minimizer: [0.9999999999999992,0.999999999999998]
 * Minimum: 2.032549e-29
 * Iterations: 14
 * Convergence: true
   * |x - x'| ≤ 0.0e+00: false
     |x - x'| = 3.67e-08
   * |f(x) - f(x')| ≤ 0.0e00 |f(x)|: false
     |f(x) - f(x')| = 1.66e+13 |f(x)|
   * |g(x)| ≤ 1.0e-08: true
     |g(x)| = 1.76e-13
   * stopped by an increasing objective: false
   * Reached Maximum Number of Iterations: false
 * Objective Calls: 17
 * Gradient Calls: 17
 * Hessian Calls: 14

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