Содержание к диссертации
Введение
1. Вырожденные задачи оптимального управления и дифференциальных уравнений 19
1.1. Задачи оптимального управления, имеющие особое управление 20
1.2. Задачи оптимального управления с фазовыми ограничениями 24
1.3. Дифференциально-алгебраические системы уравнений 33
2. Метод параметризации 40
2.1. Постановка задачи и ее параметризация 40
2.2. Сходимость метода параметризации
2.2.1. Условия сходимости 43
2.2.2. Расширение4 терминальных ограничений 46
2.2.3. Теорема аппроксимации
2.3. Первые производные параметризованных функционалов 53
2.4. Вторые производные 56
2.5. Задачи с оптимизируемыми параметрами 64
3. Реализация метода параметризации 74
3.1. Используемые методы и алгоритмы 74
3.2. Задача с особым управлением 77
3.3. Задача оптимального планирования с фазовым ограничением 81
3.4. Задача со смешанным критерием качества 85
3.5. Сингулярные задачи дифференциальных уравнений
3.5.1. Краевая задача с малым параметром при старшей производной 87
3.5.2. Дифференциально-алгебраическая система 91
3.5.3. Интегро-дифференциальная система 94
Заключение 97
Литература
- Задачи оптимального управления с фазовыми ограничениями
- Дифференциально-алгебраические системы уравнений
- Первые производные параметризованных функционалов
- Задача со смешанным критерием качества
Введение к работе
Актуальность темы. Задачи оптпмаїьного управления (ОУ), наряду с дифференциальными уравнениями (ДУ), являются одними из основных в математическом моделировании динамических процессов в различных областях техники, технологии, естествознания и экономики. Имеется достаточно широкий набор численных методов для различных типов задач, однако усложнение проблем, охватываемых математическим моделированием, приводит к вычислительным задачам, для которых известные методы становятся малоэффективными или неприменимыми. Это так называемые вырожденные или нерегулярные задачи ОУ и ДУ. Они представляют специальный класс некорректно поставленных вычислительных задач. Явление вырождения условий экстремума в оптимальном управлении получило название "особых управлений". Такие задачи существенно сложнее для исследования и численного решения. Другой сложный класс - это задачи с промежуточными фазовыми ограничениями. Из класса задач для сингулярных дифференциальных уравнении выделим дифференциально-алгебраические, системы уравнений и уравнения, содержащие малый параметр при старшей производной. Таким образом, нерегулярные задачи математического моделирования становятся типичным яатением и их усложнение требует постоянного развития соответствующей теории и численных методов. Разработка эффективных методов их решения является одной из валсных проблем математической кибернетики.
Среди большого количества исследовании, посвященных развитию численных методов решения вариационных задач, выделим работы Полака Э.1, Черноусько Ф.Л.2, Федоренко Р.П. 3, Евтушенко Ю.Г. 4, Бояринцева Ю.Е., Чистякова А.Ф.. Проблема решения вы- ; рожденных задач ОУ в первую очередь связана с именами Г.Келлп5, Р.Коппа и Г.Мойера6. Дальнейшее развитие было продолжено в ра-
'Полак Э. Численные, методы оптимизации. Единый подход. V.: Мир, 1974.
2Крылов И.А., Черноусько Ф.Л. О методе последовательных приближений для решений задач оптимального управления. -//ЖВМпМФ. 1962. Т.2. N6. С.Ш2-Ш8.
3Федоренко Р.П. Приближенное решение задач оптимального управления. М.: Наука, 1978.
Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. M.: Наука, 1082.
5Кслли Г. Необходимое условие для особых экстремален, основанное на второй вариации. -Ракетная техника и космонавтика. 1964. Х8. С.26-29.
6Копп Р., Монер Г. Необходимые условия оптимальности особых экстремалей. - Ракетная техника и космонавтика. 1965. М8. С.81-01.
ботах Г.Габасова и Ф.М.Кирилловен', В.А.Срочко.
Несмотря на широкий набої) численных методов решения задач ОУ и ДУ, они ограничиваются в основном регулярными задачами. Для нерегулярных задач разрабатываются узко специализированные методы. Поэтому, в нерегулярных случаях представляется перспективным использование методов второго порядка (см., например, Анрион Р.8). Возможность развития численных методов с использованием вторых производных заложена, в частности, в работе Горбунова В .К. 9.
Цель работы состоит в развитии и практической реализации метода параметризации задач ОУ 9. Развитие метода с целью использования вторых производных минимизируемого функционала по параметрам управления. Обоснование сходимости метода параметризации. Исследование и применение метода параметризации второго порядка в вырожденных задачах оптимального управления и сингулярных дифференциальных уравнениях.
Методы исследования. При формулировке и доказательстве результатов в диссертационной работе используются элементы теории оптимального управления, дифференциальных уравнений, многозначных отображений.
Научная новизна. Метод параметризации развит с целью использования вторых производных минимизируемого функционала по параметрам управления. Это позволяет применять метод Ньютона или линейно-квадратичной аппроксимации в задачах ОУ, что актуально в вырожденных случаях. Получена теорема о сходимости метода -параметргаацци_в^яулае^омпактаого_!г^^ дельно выделен случай регулярных терминальных ограничений.
Теоретическая и практическая значимость диссертационной работы заключается в развитии метода параметризации задач ОУ, расширяющем область его применения, в частности, на вырожден-л ные задачи ОУ и ДУ.
На защиту выносятся следующие положения:
1. Развитие нового метода параметризации задачи оптимального управления с целью использования при численном решении вто-
'Габасов Г., Кириллова Ф.М. Особые оптимальные управления. М.: Наука, 1973.
*Анрнон Р. Теория второй вариации и ее приложения в оптимальном управлении. - пер с франц., Наука, Гл. ред. фпз.-мат. лит., 1979, 208 С.
'Горбунов U.K. Метод параметризации задач оптимального управления // ЖВМиМФ. І979. Т.19. N2. С. 292-S03.
рых производных минимизируемого функционала задачи по параметрам искомого управления.
-
Обоснование сходимости метода параметризации по функционалу задачи при сгущении узлов искомого управления, в случае компактного ограничения на управление.
-
Алгоритмизация метода параметризации, ориентированного на решение вырожденных задач оптимального управления, задач с промежуточными фазовыми ограничениями, а также сингулярных задач дифференциальных уравнений.
-
Вычислительный эксперимент, выявляющий практическую эффективность реализованного метода в проблемных задачах.
Апробация работы. Результаты диссертации докладывались и обсуждались на:
VI научно-практической конференции Ульяновского государственного университета (г. Ульяновск, 1997 г.);
Всероссийской научной конференции ''Алгоритмический анализ некорректных задач" (г. Екатеринбург, 1998 г.);
III международной конференции "Дифференциальные уравнения и их приложения" (г. Саранск, 1998 г.);
II международной конференции "Математическое моделирование физических, экономических, социальных систем и процессов" (г. Ульяновск, 1999 г.);
IV международной конференции "Дифференциальные уравнения п нх приложения" (г. Саранск, 2000 г.).
Личный вклад. Основные теоретические положения разработаны совместно с научным руковолптелем. Вывод вторых производных, по параметрам, определяющим управление, исследование приложений, анализ результатов, выводы из них, программная реализация метода н вычислительный эксперимент выполнены автором самостоятельно.
Публикации. По теме диссертации опубликовано 11 работ.
Структура її объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 67 наименовании. Общий объем диссертации составляет 107 страниц.
Задачи оптимального управления с фазовыми ограничениями
Очевидно, что в нетривиальном случае для получения решения с достаточной степенью точности требуется большое число точек аппроксимации t{, тем самым существенно растет объем вычислений, и как следствие, падает надежность результатов. Кроме того, данная схема ограничивает набор численных методов решения задач оптимального управления, способных справиться с задачей (1.2.2). В основном, эти методы сводятся к замене исходной системы дифференциальных уравнений дискретной системой, а затем последующим решением конечномерной задачи математического программирования. Проблема данных методов заключается в том, что в сложных ситуациях требуется густая сетка, тем самым возрастает размерность конечномерной задачи, что, в свою очередь, влечет дополнительные трудности по решению этой задачи.
Вторая схема численного решения задач оптимального управления с фазовыми ограничениями основана на стандартном методе штрафных функций. Введем обозначение а+ = тах{а, 0} - положи 1.2. Задачи ОУ с фазовыми ограничениями тельная срезка, Рассмотрим следующую задачу приближения в каждой задаче берется решение, полученное в предыдущей задаче.
К достоинствам данной схемы следует отнести то, что она позволяет применять достаточно богатый арсенал численных методов решения задач оптимального управления. Однако данная схема в наиболее простом варианте q = 2 обладает тем же существенным недостатком, который имеет стандартный метод штрафных функций, применяемый для конечномерных задач нелинейного программирования. При увеличении параметра штрафа резко ухудшается сходимость задачи оптимального управления, так как экстремальная задача приобретает овражный характер, и получение достаточно хорошего приближения вызывает большие затруднения. В случае q = 1 параметр штрафа конечный, но здесь требуется применять сложные и трудоемкие методы недифференцируемой минимизации.
В [16, 19] был предложен новый вариант снятия фазовых ограничений на основе штрафных функций, когда задача оптимального
Задачи ОУ с фазовыми ограничениями управления с ограничениями смешанного типа путем расширения фазового пространства сводится к задаче только с терминальными ограничениями. Для новой задачи исследуется специфика принципа максимума.
Рассмотрим управляемую систему, фазовое состояние которой представляется вектором х = (х\,... ,хп) евклидового пространства Еп, управляющие воздействия - вектором и = (щ,... ,иг) евклидового пространства Ег.
Мы ограничиваемся рассмотрением терминального функционала, автономного случая и отрезка времени [ о5Г], так как известными преобразованиями к такому виду могут быть сведены более общие задачи оптимального управления. Выделение ограничений (1.2.5),
Задачи О У с фазовыми ограничениями где часть компонент функций hj может зависить лишь от управляющих переменных, позволяет считать U множеством достаточно простой структуры (например, неотрицательный ортант Ет+ или совпадающим с " ). Практически условиями (1.2.5) нецелесообразно описывать лишь условия дискретности.
В качестве допустимых управляющих функций u(t) ограничимся классом кусочно-непрерывных функций со значениями в U.
В дальнейшем будем использовать следующие обозначения: а+ — тах(а, 0) - функция положительной срезки, (a, b)v - скалярное произведение и „ - соответствующая норма в Ev.
Эта функция равна нулю тогда и только тогда, когда ее аргументы удовлетворяют условиям (1.2.5). Она непрерывна и непрерывно дифференцируема по фазовым переменным, причем ІдР(х.и) ,.,, , ..,„ idhilx.u) .,, , ,,.„ idh-iix.u)
Таким образом, исходная задача с промежуточными фазовыми ограничениями смешанного типа (1.2.5) эквивалентна следующей за 1.2. Задачи О У с фазовыми ограничениями даче с терминальными ограничениями: минимизировать функционал (1.2.8) при условиях (1.2.4), (1-2.6), (1.2.7), (1.2.9), (1.2.10).
Новая формулировка исходной трудной задачи оптимального управления позволяет применять для ее качественного исследования и численного решения довольно развитые методы, ориентированные на задачи без промежуточных фазовых ограничений (в частности, предложенный метод параметризации). В описанном приеме использована штрафная функция снимаемых промежуточных ограничений, но без какого-либо коэффициента.
Формальное преобразование задачи часто не уменьшает ее трудности. Исследуем как проявляется специфика фазовых ограничений (1.2.5) в условиях оптимальности. Для новой задачи справедливо необходимое условие оптимальности принцип максимума Понтря-гина. Рассмотрим это условие.
Дифференциально-алгебраические системы уравнений
Доказательство. Очевидно, инфимум числового множества совпадает с инфимумом его замыкания, поэтому величина (2.2.6) может быть определена как
В силу компактности множеств т(г) эта величина определена и конечна при любых г 0. Из свойства неубывающей по включению монотонности отображения т следует невозрастание функции J (г). В [60, гл.1, Лемма 1.1] показано, что для задачи минимизации непрерывной функции на значениях компактного и полунепрерывного сверху многозначного отображения ее экстремальное значение является полунепрерывной снизу функцией аргумента допустимого отображения. Если допустимое отображение непрерывно, то значение задачи - непрерывная функция. Таким образом, экстремальное значение ( ) задачи минимизации непрерывной функции до(х) на значениях полунепрерывного сверху отображения т в общем случае является полунепрерывной снизу функцией. Это значит, что для любых значений го 0 и є 0 существует такое число 8 0, что для любых г 0 и \г — г0 8 будет выполнено
Легко видеть, что это свойство в силу установленного невозрастания J(r) влечет непрерывность справа в VQ. В регулярном случае функция J(r) непрерывна. Теорема доказана.
Неравенство (2.2.8) означает непрерывность справа в точке г$ = 0. Таким образом, в силу теоремы 1 задача ОУ (2.1.1)-(2.1.4), удовлетворяющая условию ограниченности, устойчива по расширению терминального множества.
Аналогично расширим ограничения из (2.1.8) редуцированной задачи (2.1.8). Будем рассматривать задачу минимизации (роі ш1,... , «;Л) из (2.1.8) на множестве параметров управления
Эта задача при любом г 0 и достаточно большом N(r) разрешима. Если для исходной задачи (2.1.1)-(2.1.4) выполнено УО, то определена конечная величина (2.2.10), аппроксимирующая при достаточно малом г 0 значение J . При этом для любого числа є 0 существует процесс {игє (t), xre (t)\, удовлетворяющий условию
Для такого процесса при достаточно большом N(r.e) N(r) существует параметризованный процесс {uN(t),xNs(t)}, определяемый набором параметров {«;1є,... ,wNs} из множества (2.2.9), для которого
Теорема 3. Если задача (2.1.1)-(2.Ц) удовлетворяет условию ограниченности, то для любых положительных чисел г и є существует такое число N — N(r,e), что параметризованная задача (2.2.9), (2.2.10) разрешима и ее значение р (г) удовлетворяет неравенствам (2.2.13).
Таким образом, условие ограниченности задачи ОУ (2.1.1)-(2.1.4) обеспечивает ее устойчивость по расширению терминального множества и возможность сколь угодно точной аппроксимации разрешимой задачи параметризованной конечномерной задачей (2.2.9),(2.2.10) как по терминальным условиям (2.1.3), так и по функционалу (2.1.4). Условие регулярности терминальных ограничений обеспечивает непрерывность аппроксимации минимизируемого функционала по параметру грубости аппроксимации траекторий.
Остановимся на проблеме выбора параметра расширения г. Если терминальные условия (2.1.3) не слишком стенительны, то естественно ожидать разрешимость задачи нелинейного программирования (2.1.8), соответствующей г = 0. Но если априорно трудно выбрать умеренное число N, определяющее размерность аппроксимирующей задачи, и допустимую точку системы ограничений из (2.1.8), то можно применить релаксационно-штрафной метод [21]. Для этого переменная г 0 назначается дополнительным параметром оптимизации и вместо задачи (2.2.10) ставится задача минимизации на
Первые производные параметризованных функционалов
Метод параметризации задач оптимального управления, изложенный в главе 2, сводит исходную динамическую задачу к задаче нелинейного программирования, которая может иметь достаточно сложный вид. Вместе с тем эта задача имеет свою специфику. Она выражается прежде всего в упорядочении точек сетки, определяющей структуру искомого управления. В случае, когда ищется непрерывное и, возможно, непрерывно дифференцируемое управление, это выражается в специальных условиях на параметры управления„ Из этого следует, что для создания эффективных алгоритмов реализации метода параметризации следует использовать достаточно сложные методы нелинейного программирования, учитывая специфику ограничивающих функций.
Здесь для решения конечномерных задач НП, возникающих в ходе реализации метода параметризации, использовалось несколько методов нелинейного программирования: градиентный метод (наискорейший спуск), метод проекции градиента, метод Дэвидона-Флэтчера-Пауэлла, метод Ньютона. Выбор этих методов НП обоснован свойствами получаемых конечномерных задач.
Таким образом исходная задача минимизации (3.1.1), (3.1.2) на множествах Wi, \\\ сводится к минимизации функционала (3.1.4) на И7і, W-2- В том случае, когда Wi, W-i задаются системой неравенств, соответствующие ограничения можно также включать в штрафную функцию (3.1.4), и применять методы безусловной минимизации. При этом вторые производные (метод Ньютона) достаточно вычислять лишь для одного (минимизируемого) функционала.
Остановимся подробнее на задаче о проекции на множество Ид. Пусть 2 - фиксированная точка пространства Rs. Построить проекцию точки z на W\ - решить задачу квадратичного программирования (КП):
Матрица А определяется ( ) в том случае, когда конечный момент времени задачи оптимального управления фиксирован, и, таким образом, матрица линейных ограничений имеет s столбцов и (s + 1) строк. Если же конечный момент времени подвижен, то в матрице ( ) отсутствует последняя строка, и она имеет s столбцов и s строк.
Алгоритм решения задач КП из [17] использует матрицу Грама, которая определяется скалярным произведением активных ограничений строк матрицы А. В силу специфики ограничений (3.1.3) матрица Грама данной задачи имеет простую структуру, и решение соответствующей линейной системы уравнений находится обратным ходом Гауса без предварительного LU разложения. При этом, в отличии от общего случая алгоритма, хранение матрицы Грама не обязательно.
Задачи, имеющие на оптимальной траектории участки с особым управлением, сложны как для качественного анализа так и для решения стандартными численными методами. Это происходит из-за
Задача с особым управлением 78 того, что условия экстремума первого порядка в особых задачах вырождаются, поэтому логично применять для таких задач методы, основанные на условиях второго порядка, Одним из таких методов может быть метод параметризации со вторыми производными. Рассмотрим задачу оптимального управления из [4].
В [4] для оптимизации билинейных динамических систем с квадратичным критерием качества предложены процедуры улучшения на основе операции проектирования. При этом сходимость существенно зависит от некоторого параметра метода с неопределенным правилом выбора.
Исходную задачу ОУ сведем к классической вариационной задаче: без ограничений на управляющую функцию. Для этого используем метод снятия промежуточных фазовых ограничений путем расширения фазового пространства.
Задача безусловной минимизации решалась следующими методами: градиентным методом (наискорейшего спуска), методом Дэвидона-Флэтчера-Пауэлла, методом Ньютона. В качестве начального приближения во всех трех случаях рассматривался набор: v\\ — —0.5, v\2 = 0, г»2і = 0.5, г 22 = 0, т = 1, стартовые параметры штрафа pi = р2 — 100. Значение функционала при этом приближении J (и) = 173. Все задачи Коши решались методом Рунге-Кутты 4-го порядка с шагом интегрирования равным 0.1. Пересчет коэффициентов штрафа происходил (в отличие от точной схемы Узавы) каждые 15 итераций.
3.2. Задача с особым управлением При решении методом наискорейшего спуска (МНС) конечномерной задачи безусловной минимизации после 20 итераций было получено решение: J (и) = 0.36. Дальнейшее уменьшение значения функционала на каждой итерации было менее одного процента. Такое изменение функционала можно объяснить либо тем, что задача в окрестности оптимального решения прнимает овражный характер, либо тем, что условия экстремума первого порядка вырождаются. После 210 итераций процесс был остановлен
Задача со смешанным критерием качества
Таким образом, функциональная задача перешла в задачу нелинейного программирования относительно параметров управления vi, v2l г, Г и параметра интенсивности р. Выбор кусочно-постоянного управления определяется линейностью системы по параметру и.
Конечномерная задача решалась в два этапа: на первом градиентным методом, на втором уточнялась методом Ньютона, на основе
Сингулярные задачи дифференциальных уравнений 87 формул для вторых производных. Выбор этого способа решения определяется тем, что полученная задача нелинейного программирования в окрестности оптимального решения несет овражный характер, поэтому градиентные методы становятся практически неэффективны, с другой стороны, если приближение достаточно далеко от оптимального, то сходимость метода Ньютона становится проблематичной.
Все задачи Коши для исходной системы, сопряженных систем и первых вариаций траектории (необходимых для вычисления вторых производных) решались методом Рунге-Кутты второго порядка с шагом интегрирования 0.05. Получено численное решение v\ = 4.50293, v2 = -4.50132, т = 1.30357, Т - 1.71898, при этом значение функционала J(u.p) = 7.93908, что совпадает с результатом [37].
Сложность решения этой задачи заключается в проявлении пограничного слоя при стремлении є к нулю. Для таких задач разрабаты 3.5. Сингулярные задачи дифференциальных уравнений ваются специальные алгоритмы [31, 32].
Задача оптимального управления решалась при нескольких значениях параметра є методом параметризации. Управление параметризовалось кусочно-квадратичной функцией: на участке [гг_і,гг] управление представлялось квадратичной функцией уц + y t + Vizt2. В данных обозначениях TQ = 0. При є — 1 управление параметризовалось с одним моментом переключения и, Г2 = 1, а при є = 0.1 и є = 0.01 параметризовалось с тремя моментами переключения и, г4 = 1.
В методе параметризации решаются задачи Копій, следовательно требуется полная определенность начальных данных. В данном случае жг(0) не определено, однако метод параметризации позволяет решить эту проблему: задача нелинейного программирования увеличивается за счет введения недоопределенных начальных данных. Неопределенные начальные данные объявляются неизвестными параметрами, требующими оптимизации.
Таким образом, при є = 1 исходная функциональная задача сводится к конечномерной задаче нелинейного программирования, определяемой 8 переменными: параметрами управления Уц, г;12, У\з. 2ь v22, 235 моментом переключения управления т и недоопределен-ным начальным условием 2(0). Аналогично при є — 0.1 и є = 0.01
3.5. Сингулярные задачи дифференциальных уравнений исходная функциональная задача сводится к конечномерной задаче размерности 16.
Получаемые задачи нелинейного программирования решались в два этапа: на первом градиентным методом, на втором уточнялись методом Ньютона. Выбор этого способа определяется тем, что полученные конечномерные задачи в окрестности оптимального решения несут овражный характер, поэтому градиентные методы становятся практически неэффективны, и требуется метод, использующий условия второго порядка. Все задачи Коши для исходной системы, сопряженных систем и первых вариаций траектории решались методом Рунге-Кутты четвертого порядка с шагом интегрирования h.
Пусть норма функции \\х\\ определяется как \\х\\ = max #(). Обозначим . (), u(t) - решение, полученное вышеописанным алгоритмом, x{t) - решение из [32]. Приведем в таблице 4 соответствующие результаты.
Сингулярные задачи дифференциальных уравнений Для решения системы дифференциально-алгебраических уравнений с определенными только начальными данными оказалось удобно применять следующую схему. Исходный интервал [to;T] разбивался на несколько более мелких отрезков to t\ ... tk = Т. В силу того, что на оптимальной траектории J(y,Ti,T2) = 0 для любого [ті;т2] С [о; 1? то решение находилось последовательно на каждом интервале [ti-i; tj]. В качестве начальных данных на интервале [to] ti] брались начальные условия задачи ОУ, а на интервалах [г-_і;г-] конечные значения предыдущих интервалов [г-_2; г--і], г = 2,3, ...,&. Таким образом, на каждом интервале [г-_і;г-] решалась своя задача оптимального управления с функционалом J(y, г-_і, г-).
Рассмотрим решение на отрезке [0:0.5]. Отрезок [0;0.5] разбивался на 125 равных частей, т.е. к = 125. Каждая задача оптимального управления решалась методом параметризации в классе кусочно-линейных управлений с одним моментом переключения. Таким образом каждая функциональная задача переходила в пятимерную конечномерную задачу нелинейного программирования. Как показала практика, наиболее эффективным методом решения конечномерной задачи оказался метод Ньютона. Это обосновывается тем, что задача нелинейного программирования в окрестности оптимального решения имеет овражный характер. Использование градиентных методов на начальных итерациях излишне, поскольку в качестве начального приближения на каждом интервале выбирается решение, полученное на предыдущем интервале, и это решение практически всегда достаточно близко к оптимальному.