Советы по программированию для реализации решателя нелинейной оптимизации (Часть II: Символьные…

Введение

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

Производные математических функций составляют неотъемлемую часть решателя оптимизации. Гессианы или якобианы цели и ограничений равенства/неравенства формируют основу для решения основной задачи нелинейной оптимизации. Как правило, методы на основе производных можно разделить на два типа: методы первого порядка и методы второго порядка. Методы первого порядка в первую очередь требуют две информации для решения основной задачи нелинейной оптимизации, которые

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

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

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

В литературе по компьютерному вычислению производных можно встретить три разных класса методов, которые я перечислил ниже.

Символическая дифференциация (SD)
Автоматическое/алгоритмическое дифференцирование (AD)
Численное дифференцирование

Последняя категория, буквально из ее определения видно, что производные аппроксимируются с помощью некоторых простых математических приемов (например, воображаемого трюка [1]) или просто математическим определением производной. Следующий пример иллюстрирует простой способ вычисления производной первого порядка одномерной функции с использованием метода Эйлера.

Класс методов численного дифференцирования обеспечивает численные приближения для производных, однако классы SD и AD вычисляют точную производную базовой функции. Если вы ищете статьи, блоги, книги, форумы и т. д., возможно, нередко вы можете быть озадачены определением и различиями между первым и вторым классами, поскольку среди многих пользователей и авторов нет единого мнения по этой теме. . Вполне возможно, что исследователь может быть обескуражен пестрыми ответами и объяснениями, приведенными для двух разных классов. Или это действительно два разных класса методов? Что ж, я постараюсь представить свою версию объяснения концепции и, надеюсь, убедить вас в своей точке зрения :).

Следуя старой поговорке, что «картинка стоит тысячи слов», в том же духе лучший способ объяснить и понять техническую концепцию — это закодировать ее и визуализировать алгоритм. Поэтому в этой статье, во-первых, я хотел бы рассказать о современной реализации модуля SD на C++ (которую я сделал через серию видеолекций), а в последующих статьях я хотел бы поговорить об AD (как в прямом, так и в обратном режиме). и, если возможно, обсудить современное состояние методов численного дифференцирования.

II. Символическая дифференциация (SD)

Определение SD в учебнике дается следующим образом: «Программа символьного дифференцирования находит производную данной формулы по заданной переменной, создавая новую формулу на выходе. Как правило, программы символьной математики манипулируют формулами для создания новых формул, а не выполняют числовые вычисления на основе формул«[2]. Я считаю, что это определение само по себе говорит само за себя, однако теперь следующий большой вопрос: «В чем разница между SD и AD?». Теперь, поскольку я планировал рассказать об AD в своем следующем блоге, однако, в интересах решения этой головоломки, позвольте мне сделать небольшое предупреждение по этой теме и демистифицировать различия между AD и SD.

Определение AD в учебнике согласно Википедии дается в виде следующего утверждения: «В математике и компьютерной алгебре автоматическое дифференцирование (AD), также называемое алгоритмическим дифференцированием, вычислительным дифференцированием, автодифференцированием или просто автодифференцированием, представляет собой набор методов вычисления производной функции, заданной компьютерной программой. AD использует тот факт, что каждая компьютерная программа, какой бы сложной она ни была, выполняет последовательность элементарных арифметических операций (сложение, вычитание, умножение, деление и т. д.) и элементарных функций (exp, log, sin, cos и т. д.). При многократном применении цепного правила к этим операциям производные произвольного порядка могут быть вычислены автоматически, с точностью до рабочей точности и с использованием не более чем на небольшой постоянный коэффициент большего количества арифметических операций, чем исходная программа» [3]. Это еще раз говорит само за себя, однако небольшое углубление в предмет может многое рассказать о различиях между AD и SD.

AD имеет два режима работы: прямой режим (также известный как режим касательной) и режим обратного хода (также известный как режим сопряженного/ко-касательного), где первый обрабатывает математическое выражение из входных данных. на выход, а последний — с выхода на вход. Принцип работы SD в основном такой же, как принцип работы прямого режима AD, однако различия лежат на уровне реализации или, если быть более точным, в базовой структуре данных, используемой для обоих методов. Согласно статье [4], автор предлагает, чтобы AD в прямом режиме обычно использовал структуру данных направленного ациклического графа (DAG), а SD использовал структуру данных дерева выражений (ET) для представления лежащего в основе математического выражения. Тем не менее, всегда можно преобразовать DAG в ET и наоборот и создать эквивалентность на операционном уровне между SD и прямым режимом AD, но это взаимозаменяемо с вычислительными накладными расходами.

Также важно учитывать контекст, в котором они применяются, то есть в среде SD, в конечном итоге действительно важна правильность вывода, однако в среде AD средства реализации также имеют значение наряду с правильностью вывода. Короче говоря, с точки зрения эксплуатации SD является небрежной реализацией [5] прямого режима AD, и это применимо и в обратном направлении. В таком случае это приводит к явлению, известному как разбухание выражения, которое замедляет вычисление производных и вычисление выражения. В качестве примера рассмотрим следующее математическое выражение

