Быстрое автоматическое дифференцирование в задачах оптимального управления тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

г

У

Засухина Елена Семеновна

ООЗОБЗ151

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

Специальность 01.01.09 - Дискретная математика и математическая кибернетика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва- 2007

003053151

Работа выполнена в Вычислительном центре им. A.A. Дородницына Российской академии наук

Научный руководитель: доктор физико-математических наук

Зубов Владимир Иванович

Официальные доктор физико-математических наук, профессор оппоненты: Лотов Александр Владимирович

кандидат физико-математических наук, доцент Бирюков Александр Гаврилович

Ведущая организация: Институт системного анализа РАН

Защита состоится « Л 2007 г. в je часов на

заседании диссертационного совета Д 002.017.02 Вычислительного центра им. A.A. Дородницына Российской академии наук по адресу: 119991, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Вычислительного центра им. A.A. Дородницына Российской академии наук.

Автореферат разослан «_ // _» gQM2007 г.

Ученый секретарь диссертационного совета

доктор физико-математических наук " В.В. Рязанов

Общая характеристика работы

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

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

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

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

Научная новизна работы состоит в следующем.

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

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

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

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

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

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

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

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

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

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

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

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

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

На защиту выносятся следующие положения:

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

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

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

Апробация работы. Основные положения и результаты работы были доложены и обсуждены на следующих научных конференциях: Всероссийская конференция "Обратные и некорректно поставленные задачи", (Москва, МГУ, 1998 г.); 3-я Международная конференция по быстрому автоматическому дифференцированию (Third International Conference on Automatic Differentiation: "From Simulation to Optimization", 2000, Maison du Seminaire, Nice, Prance ) (Франция, 2000г.); а также на научных семинарах отдела прикладных проблем оптимизации ВЦ РАН (Москва, 2001-2006); на научных семинарах отдела механики сплошных сред ВЦ РАН (Москва, 2006); на научном семинаре кафедры математических основ управления МФТИ (г. Долгопрудный, 2006).

Объём и структура. Диссертация состоит из введения, трех глав, заключения, списка используемых источников и приложения, состоящего из рисунков и таблиц. Полный объём работы, включая 17 таблиц, 64 рисунка и список литературы, насчитывающий 67 наименований, составляет 120 страниц.

Краткое содержание работы.

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

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

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

Математическая постановка задачи.

Пусть Ш : Яп х Яг -> Я1, Ф : Яп х Яг -> Яп дважды непрерывно дифференцируемые отображения. Рассмотрим систему из п уравнений связи Ф(х,и) = 0П, где х € Яп и и 6 Яг. Пусть матрица и) неособенная всюду в интересующей нас области. Тогда по теореме о неявной функции существует дважды непрерывно дифференцируемая функция х = х(и), такал что Ф(х(и),и) = 0п.

Задача состоит в нахождении вторых производных функции П(и) = ]У{х(и),и).

Чтобы определить с помощью обобщенной БАД-методологии градиент функции П(и), вводится функция Лагранжа Ь(х,и,р) = \¥(х, и) + ртФ(х, и), где р - множитель Лагранжа, р 6 Яп. Продифференцировав Ь(х,и,р) по р и по х и приравняв нулю полученные производные, получим исходную систему уравнений связи и сопряженную систему уравнений

Ьх(х,и,р) = \¥х(х,и) + Ф х(х,и)р = 0П.

Выражение Ьи{х(и),и,р(и)), где функции х(и) и р{и) удовлетворяют исходной и сопряженным системам уравнений, определяет градиент функции О, (и)

п

= wu + ^ф;t■p^ t=l

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

форме:

Фмт(х,г») + Фхт(д:>и) • Л = 0ПГ,

где Л есть п х г-матрица, элементами которой являются новые (по сравнению с множителем Лагранжа р) сопряженные переменные, а формула для вычисления вторых производных функции 0,(и) выглядит следующим образом:

й2Щи)/йи2 = \¥хтиА + (И^А)7" + УГити + Лт^Т1Л +

+ Х>* • (Кг и + Кг Л + (Фг*тил)т + лтф* т,л), 1=1

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

Количество скалярных уравнений, которые необходимо решить для определения вторых производных функции П(и), равно пг, что в (г+1)/2 меньше количества уравнений, которые необходимо решить при определении вторых производных путем дифференцирования уравнений связи.

