авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

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

Засухина Елена Семеновна Быстрое автоматическое дифференцирование в задачах оптимального управления Специальность 01.01.09 - Дискретная математика и математическая кибернетика

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

Москва – 2007

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

Научный консультант: доктор физико-математических наук Зубов Владимир Иванович Официальные доктор физико-математических наук, профессор оппоненты: Лотов Александр Владимирович кандидат физико-математических наук, доцент Бирюков Александр Гаврилович

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

Защита состоится « 22 » февраля 2007 г. в 16 часов на заседании диссертационного совета Д 002.017.02 Вычислительного центра им. А.А. Дородницына Российской академии наук по адресу:

119991, Москва, ул. Вавилова, 40.

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

Автореферат разослан « 18 » января 2007 г.

Ученый секретарь диссертационного совета доктор физико-математических наук В.В. Рязанов

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

Апробация работы. Основные положения и результаты ра боты были доложены и обсуждены на следующих научных кон ференциях: Всероссийская конференция "Обратные и некоррект но поставленные задачи (Москва, МГУ, 1998 г.);

3-я Международ ная конференция по быстрому автоматическому дифференциро ванию (Third International Conference on Automatic Dierentiation:

"From Simulation to Optimization 2000, Maison du Seminaire, Nice, France ) (Франция, 2000г.);

а также на научных семинарах отдела прикладных проблем оптимизации ВЦ РАН (Москва, 2001-2006);

на научных семинарах отдела механики сплошных сред ВЦ РАН (Москва, 2006);

на научном семинаре кафедры математических основ управления МФТИ (г. Долгопрудный, 2006).

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

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

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





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

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

Пусть W : Rn Rr R1, : Rn Rr Rn дважды непрерывно дифференцируемые отображения. Рассмотрим систему из n урав нений связи (x, u) = 0n, где x Rn и u Rr. Пусть матрица x (x, u) неособенная всюду в интересующей нас области. Тогда по теореме о неявной функции существует дважды непрерывно дифференцируемая функция x = x(u), такая что (x(u), u) = 0n.

Задача состоит в нахождении вторых производных функции (u) = W (x(u), u).

Чтобы определить с помощью обобщенной БАД-методологии градиент функции (u), вводится функция Лагранжа L(x, u, p) = W (x, u) + p (x, u), где p - множитель Лагранжа, p Rn. Продифференцировав L(x, u, p) по p и по x и приравняв нулю полученные производные, получим исходную систему урав нений связи и сопряженную систему уравнений Lx (x, u, p) = Wx (x, u) + x (x, u)p = 0n.

Выражение Lu (x(u), u, p(u)), где функции x(u) и p(u) удовле творяют исходной и сопряженным системам уравнений, опреде ляет градиент функции (u) n i · pi.

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

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

d2 (u)/du2 = Wx u + (Wx u ) + Wu + Wx x + u n pi · (i + i + (i + i + u u ) x ), u u x x x i= Основная матрица сопряженной системы относительно сопря женной переменной p и основная матрица сопряженного матрич ного уравнения относительно – матрицы сопряженных пере менных, входящих в формулу для вторых производных, являют ся транспонированными друг другу. Поэтому после вычисления градиента функции решение сопряженного матричного уравне ния относительно матрицы не представляет трудности.

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

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

Уравнения, описывающие процесс, расщепляются на N соотно шений вида xi = F (i, Xi, Ui ), 1 i N, где Xi, Ui – заданные подмножества множеств {x1,..., xN } и {u1,..., uN } соответственно.

Во всех рассматриваемых матрицах множества строк и столб цов разделяются на N равных частей (возникают блок-строки и блок-столбцы), эти матрицы рассматриваются как матрицы блоч ных элементов. Вводится матрица B, разность между которой и основной матрицей сопряженной системы относительно множите ля Лагранжа p составляет единичную матрицу. Вводится также матрица C, C = u. Сопряженное матричное уравнение для опре деления матрицы с введением матриц B и C представляется в виде:

C + B · = 0nr.

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

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

Рассматривается задача оптимального управления процессом, описываемым системой обыкновенных дифференциальных урав нений dx/dt = f (t, x, u, ), T1 t T2, x(T1, x0 ) = x0, где f (t, x, u, ) – дважды непрерывно дифференцируемая функ ция, x Rs – вектор состояний, управление u есть произволь ная кусочно непрерывная функция переменной t со значениями в U, U – компакт в пространстве Rm, – управляющий параметр, V Rq, V компактное множество. Величины T1, T2, x1 мо гут быть как фиксированными, так и свободными. Если они не фиксированы, то должны определяться из решения задачи опти мизации, и в этом случае их следует включить в вектор.

Задача состоит в нахождении управляющей функции u(t), u(t) U, T1 t T2, и управляющего вектора, V, которые минимизируют целевую функцию W (x(T2, x0 ), ). Здесь x(t, x0 ) обозначает решение системы уравнений, описывающей управляе мый процесс, при заданных u(t) и, удовлетворяющее начальному условию x(T1, x0 ) = x0.

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

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

rrrr @ r r @ rr @r @ rrrr @ rrrr r r @ rrrr B= rr C= rrrr @r @ rrrr rrrrrrrrrrrr @r r @ rr @r @ @ Рис. 1.

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

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

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

r r r r r r r r r r r = r r r r r r r r r r r r r r r r r r r r r r r r r Рис. 2.

Высота ступенек в матрице составляет M блочных элементов (M – порядок аппроксимации исходной задачи методом Рунге Кутты), ширина – один блочный элемент. Из структуры матрицы следует вывод о том, что количество уравнений, которое необ ходимо решить для нахождения вторых производных функции (u), равно (1 s/n)(1 + q/r)nr/2, что с увеличением N стремит ся к nr/2.

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

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

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

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

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

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

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

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

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

Рис. 4.

2, 1, tness/(tf*r) Задача Задача Задача 0, 0 50 100 150 200 Размерность управления r Рис. 5.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(хорошее начальное приближение) Количество точек 5 10 20 Э 8.8 8.4 18.1 37. 105 18.0 16.2 33.8 66. Р-К 2.1 14.1 3.1 21.5 49. 105 22.8 4.7 37.5 80. Р-К 2.2 16.0 3.1 25.1 58. 105 27.2 5.0 44.5 95. Р-К 3 17.9 3.6 27.8 63. 105 29.5 5.8 47.7 102. Р-К 4 19.3 4.3 29.1 72. 105 31.6 7.0 50.6 106. 103 диапазон изменения этого отношения составляет от 3.1 до 72.2. При требуемой точности 105 этот диапазон составляет от 4.7 до 106.4.

Отношение времен tgr и tN, затрачиваемых на нахождение ре шения с произвольным начальным приближением градиентным методом и методом Ньютона, в зависимости от схемы дискрети зации исходной задачи и количества точек, по которым строится интерполирующий сплайн, приводится в табл. 2. Это отношение изменяется при точности получения решения 103 от 1.7 до 14, а при точности 105 от 2.6 до 28.5.

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

(начальное приближение u = 0.) Количество точек 5 10 20 Э 4.4 3.1 8.5 7. 105 8.7 6.8 16.2 24. Р-К 2.1 6.7 1.9 12.7 12. 105 12.8 3.0 24.8 22. Р-К 2.2 7.3 1.7 13.3 105 14.5 2.6 28.5 20. Р-К 3 7.6 1.8 14.0 13. 105 15.0 2.8 26.8 26. Р-К 4 10.0 1.9 13.9 9. 105 18.2 3.2 27.5 23. ным единице.

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

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

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

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

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

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

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

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

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

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

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

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

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

Изд-во МГУ. 1998. С. 31.

3. Yu. Evtushenko, E. Zasuhina, V. Zubov. The application of FAD methodology for computing second order derivatives. Abstracts of Third International Conference on Automatic Dierentiation: "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 Dierentiation: "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 Dierentiation of Algorithms:

from Simulation to Optimization New York: Inc. Springer- Verlag.

2002. P. 327-333.

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

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

С. 1923-1949.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.