Блок-схема вычисления вышеуказанной математической функции в формах ET и DAG приведена ниже.

Из приведенной выше вычислительной схемы видно, что ET допускает повторение общего подвыражения (то есть аддитивных терминов), однако в DAG этого избегают. В случае SD при вычислении производной цепное правило повторно применяется к выражению, и может случиться так, что выражение позволит просочиться нескольким общим подвыражениям, что приведет к увеличению выражения, однако в DAG этого избегают. рамки. Часть SD, связанная с кодированием, будет рассмотрена позже в этой статье, однако беглый взгляд на абстрактное синтаксическое дерево (AST) поясняет явление увеличения выражений из-за взрывного роста декартовых классов.

а) Символьное математическое выражение Структура класса AST

класс VariableProduct‹класс VariableSin‹класс VariableSum‹класс Variable,класс Variable››,класс VariableCos‹класс VariableSum‹класс Variable,класс Variable›››

Приведенная выше структура класса является реализацией ET для математического выражения, показанного на рис. 3 (левая диаграмма).

b) Структура класса AST выражения символьной производной

класс VariableSum‹класс VariableProduct‹класс VariableProduct‹класс VariableCos‹класс VariableSum‹класс Переменная,класс VariableSum‹класс Variable,класс VariableSum‹класс Variable,класс Variable››,класс VariableCos‹класс VariableSum‹класс Variable,класс Variable›››,класс VariableProduct‹класс VariableSin‹класс VariableSum‹класс Variable,класс Variable››,класс VariableProduct‹класс VariableProduct‹double,класс VariableSin‹класс VariableSum‹класс Variable,класс VariableSin‹›,класс VariableSum‹класс Variable,класс Variable››› ›

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

Теперь давайте не будем сразу вдаваться в детали реализации, поскольку все, что я пытаюсь сказать, это то, что производное вычислительное дерево имеет несколько дубликатов общих подвыражений, и это превратилось в сложный беспорядок, но что действительно важно, так это то, что оно работает и вывод правильный!. Это типичный сценарий набухания экспрессии в случае SD.

III. Принцип работы SD

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

Целью здесь является вычисление частных производных указанной выше функции по x1 и x2. Предположим, что мы вычисляем полную производную функции f по переменной, скажем, t. Тогда по правилам исчисления (цепное правило) полная производная вычисляется как

Это также может быть представлено в следующем виде

Теперь, чтобы вычислить частные производные по x1 и x2, необходимо ввести значения членов полной производной (xd1, >xd2). Если xd1= 1 и xd2= 0, то подстановка этого значения в приведенное выше уравнение дает частную производную по x1, т. е.

Если xd1 = 0 и xd2 = 1, то подстановка этого значения в приведенное выше уравнение дает частную производную по x2, т. е.

Если вы выполняете частные производные вручную, вы получите те же результаты. В случае, если у вас есть n переменных, то n раз начальный вектор должен циклически повторяться, при этом один компонент вектора равен единице, а остальные равны нулю. Таким образом, вы получите все частные производные с n переменными. Математическое условие начального вектора с n переменными может быть представлено в следующем виде

Просто для математически склонных людей это классическая симплексная форма в целочисленных пространствах.

Концепция начального цикла может быть реализована несколькими способами, однако в этой статье я использую обход дерева предварительного порядка для сгенерированного ET для оценки и вычисления соответствующих производных.

IV. Реализация SD

Несмотря на то, что я несколько объяснил теорию SD, однако, когда дело доходит до практики, реализация имеет свои особенности. В контексте языка программирования C++ SD может быть реализован двумя разными способами: SD во время компиляции и SD во время выполнения.

Реализация SD во время компиляции на C++ использует расширенные концепции, такие как метапрограммирование шаблонов, перегрузка операторов, шаблоны проектирования, такие как CRTP для статического полиморфизма, шаблоны выражений, наследование примесей и т. д., которые помогают структурировать и обрабатывать AST во время компиляции и, следовательно, можно получить высокую производительность с небольшими вычислительными затратами или без них (например, построение V-таблиц в случае динамического полиморфизма). Однако к недостаткам относится более длительный период компиляции и, в частности, самый важный недостаток — невозможность динамически изменять выражения. Каждое выражение должно быть явно написано и оставаться статическим по своей природе, чтобы компилятор мог обработать его в самом начале этапа компиляции.

Реализация SD во время выполнения может быть запрограммирована двумя способами:

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

В этой статье, в качестве доказательства концепции (POC), я просто хотел бы поговорить о SD времени компиляции всего с 4 операциями (+, *, sin, cos) для выражения, показанного на рис. а также числовую оценку выражения (небрежная форвардная реализация AD). Итак, со всем, что было сказано и объяснено, позвольте мне сразу же перейти к кодированию простой SD времени компиляции. Я прикрепил видео (в 4 частях) ниже.

V. Выводы

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