Быстрое автоматическое дифференцирование в задачах оптимального управления

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

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

Среди упомянутых задач обширный класс составляют оптимизационные задачи, значительную часть которых представляют задачи оптимального управления. Среди подходов к решению задач оптимального управления (см., например, работы [1]-[10]) одним из самых распространенных и плодотворных является сведение исходной задачи к задаче нелинейного программирования (см., например, работы [1], [3], [5]). Численное решение таких задач находится с помощью стандартных или адаптированных методов нелинейного программирования (методов штрафных функций, модифицированной функции Лагранжа, проекции градиента, линеаризации, внутренней точки и т. д.- см., например, [1]). Среди них градиентные методы часто оказываются наиболее эффективными. Еще более привлекательными в смысле нахождения оптимального решения являются методы, использующие вторые производные. Тут, однако, возникают серьезные трудности в случае задач большой размерности. Поэтому разработка способа вычисления производных сложной функции играет очень важную роль при создании алгоритмов численной оптимизации. При этом следует учесть, что точность и время вычисления производных существенно влияют на эффективность алгоритмов оптимизации в целом.

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

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

К числу ранних работ, касающихся техники прямого дифференцирования, относятся работы [11]-[14]. Они представляют собой первые шаги в этом направлении и получили свое продолжение в работах [15] и [16]. Среди работ, более ориентированных на практическое применение, следует упомянуть работы [17]—[19]. Наиболее полно техника прямого дифференцирования алгоритмов излагается в основополагающих публикациях [20] и [21].

Что касается обратного дифференцирования, то очень похожий подход был использован при конструировании электрических цепей (см. [22], [23]). Многие авторы независимо друг от друга использовали возможности техники обратного дифференцирования при решении широкого класса задач. Среди них особого внимания заслуживают работы [24]-[32].

Важному вопросу оценивания трудоёмкости вычисления градиента функции посвящен ряд статей (см., например, работы [10], [33]—[34]) среди которых, безусловно, следует выделить работу наших соотечественников Кима К. В., Нестерова Ю. Е., Черкасского Б. В. [33]. Авторы этой работы показали, как по заданному алгоритму вычисления функции можно построить алгоритм вычисления её градиента такой, что отношение его трудоемкости к трудоемкости исходного алгоритма не будет превышать константы, не зависящей от числа переменных.

Вопросу дальнейшего совершенствования алгоритмов вычисления производных функции, использующих технику БАД, в целях снижения их трудоемкости и размеров требуемой памяти посвящены многие работы (см., например, [35]-[43]).

В течение ряда лет прилагаются усилия по созданию пакетов компьютерных программ, вычисляющих производные сложных функций с помощью БАД-методологии (см., например, работы [44]—[52]). Цель таких пакетов состоит в том, чтобы по функции, заданной математической формулой, или по функции, значение которой вычисляется в результате выполнения компьютерной программы на языке ФОРТРАН, С++ или другом современном языке программирования, сгенерировать компьютерную программу, вычисляющую производные исходной функции. Один из таких пакетов ADOL-C (см. работу [48]) был создан в Аргонской Национальной Лаборатории (США) под руководством А. Гриванка. Там же, в Аргонской Национальной Лаборатории, был разработан широко используемый пакет ADIFOR (см. работы [49]-[50]), в создание которого большой вклад внес Бишоф. В Японии под руководством М. Ири и К. Ку-бота (см., например, работы [53]—[54]) был разработан пакет PADRE. Решение практических задач с помощью этих пакетов показало, что основным их недостатком является необходимость использования большой компьютерной памяти. Поэтому в настоящее время ведутся работы по сокращению требуемой памяти.

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

Среди работ, посвященных автоматическому дифференцированию, особое место занимает разработанная Ю. Г. Евтушенко и его сотрудниками БАД-методология, рассматривающая означенную проблему в ином ракурсе. Она берет своё начало в проводимых с 1970 года в ВЦ РАН под руководством Ю. Г. Евтушенко работах по созданию и совершенствованию методов решения задач оптимального управления, редуцированных к задачам нелинейного программирования. Формулы дифференцирования функций, возникающих в этих задачах, оказались очень близкими к формулам, используемым в работах, посвященных технике БАД.

В статьях [7]-[9] был сформулирован общий подход к вычислению градиента сложной функции, основанный на теореме о неявной функции и методе множителей Лагранжа. Его важной особенностью является то, что он позволяет с единых позиций определять градиенты не только функций, заданных в явном виде, но и функций, не имеющих явного аналитического представления. Примером могут служить функции, возникающие в результате дискретной аппроксимации задач оптимального управления процессами, описываемыми обыкновенными дифференциальными уравнениями и уравнениями с частными производными.

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

Описываемый подход обобщает технику БАД и в своих частных случаях явно заданных элементарных функций и многошаговых процессов приводит к формулам БАД. Он был успешно применен при решении ряда задач оптимального управления, например, в задаче оптимального управления решением уравнения Бюргерса [55], в задачах оптимального управления процессом плавления и кристаллизации вещества [56]-[60], при решении обратной задачи для уравнения Бюргерса и других (см., например, [61], [62]).

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