При рассмотрении многошаговых процессов все переменные х и и расщепляются на N переменных более низкой размерности.

Уравнения, описывающие процесс, расщепляются на N соотношений вида

a;t = F(г,Xl,[/í), 1<г<ЛГ,

где Хг, \]{ - заданные подмножества множеств {х\,... и

{и\,...,и^} соответственно.

Во всех рассматриваемых матрицах множества строк и столбцов разделяются на N равных частей (возникают блок-строки и блок-столбцы), эти матрицы рассматриваются как матрицы блочных элементов. Вводится матрица В, разность между которой и

основной матрицей сопряженной системы относительно множителя Лагранжа р составляет единичную матрицу. Вводится также матрица С, С = Ф„. Сопряженное матричное уравнение для определения матрицы Л с введением матриц В и С представляется в виде:

Ст + Вт • Л = 0ПГ.

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

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

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

йх/<И = f(t,x,u,t), Тг<£<Т2, аг(Тьх0) = х0,

где /(£, х, и, £) - дважды непрерывно дифференцируемая функция, х е К* - вектор состояний, управление и есть произвольная кусочно непрерывная функция переменной Ь со значениями в 1/, и - компакт в пространстве Дт, £ - управляющий параметр, £ € V С Д9, V—компактное множество. Величины 7\, Т2,х\ могут быть как фиксированными, так и свободными. Если они не фиксированы, то должны определяться из решения задачи оптимизации, и в этом случае их следует включить в вектор

Задача состоит в нахождении управляющей функции и(Ь), и(£) 6 и, Т\ < £ < Т2, и управляющего вектора £ £ V, которые минимизируют целевую функцию \¥(х(Т2,хо),£). Здесь х(Ь,хо) обозначает решение системы уравнений, описывающей управляемый процесс, при заданных и удовлетворяющее начальному условию

х(Т\, Хо) = Хо.

Рассматриваются конечномерные задачи оптимизации, получаемые в результате дискретной аппроксимации этой задачи с по-

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

Структура этих матриц в случае дискретизации методом Рунге-Кутты 4-го порядка имеет следующий вид (здесь и далее ненулевые блочные элементы отмечены черными кружочками):

В =

\ • • • •

\ • •

\ • •

\ •

\ • • • •

\ • •

\ • •

\ •

\ • • • •

\ • •

N • •

\ •

\

С =

Рис. 1.

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

В матрица С в каждой блок-строке, за исключением последней (она соответствует управляющему параметру £ и, вообще говоря, имеет отличную от остальных строк толщину) и предпоследней, содержится М ненулевых блочных элементов, расположен-

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

Анализ структур матриц В к С приводит к выводу о том, что решение сопряженного уравнения матрица А имеет такой вид ( дискретизация методом Рунге-Кутты 4-го порядка):

Л =

Рис. 2.

Высота ступенек в матрице Л составляет М блочных элементов (М - порядок аппроксимации исходной задачи методом Рунге-Кутты), ширина - один блочный элемент. Из структуры матрицы Л следует вывод о том, что количество уравнений, которое необходимо решить для нахождения вторых производных функции равно (1 — в/гг)(1 + 9/г)пг/2, что с увеличением N стремится к пг/2.

Для всех указанных конечномерных задач устанавливается структура всех слагаемых-матриц в формуле для вычисления матрицы вторых производных целевой функции. Из всех слагаемых в этой формуле выделяется множество пар, составленных из 1-го и 2-го слагаемых, а также из 2-го и 3-го слагаемых, стоящих за знаком суммы. Матрицы, составляющие каждую такую пару, являются транспонированными друг другу. Так как матрица вторых производных симметричная, то для ее определения достаточно найти ее нижний треугольник. Ввиду особой структуры матриц

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

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

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

Функция у(х,£) определялась из решения прямой задачи при выбранном управлении. Это управление представляло на левом конце отрезка линейную функцию времени, изменяющуюся от 1 до 0, а на правом конце - линейную функцию времени, изменяющуюся от —1 до 0. Задача определения оптимального управления решалась с использованием градиентов, вычисленных с помощью обобщенной БАД-методологии. В качестве начального управления, с которого начинается процесс оптимизации функционала, выбиралось Фгшь полученное из выбранных граничных условий путем наложения на них гауссовского белого шума (со средне-квадратическим отклонением 0.3). На рис. 3 представлены начальное управление Ф^г (пунктирная линия) и оптимальное управление Фор«- Найденное оптимальное управление Фор{ отличается от истинного значения не более, чем на Ю-9.

Подход, при котором для непрерывной прямой задачи строит-

ся ей сопряженная, определяется градиент функционала, а затем обе задачи и градиент функционала аппроксимируются, приводит к успеху только в том случае, когда дискретные аппроксимации прямой задачи, сопряженной задачи и градиента функционала являются согласованными. На рис. 4 представлены результаты расчетов, когда при использовании этого подхода эти аппроксимации были не согласованы. Наибольшее отличие оптимального управления от истинного (порядка 22%) наблюдается в окрестности начального момента времени t = 0.

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

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

Расчеты показали, что значение {thess/tf)/r незначительно изменяется в зависимости от г, но существенно зависит от конкретной задачи. Так, для задачи 3 это соотношение в среднем равно 0.3, для задачи 2 - 0.78, а для задачи 1 - 1.88. Полученные в ходе расчетов зависимости (theSs/tf)/r от г демонстрируются на рис. 5. Таким образом, полученные результаты позволяют сделать заключение о том, что время, затрачиваемое на вычисление вто-

Рис. 3.

Размерность управления г

Рис. 5. 12

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

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

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

Чтобы оценить влияние количества точек, определяющих интерполирующий сплайн, было проведено 4 варианта расчетов, когда интерполяция выполнялась по 5, 10, 20 и 40 точкам.

С целью нахождения хорошего начального приближения было проведено предварительное исследование: поиск решения с начальным приближением и(£) = 0 (которое хорошим начальным приближением не является, так как поиск решения методом Ньютона с этим начальным приближением, приводил к расхождению итерационного процесса) проводился модифицированным мето-

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

На начальных итерациях значения а были очень далеки от единицы (Ю-2 Ч- Ю-1), затем с увеличением номера итерации все чаще появлялись а, близкие к единице. Момент, когда, начиная с некоторой итерации, а принимало значение единица и оставалось таковым вплоть до получения решения с точностью Ю-5 -г- Ю-7, принимался за момент переключения оптимизационного процесса на стандартный метод Ньютона, а управление, полученное на предшествующей итерации, - за хорошее начальное приближение.

Приближение, полученное после проведения 7 итераций, выполненных модифицированным методом Ньютоном в задаче Р-К 4 с начальным приближением и{€) = 0, оказалось хорошим для всех расчетных задач, кроме ДЭ. При этом одномерная оптимизация производилась с использованием сплайнов, построенных по 40 точкам.

В задаче ДЭ, использовалось свое хорошее начальное приближение, полученное после 8 итераций, выполненных модифицированным методом Ньютоном при решении этой же задачи с начальным приближением и(Ь) = 0 и с применением сплайнов, построенных по 40 точкам.

Изучался вопрос: не окажется ли градиентный метод более эффективен, чем модифицированный метод Ньютона, при нахождении хорошего начального приближения? С этой целью для каждой схемы дискретизации с помощью градиентного метода производилось то же количество итераций, которое потребовались модифицированному методу Ньютона для нахождения хорошего начального приближения. Полученное управление %,-(£), условно называемое "градиентным"начальным приближением, принималось в качестве начального приближения при решении задачи оптимизации методом Ньютона. Анализ расчетов показал, что градиентное начальное приближение не позволяет "включить"стандартный метод Ньютона на начальных итерациях.

Как показали расчеты задач ДЭ, ДР-К 2.1, ДР-К 2.2, ДР-К 3 и

ДР-К 4, с увеличением точности аппроксимации исходной задачи время, затрачиваемое на получение решения, увеличивается. При этом количество итераций, приводящих к решению с заданной точностью, изменяется незначительно. Сравнение оптимальных значений функционала, полученных для различных аппроксимаций, позволяет сделать вывод о том, что дискретизация по схеме Эйлера недостаточно точно аппроксимирует исходную задачу.

Метод Ньютона оказался гораздо эффективнее градиентного метода в смысле получения решения с высокой точностью: в то время как метод Ньютона приводит к решению с точностью 10~12 (при всех схемах дискретной аппроксимации), для градиентного метода точность Ю-7 в получении решения (при всех схемах дискретной аппроксимации) оказывается недостижимой. Точность определяется С-нормой градиента целевой функции.

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

• по количеству итераций, приводящих к решению;

• по времени, затрачиваемому на нахождение решения;

• и, наконец, по скорости сходимости итерационного процесса к решению, -

по всем этим показателям метод Ньютона обладает бесспорным преимуществом перед градиентным методом.

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

Таблица 1: Отношение ¿сЛдг-(хорошее начальное приближение)

Количество точек 5 10 20 40

Э Ю-3 8.8 8.4 18.1 37.4

Ю-5 18.0 16.2 33.8 66.1

Р-К 2.1 Ю-3 14.1 3.1 21.5 49.1

Ю-5 22.8 4.7 37.5 80.8

Р-К 2.2 Ю-3 16.0 3.1 25.1 58.4

10~5 27.2 5.0 44.5 95.7

Р-К 3 Ю-3 17.9 3.6 27.8 63.2

10~5 29.5 5.8 47.7 102.5

Р-К 4 Ю-3 19.3 4.3 29.1 72.2

Ю-5 31.6 7.0 50.6 106.4

10 3 диапазон изменения этого отношения составляет от 3.1 до 72.2. При требуемой точности Ю-5 этот диапазон составляет от 4.7 до 106.4.

Отношение времен ¿зг и ¿дг, затрачиваемых на нахождение решения с произвольным начальным приближением градиентным методом и методом Ньютона, в зависимости от схемы дискретизации исходной задачи и количества точек, по которым строится интерполирующий сплайн, приводится в табл. 2. Это отношение изменяется при точности получения решения Ю-3 от 1.7 до 14, а при точности Ю-5 — от 2.6 до 28.5.

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

Таблица 2: Отношение (начальное приближение и = 0.)

Количество точек 5 10 20 40

Э 10~а 4.4 3.1 8.5 7.5

Ю-5 8.7 6.8 16.2 24.39

Р-К 2.1 1(Га 6.7 1.9 12.7 12.0

Ю-5 12.8 3.0 24.8 22.0

Р-К 2.2 Ю-3 7.3 1.7 13.3 10

Ю-5 14.5 2.6 28.5 20.2

Р-К 3 1(Га 7.6 1.8 14.0 13.0

Ю-5 15.0 2.8 26.8 26.6

Р-К 4 Ю-3 10.0 1.9 13.9 9.5

Ю-5 18.2 3.2 27.5 23.5

ным единице.

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

Основные результаты работы.

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

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

3. Установлено важное свойство предлагаемого подхода: по-

сле вычисления градиента функции решение сопряженного

уравнения для определения множителей Лагранжа, связанных с вычислением вторых производных, не представляет

трудности, т. к. основная матрица этого уравнения и основная матрица сопряженной системы, уже решенной при опре-

делении градиента функции, являются транспонированными друг другу.

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

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

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

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

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

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

Список публикаций по теме диссертации

1. Ю.Г. Евтушенко, Е.С. Засухина, В.И. Зубов. О численном подходе к оптимизации решения задачи Бюргерса с помощью граничных условий // Журн. вычисл. матем. и ма-тем. физики. 1997. т. 37. №12. С.1449-1458

2. Ю.Г. Евтушенко, Е.С. Засухина, В.И. Зубов. Применение метода быстрого автоматического дифференцирования при решении обратных задач. Тезисы докладов конференции "Обратные некорректно поставленные задачи", Москва, МГУ, 16-17 июня 1998 г. М: Изд-во МГУ. 1998. С. 31.

3. Yu. Evtushenko, Е. Zasuhina, V. Zubov. The application of FAD-methodology for computing second order derivatives. Abstracts of Third International Conference on Automatic Differentiation: "From Simulation to Optimization", June 19-23, 2000, Maison du Seminaire, Nice, France. Published by INRIA, Sophia Antipolis, France, P. 23.

4. Yu. Evtushenko, E. Zasuhina, V. Zubov. Fast AD technique and inverse problems. Abstracts of Third International Conference on Automatic Differentiation: "From Simulation to Optimization", June 19-23, 2000, Maison du Seminaire, Nice, France. Published by

INRIA, Sophia Antipolis, France, P. 23-24.

5. Yu. Evtushenko, E. Zasuhina, V. Zubov. FAD Method to Compute Second Order Deriva-tives. In.: "Automatic Differentiation of Algorithms: from Simulation to Optimization", New York: Inc. Springer- Verlag. 2002. P. 327-333.

6. Евтушенко Ю. Г., Засухина E. С., Зубов В. И. Вычисление вторых производных сложной функции с помощью обобщенной БАД-методологии. М: ВЦ РАН, 20057. Засухина Е. С. Применение быстрого автоматического дифференцирования для вычисления вторых производных сложных функций // Ж. вычисл. матем. и матем. физ. 2006. Т. 46. № 11. С. 1923-1949.

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

Подписано в печать 11.01.2007

Формат бумаги 60x84 1/16 Уч.-изд.л. 0,8. Усл.-печ. л. 1,25 Тираж 100 экз. Заказ 4

Отпечатано на ротапринтах в Вычислительном центре им. A.A. Дородницына Российской академии наук 119991, Москва, ул. Вавилова, 40

Засухина Елена Семеновна

Введение

1 Основные соотношения

1.1 Вычисление градиента с помощью обобщенной

Б АД-методологии

1.2 Вывод формул для вторых производных

1.3 Случай многошаговых процессов.

2 Задача оптимального управления

2.1 Схема Эйлера.

2.2 Модифицированная схема Эйлера.

2.3 Метод Рунге-Кутты.

3 Результаты численных расчетов

3.1 Описание расчетных задач.

3.2 Выбор шага.

3.3 Поиск "хорошего" начального приближения.

3.4 Анализ результатов расчетов.

3.5 Интерполяция с помощью кубической параболы.

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

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

Среди упомянутых задач обширный класс составляют оптимизационные задачи, значительную часть которых представляют задачи оптимального управления. Среди подходов к решению задач оптимального управления (см., например, работы [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. Показано, что метод Ньютона демонстрирует преимущество по всем перечисленным выше показателям перед градиентным методом даже в том случае, когда поиск решения начинается с произвольного приближения, не являющегося хорошим для метода Ньютона.

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

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

Заключение

1. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. М: Наука, 1982.

2. Васильев Ф. П. Численные методы решения экстремальных задач. М: Наука, 1988.

3. Пропой А. Я. Элементы теории оптимальных дискретных процессов. М: Наука, 1973.

4. Кротов В. Ф., Гурман В. И. Методы и задачи оптимального управления. М: Наука, 1973.

5. Полак Э. Численные методы оптимизации. М.: Мир, 1974.

6. Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление. М: Физматгиз, 1979.

7. Айда-Заде К. Р., Евтушенко Ю. Г. Быстрое автоматическое дифференцирование на ЭВМ // Матем. моделирование. 1989. Т. 1. С. 121-139.

8. Евтушенко Ю. Г., Мазурик В. П. Программное обеспечение систем оптимизации. М: Знание, 1989.

9. Evtushenko Yu. G. Automatic differentiation viewed from optimal control theory // Automatic differentiation of algorithms: Theory, Implementation and Application, SIAM, Philadelphia, 1991, pp. 25-30.

10. Evtushenko Yu. G. Computation of exact gradients in distributed dynamic systems // Optimizat. Meth. and Software. 1998. V. 9. pp. 4575.

11. Beda L. M., Korolev L. N., Sukkick N. V., Frolova T. S. Programs for Automatic Differentiation for the machine BESM // Technical Report, Institute for Precise Mechanics and Computation Technique, Academy of Science, Moscow, USSR, 1959. (In Russian)

12. Wengart R. E. A simple automatic derivative evaluation program // Comm. ACM, 7 (1964), pp. 463-464.

13. Wanner G. Integration gewohnlicher differentialgleichnugen, Lie Reihen, Runge-Kutta-Methoden // Vol. XI, B.I-Hochschulskripten, no. 831/831a, Bibliographisches Institut, Mannheim-Zurich, Germany, 1969.

14. Warner D. D. A partial derivative generator // Computing Science Technical Report, Bell Laboratories, 1975.

15. Kedem G. Automatic differentiation of computer programs // ACM Trans. Math. Software 6 (1980), pp. 150-165.

16. Rail L. B. Differentiation in Pascal-SC: Type GRADIENT // ACM Trans. Math. Software 10 (1984), pp. 161-184.

17. Sargent R. W. H., Sullivan G. R. The development of an efficient optimal control package // Proceedings of the 8th IFIP Conference on Optimization Technology 2, 1977.

18. Pfeiffer F. W. Some advances related to nonlinear programming // Tech. Report 28, SIGMAP Bulletin, New York, 1980.

19. Ponton J. W. The numerical evaluation of analytical derivatives. If Comput. Chem. Eng. 6 (1982), pp. 331-333.

20. Rail L. B. Automatic Differentiation: Techniques and Applications // Lecture Notes in Computer Sci. 120, Springer Verlag, Berlin, 1981.

21. Kagiwada H., Kalaba R., Rasakhoo N., Spingarn K. Numerical derivatives and nonlinear analysis // Math. Concepts Methods Sci. Engrg., Plenum Press, New York, London, 1986.

22. Director S. W., Rohrer R. A. Automatic network design — the frequency-domain case // IEEE Trans. Circuit Theory CT-16(1969), pp. 330-337, reprinted by permission.

23. Hachtel G. D., Bryton R. K., Gustavson F. G. The sparse tableau approach to network analysis and design // IEEE Trans. Circuit Theory CT-18(1971), pp. 101-113.

24. Ostrovskii G. M., Volin Yu. M, Borisov W. W. Uber die Berechnung von Ableitungen // Wiss. Z. Tech. Hochschule fur Chemie 13 (1971), pp. 382-384.

25. Linnainmaa S. Taylor expansion of the accumulated rounding error // BIT 16 (1976), pp. 146-160.

26. Speelpenning B. Compiling fast partial derivatives of functions given by algorithms: Ph.D thesis, University of Illinois of Urbana-Champaign, 1980.

27. Cacuci D. G., Weber C. F., Oblow E. M., Marable J. H. Sensitivity theory for general systems of nonlinear equations // Nuclear Sci. Engrg. 88 (1980), pp. 88-110.

28. Baur W., Strassen V. The complexity of partial derivatives // Theoret. Comput. Sci. 22 (1983), pp. 317-330.

29. Ким К. В., Нестеров Ю. Е., Черкасский Б. В. Эффективный алгоритм дифференцирования и экстремальные задачи // Экономика и математические методы. 1984. Т. 20. С. 309-318.

30. Iri М., Tsuchiya Т., Hoshi М. Automatic computation of partial derivatives and rounding error estimates with application to large-scale systems of nonlinear equations // Comput. Appl. Math. 24 (1988), pp. 365-392.

31. Griewank A. On automatic differentiation // Mathematical Programming: Recent Developments and Applications, by eds. M. Iri and K. Tanabe, Kluwer, Dordrecht, the Netherlands, 1989, pp. 83108.

32. Ким К. В., Нестеров Ю. Е., Черкасский Б. В. Оценка трудоёмкости вычисления градиента // ДАН. 1984. Т. 275. М. С. 1306-1309.

33. Griewank A., Reddien G. W. Computation of cusp singularities for operator equations and their discretizations // J. Comput. Appl. Math. 26 (1989), pp. 133-153.

34. Griewank A., Corliss G. F. (eds.) Automatic differentiation of algorithms: Theory, Implementation and Application, SIAM, Philadelphia, 1991.

35. Griewank A., Reese S. On the calculation of Jacobian matrices by the Markowitz rule // Automatic differentiation of algorithms: Theory, Implementation and Application, SIAM, Philadelphia, 1991, pp. 126135.

36. Griewank A. Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation // Optimization Methods and Software, 1992. V. 1. pp. 35-54.

37. Griewank A. Some bounds on the complexity of gradients, Jacobians, and Hessians // Complexity in Nonlinear Optimization, by ed. P.M. Pardaros, World Scientific, River Edge, NJ, 1993, pp. 128-161.

38. Averick В. M., More J. J., Bishof С. H., Carle A., Griewank A. Computing large sparse jacobian matrices using automatic differentiation // SIAM J. Scientific Computing 15(1994), pp. 285-294.

39. Bischof С. H., Corliss G., Griewank A. Structured second- and higher-order derivatives through univariate Taylor series // Optim. Methods Softw. 2 (1993), pp. 211-232.

40. BerzM., Bischof С. H., Corliss G., Griewank A. (eds). Computational differentiation techniques, applications, tools, SIAM, Philadelphia, 1996.

41. Fisher H., Fander H. A minimal code list // Tech. Report, 1999.

42. Griewank A. Evaluating derivatives, SIAM, Philadelphia, 2000.

43. Rostaing N., Dalmas S., Galligo A. Automatic differentiation in Odissee // Tellus 45A (1993), pp. 558-568.

44. Averick В. M., Carter R. G., More J. J, Xue G.-L. The MINPACK-2 test problem collection, Preprint MCS-P153-0692, ANL/MCS-TM-150, Rev. 1, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne IL, 1992.

45. Bartholomew-Biggs M. C., Bartholomew-Biggs L., Christianson B. Optimization and automatic differentiation in Ada: Some Practical Experience // Optim. Methods Softw. 4 (1994), pp. 47-73.

46. Czyzyk J., Mesner M. P., More J. J. The network-enabled optimization server, Preprint ANL/MCS-P615-1096, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, 1997.

47. Griewank A., Juedes D., Utke J. ADOL-C, a package for the automatic differentiation of algorithms written in C/C++ // ACM Trans. Math. Software 22 (1996), pp. 131-167.

48. Bischof С. H., Griewank A. ADIFOR: A FORTRAN system for portable automatic differentiation, Preprint MCS-P317-0792, Mathematic and Computer Science Division, Argonne National Laboratory, Argonne, Illinois, 1992.

49. Bischof С. H., Carle A., Khademi P. M., Mauer A. The ADIFOR 2.0 system for the automatic differentiation of FORTRAN 77 programs // IEEE Computational Sci. Engrg. 3 (1996), MCS-P481-1194.

50. Bischof С. H., Corliss G. F., Green L., Griewank A., Haigler K., Newman P. Automatic differentiation of advanced CFD codes for multidisciplinary design // Journal of Computing Systems in Engineering 3 (1992), pp. 625-638.

51. Bischof С. H., Dilley F. A compilation of automatic differentiation tools: Presented at the 1995 international convention on industrial and applied mathematics // SIGNUM Newsletter 30 (1995), 3, pp. 2-20.

52. Iri M. Simultaneous computation of functions, partial derivatives and estimates of rounding errors Complexity and practicality // Japan Journal of Applied Mathematics. 1984. V. 1. pp. 223-252.

53. Iri M., Kubota K. Methods of fast automatic differentiation and applications, Research memorandum RMI 87-02, Department of Mathematical Engineering and Instrumental Physics, Faculty of Engineering, University of Tokyo, 1987.

54. Евтушенко Ю. Г., Засухша E. С., Зубов В. И. О численном подходе к оптимизации решения задачи Бюргерса с помощью граничных условий // Ж. вычисл. матем. и матем. физ. 1997. Т. 37. Я5 12. С. 1406-1414.

55. Албу А. Ф., Горбунов В. И., Зубов В. И. Оптимальное управление процессом плавления // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. № 4. С. 517-531.

56. Албу А. Ф., Горбунов В. ИЗубов В. И. Об оптимальном управлении процессом плавления // Матем. моделирование. 2000. Т. 12. № 5. С. 114-118.

57. Албу А. Ф., Зубов В. И. О процессе плавления с ограничением на скорость остывания // Матем. моделирование. 2002. Т. 14. № 8. С. 119-123.

58. Албу А. Ф., Зубов В. И. Оптимальное управление процессом кристаллизации вещества // Ж. вычисл. матем. и матем. физ. 2004. Т. 44. № 1. С. 38-50.

59. Албу А. Ф., Зубов В. И. Оптимизация процесса плавления и кристаллизации вещества. М: ВЦ РАН, 2004.

60. Birgin E. G. Automatic differentiation and application, PhD Thesis. Applied Mathematic Department, IMECC-UNICAMP, Brasil, 1998. (in Portuguese)

61. Birgin E. G., Evtushenko Yu. G. Automatic differentiation and spectral projected gradient methods for optimal control problems // Optimizat. Meth. and Software. 1998. V. 10. pp. 125-146.

62. Евтушенко Ю. Г., Засухина E. С., Зубов В. И. Вычисление вторых производных сложной функции с помощью обобщенной БАД-методологии. М: ВЦ РАН, 2005.

63. Засухина Е. С. Применение быстрого автоматического дифференцирования для вычисления вторых производных сложных функций // Ж. вычисл. матем. и матем. физ. 2006. Т. 46. № 11. С. 1923-1949.

64. Lellouche J.-M., Devenon J.-L., Dekeyser I. Boundary Control of Burgers' Equation A Numerical Approach // Computers Math. Applic. 1994. V. 28. № 5. pp. 33-44.

65. Грачев H. И., Филъков A. H. Решение задач оптимального управления в системе ДИСО. М: Вычислительный центр АН СССР, 1986.1. Таблицы и рисункив =