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

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

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

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

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

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

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

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

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

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

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

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

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