В диссертационной работе с помощью обобщенной БАД-методологии, развитой в ВЦ РАН, получены точные формулы для вычисления вторых производных сложных функций с функциональными связями. Количество сопряженных скалярных уравнений, которые необходимо решить для определения вторых производных целевой функции, есть линейная функция от размерности независимой переменной. Эти формулы были применены в конечномерной задаче оптимизации, получаемой в результате дискретной аппроксимации с привлечением метода Рунге-Кутты произвольного порядка общей задачи оптимального управления процессами, описываемыми обыкновенными дифференциальными уравнениями. Для этой конечномерной задачи оптимизации установлен вид сопряженных систем, указан путь их решения. Формулы для вычисления вторых производных целевой функции детализированы и приведены в окончательном виде, пригодном для практического использования.

В результате дискретной аппроксимации конкретной задачи оптимального управления с помощью метода Рунге-Кутты 1-го, 2-го, 3-го и 4-го порядка построены 5 расчетных конечномерных задач оптимизации (было использовано 2 варианта дискретизации с помощью метода Рунге-Кутты 2-го порядка). Расчеты этих задач были проведены методом Ньютона с применением полученных формул для вычисления вторых производных, а также градиентным методом с целью оценить эффективность предлагаемого подхода. Сравнение результатов расчетов показало, что по точности получаемого решения, по количеству итераций и даже по времени метод Ньютона оказывается предпочтительнее.

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

Были также проведены расчеты задачи оптимального управления решением уравнения Бюргерса с использованием метода сопряженных градиентов. При их проведении градиент функционала вычислялся с помощью БАД-методологии, а также с использованием следующей техники: для непрерывной прямой задачи строилась ей сопряженная непрерывная задача, определялся градиент функционала, а затем обе задачи и градиент функционала дискретизировались. Результаты расчетов показали, что в отличие от БАД-методологии применение описанной выше техники приводит к успеху только в том случае, когда дискретные аппроксимации прямой задачи, сопряженной задачи и градиента функционала являются согласованными. БАД-методология автоматически обеспечивает согласованность дискретных аппроксимаций прямой и сопряженных задач и функционала. Подробно эти вопросы обсуждаются в [55], [66].

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

Основные результаты, полученные в диссертационной работе.

1. Обобщенная БАД-методология распространена на случай вычисления вторых производных сложной функции.

2. Получены точные формулы для вычисления вторых производных сложной функции. В эти формулы входят сопряженные переменные — множители Лагранжа, которые определяются в результате решения сопряженного линейного матричного уравнения.

3. Установлено важное свойство предлагаемого подхода: после вычисления градиента функции решение сопряженного уравнения для определения множителей Лагранжа, связанных с вычислением вторых производных, не представляет трудности, т. к. основная матрица этого уравнения и основная матрица сопряженной системы, уже решенной при определении градиента функции, являются транспонированными друг другу.

4. Количество скалярных уравнений, которые необходимо решить для определения вторых производных сложной функции зависит от размерности независимой переменной линейным образом.

5. Полученные формулы для нахождения вторых производных сложной функции адаптированы к случаю многошаговых процессов.

6. Рассмотрена в общем виде задача оптимального управления процессом, описываемым обыкновенными дифференциальными уравнениями. Для конечномерной задачи оптимизации, полученной в результате дискретной аппроксимации этой задачи с помощью метода Рунге-Кутты произвольного порядка, установлен вид сопряженных уравнений и структура их основных матриц. Установлено, что сопряженные уравнения имеют простой вид и могут быть решены методом «бегущего счета». Анализ связи организации многошаговых процессов с видом сопряженных систем, структур основных матриц сопряженных систем позволяет сделать заключение о том, что использование другого метода дискретной аппроксимации не приведет к принципиальным изменениям вида сопряженных систем и способа их решения.

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

8. Формулы для вычисления матрицы вторых производных целевой функции в этой задаче приведены в окончательном виде, пригодном для практического использования.

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

10. Расчеты 5 задач, полученных в результате дискретной аппроксимации конкретной задачи оптимального управления с помощью метода Рунге-Кутты различного порядка, методом Ньютона (с применением предлагаемого алгоритма вычисления вторых производных) и градиентным методом показали, что по скорости сходимости к решению, по точности получаемого решения, по количеству итераций, приводящих к решению, и, по времени, затрачиваемому на нахождение решения, — по всем этим показателям метод Ньютона оказывается предпочтительнее градиентного метода.

11. Показано, что метод Ньютона демонстрирует преимущество по всем перечисленным выше показателям перед градиентным методом даже в том случае, когда поиск решения начинается с произвольного приближения, не являющегося хорошим для метода Ньютона.

Анализ результатов проведенных расчетов позволяет сделать вывод об эффективности предлагаемого подхода.

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

Заключение