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

Что такое автоматическая дифференциация?

Автоматическая дифференциация (также известная как autodiff, AD или алгоритмическая дифференциация) - широко используемый инструмент в оптимизации. solve функция использует автоматическое дифференцирование по умолчанию в проблемной оптимизации для общих нелинейных объективных функций и ограничений; см. раздел Автоматическое дифференцирование в панели инструментов оптимизации.

Автоматическое дифференцирование - это набор методик численной оценки производных (градиентов). Метод использует символические правила дифференцирования, которые точнее конечных аппроксимаций разностей. В отличие от чисто символического подхода, автоматическое дифференцирование вычисляет выражения численно на ранних этапах вычислений, а не выполняет большие символьные вычисления. Другими словами, автоматическая дифференциация оценивает производные при определенных числовых значениях; он не создает символические выражения для производных.

Как отметили многие исследователи (например, Байдин, Перлмуттер, Радул и Сискинд [1]), для скалярной функции многих переменных обратный режим вычисляет градиент более эффективно, чем прямой режим. Поскольку целевая функция является скалярной, solve автоматическое дифференцирование использует обратный режим для скалярной оптимизации. Однако для векторных функций, таких как нелинейные наименьшие квадраты и решение уравнений, solve использует прямой режим для некоторых вычислений. См. раздел Автоматическое дифференцирование в панели инструментов оптимизации.

Форвардный режим

Рассмотрим проблему оценки этой функции и её градиента:

Автоматическая дифференциация работает в определенных точках. В этом случае возьмем x1 = 2, x2 = 1/2.

Следующий вычислительный граф кодирует вычисление функции f (x).

Чтобы вычислить градиент f (x) с помощью прямого режима, вычислите тот же график в том же направлении, но измените вычисление на основе элементарных правил дифференциации. Для дальнейшего упрощения вычисления необходимо заполнить значение производной каждого подэкспрессии. Чтобы вычислить весь градиент, нужно пройти график дважды, один раз для частной производной относительно каждой независимой переменной. Каждое вложенное выражение в правиле цепочки имеет числовое значение, поэтому всё выражение имеет тот же тип графа вычисления, что и сама функция.

Вычисление представляет собой повторное применение правила цепочки. В этом примере производная f относительно x1 расширяется до этого выражения:

Пусть $${\stackrel{}{}}_{\mathrm{u\dot{}i}}$$ представляет производную выражения _ui относительно x1. Используя вычисленные значения _ui из вычисления функции, вычисляется частная производная f относительно x1, как показано на следующем рисунке. Обратите внимание, что все значения $${\stackrel{}{}}_{\mathrm{u\dot{}i}}$$ становятся доступными при прохождении графика сверху вниз.

Чтобы вычислить частную производную относительно x2, нужно пройти аналогичный вычислительный график. Поэтому при вычислении градиента функции число проходов по графам совпадает с числом переменных. Этот процесс может быть медленным для многих приложений, когда целевая функция или нелинейные ограничения зависят от многих переменных.

Обратный режим

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

Теория, лежащая в основе обратного режима, также основана на цепном правиле вместе со связанными смежными переменными, обозначаемыми overbar. Смежная переменная для _ui

В терминах вычислительного графа каждая исходящая стрелка из переменной вносит вклад в соответствующую смежную переменную по её члену в правиле цепочки. Например, переменная u-1 имеет исходящие стрелки для двух переменных, u1 и u6. Граф имеет связанное уравнение

В этом вычислении, напоминая, что $${}_{\mathrm{u1}}{=}_{\mathrm{u}}^{\mathrm{}}$$− 12 и u6 = _u5u-1, вы получаете

Во время прямого прохождения графика программное обеспечение вычисляет промежуточные переменные _ui. Во время обратного обхода, начиная с начального значения $${\stackrel{}{}}_{\mathrm{}}\frac{}{}\mathrm{u¯6=\partial f\partial f=1}$$, вычисление обратного режима получает смежные значения для всех переменных. Следовательно, обратный режим вычисляет градиент только за одно вычисление, экономя много времени по сравнению с прямым режимом.

На следующем рисунке показано вычисление градиента в обратном режиме для функции

Опять же, вычисление занимает x1 = 2, x2 = 1/2. Вычисление обратного режима основано на значениях _ui, которые получаются во время вычисления функции на исходном вычислительном графике. В правой части рисунка вычисленные значения смежных переменных появляются рядом с именами смежных переменных, используя формулы из левой части рисунка.

Конечные значения градиента отображаются как $${\stackrel{}{}}_{\mathrm{}}\frac{}{{}_{\mathrm{}}}\frac{}{{}_{\mathrm{u¯0=\partial f\partial u0=\partial f\partial x2}}}$$ и $${\stackrel{}{}}_{\mathrm{}}\frac{}{{}_{\mathrm{}}}\frac{}{{}_{\mathrm{u¯-1=\partial f\partial u-1=\partial f\partial x1}}}$$.

Для получения более подробной информации см. Baydin, Pearlmutter, Radul и Siskind [1] или статью Википедии об автоматической дифференциации [2].

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

Автоматическое дифференцирование (AD) применяется к solve и prob2struct функционирует при следующих условиях:

Когда эти условия не выполняются, solve оценивает градиенты по конечным разностям, и prob2struct не создает градиенты в созданных файлах функций.

Решатели по умолчанию выбирают следующий тип AD:

options = optimoptions('fmincon','SpecifyObjectiveGradient',true,...
    'SpecifyConstraintGradient',true);
problem.options = options;

В настоящее время AD работает только для первых производных; он не относится ко вторым или более высоким производным. Так, например, если вы хотите использовать аналитический гессен для ускорения оптимизации, вы не можете использовать solve непосредственно и должен использовать подход, описанный в разделе Дериваты поставки в потоке операций на основе проблем.