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

• Автор: Засухина, Елена Семеновна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 120 с. : ил.

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]).
В течение ряда лет прилагаются усилия по созданию пакетов компьютерных программ, вычисляющих производные сложных функций с по-

г = т ■ N + д), с помощью которых вычисляются вторые производные сложной функции О(гх). Система уравнений для определения Х(1) в нашем случае имеет следующий вид:
(у'о-я строка го-й блок-строки С)Т + (2.72)
+ВТ • А(0 - А(/) = 0„,
где го и у‘о определяются из соотношений
I — (*о — 1) ■т 4- 7о> 1 ^ й) ^ N + 1, (2.73)
1 < 7о < Щ если 1 < го < АГ,
1 < у‘о < д, если г'о = N + 1.
Структуру матрицы Вт иллюстрирует рис. 32.
Напомним, что х была организована таким образом:
хт = [Щ)т (*Г У (4_,Г йГ].
Аналогичным образом представим и А(/):
Лт(() = [(А?(())Т,(А!(())Т (АГ-1(0)т (А°я_1(г))т,
(А^_1(/))т, • • •) (гтт, т)п
А 2(0 ед®, г = 1 А-1, у = 0 М
АЗД € Я5.
А теперь, принимая во внимание структуру матриц В и С, напишем более детально систему уравнений (2.72) для определения множителей Лагранжа А(/).
Каждому I, I = 1,2 г, поставим в соответствие числа го и у’о, которые определяются из соотношений (2.73).
Если 1 < / < (А — 1) • т, т. е. 1 < г'о < А - 1, то система уравнений (2.72) принимает следующий вид:
А ?(/) = О.,
А}(1) = (В^1ум+щ_1ум+2)т ■ Аг'(/)+
+ (у'о-Я строка С*0)(г0_1).м+2)Т • кго,
МУ) = (-б(1-1)'М+1,(г-1)-М+1+у)Т • (0 +
+{В(г-).М+^г-1)-М+1+^ ■ Ц (0+ ^ 74)
4~(уо_я Строка Сг0|(г0_)-М++]) ' ^г,г0) у = 2 М — 1,
А-+1(/) = ^^{В^хум+х+к^мпУ • АК0+
+ (У0"Я Строка бд0)20.ДТ+1) ' ^г,г’о> г = 1 А