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

Градиенты и гессианы

Чтобы использовать методы первого и второго порядка, необходимо предоставить градиенты и гессианы либо на месте, либо не на месте. Существует три основных способа задания производных: аналитический, конечно-разностный и автоматическое дифференцирование.

Аналитический способ

Обеспечивает самое быстрое время выполнения, но требует от пользователя выполнения часто утомительной задачи вычисления производных вручную. Градиент сложных целевых функций (например, связанных с решением алгебраических уравнений, дифференциальных уравнений, разложениями по собственным значениям и т. д.) может быть вычислен с помощью метода сопряженности (см., например, эти конспекты лекций). В частности, при условии бесконечной памяти градиент функции всегда можно вычислить за время, сравнимое с одним вычислением , независимо от размера .

Чтобы использовать аналитические производные, просто передайте функции g! и h! в optimize.

Конечные разности

Здесь используется функциональность из DiffEqDiffTools.jl для вычисления градиентов и гессианов с помощью центральных конечных разностей: . При этом для целевой функции требуется вычислений функции . Поэтому эффективность выше в малых измерениях, но замедляется при высоких значениях . Этот способ также неточен: выбирается равным , где  — машинный эпсилон (около для Float64), чтобы сбалансировать погрешности усечения и округления, что приводит к ошибке (около для Float64) при вычислении производной.

Конечные разности включены по умолчанию, если в вызове optimize не указаны градиенты и гессианы.

Автоматическое дифференцирование

Методы автоматического дифференцирования представляют собой нечто среднее между конечными разностями и аналитическими вычислениями. Их точность практически аналогична машинной, и они не требуют вмешательства пользователя. Они представлены в двух основных вариантах: прямой и обратный режимы. Автоматическое дифференцирование в прямом режиме относительно просто реализуется путем распространения чувствительности входных переменных и часто выполняется быстрее, чем конечные разности. Недостатком является то, что целевая функция должна быть написана только с использованием кода Julia. Автоматическому дифференцированию в прямом режиме все еще требуется время выполнения, сравнимое с вычислениями , и поэтому оно, как и конечные разности, является дорогостоящим в больших размерностях.

Автоматическое дифференцирование в обратном режиме можно рассматривать как автоматическую реализацию метода сопряженности, упомянутого выше. Для него требуется время выполнения, сравнимое только с одним вычислением . Однако оно значительно сложнее в реализации, поскольку необходимо записать выполнение программы, чтобы затем запустить ее в обратном направлении, и связано с большими расходами.

Автоматическое дифференцирование в прямом режиме поддерживается с помощью пакета ForwardDiff.jl и указания ключевого слова autodiff=:forward со значением optimize. Автоматическое дифференцирование в обратном режиме пока не поддерживается явным образом (хотя его можно использовать, написав собственную функцию g!). В Julia существует множество реализаций, например ReverseDiff.jl.

Пример

Еще раз возьмем пример Розенброка.

function f(x)
    return (1.0 - x[1])^2 + 100.0 * (x[2] - x[1]^2)^2
end

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

function h!(H, x)
    H[1, 1] = 2.0 - 400.0 * x[2] + 1200.0 * x[1]^2
    H[1, 2] = -400.0 * x[1]
    H[2, 1] = -400.0 * x[1]
    H[2, 2] = 200.0
end

initial_x = zeros(2)

Посмотрим, смогут ли BFGS и метод Ньютона решить эту задачу с помощью предоставленных функций.

julia> Optim.minimizer(optimize(f, g!, h!, initial_x, BFGS()))
2-element Array{Float64,1}:
 1.0
 1.0

julia> Optim.minimizer(optimize(f, g!, h!, initial_x, Newton()))

2-element Array{Float64,1}:
 1.0
 1.0

Да, все работает. Теперь используем конечные разности для BFGS.

julia> Optim.minimizer(optimize(f, initial_x, BFGS()))
2-element Array{Float64,1}:
 1.0
 1.0

Выглядит по-прежнему хорошо. Возвращаясь к автоматическому дифференцированию, попробуем оба решателя, используя этот метод. Мы включаем прямой режим автоматического дифференцирования с помощью ключевого слова autodiff = :forward.

julia> Optim.minimizer(optimize(f, initial_x, BFGS(); autodiff = :forward))
2-element Array{Float64,1}:
 1.0
 1.0

julia> Optim.minimizer(optimize(f, initial_x, Newton(); autodiff = :forward))
2-element Array{Float64,1}:
 1.0
 1.0

Действительно, минимизатор был найден без указания градиентов или гессианов.