Содержание к диссертации
Введение
Глава 1 Математическое моделирование управляемых динамических систем, допускающих параметрическую линеаризацию 14
1.1. Постановка общей задачи оптимального управления. Условия оптимальности, использующие принцип максимума Понтрягина и формализм Дубовицкого-Мнлютина 15
1.2. Линейная задача оптимального управления со смешанными ограничениями, зависящими от времени. Условия оптимальности для линейных моделей с ограничениями смешанного типа, зависящими от времени 18
1.3. Постановка параметрической задачи оптимального управления. Сведение общей задачи оптимального управления к линейной параметрической задаче. Условия сводимости 20
1.4. Двухуровневая схема решения задачи оптимального управления, сводимой к линейной методом параметризации. Условия оптимальности для двухуровневой схемы 23
1.5. Использование принципа максимума в задачах оптимального управления, зависящих от параметров 30
Глава 2 Решение линейных задач оптимального управления с зависящими от времени смешанными ограничениями 32
2.1. Общая схема решения линейных задач оптимального управления 32
2.1.1. Получение дискретной аппроксимации решения прямой задачи 34
2.1.2. Построение гипотезы о геометрии оптимальных траекторий и ее верификация 35
2.2. Оценка погрешности метода дискретной аппроксимации линейных задач оптимального управления со смешанными ограничениями 37
2.3. Обоснование схемы "локального сгущения сетки дискретизации" 42
2.4. Оценка затрат вычислительных ресурсов необходимых па реализацию метода дискретной аппроксимации линейных задач 46
Глава 3 Применение методов параметрической линеаризации и дискретной аппроксимации для динамических моделей рынка ценных бумаг 50
3.1. Содержательное описание моделируемой системы 50
3.2. Математическая формулировка модели 51
3.3. Условия существования, единственности и оптимальности 56
3.4. Проблема тривиальности решения сопряженной задачи 61
3.5. Параметрическая линеаризация модели. Описание двухуровневой схемы поиска решения задач оптимального управления для рассматриваемой модели 63
Заключение Полученные результаты и возможные направления дальнейших исследований 69
Приложение
- Постановка общей задачи оптимального управления. Условия оптимальности, использующие принцип максимума Понтрягина и формализм Дубовицкого-Мнлютина
- Двухуровневая схема решения задачи оптимального управления, сводимой к линейной методом параметризации. Условия оптимальности для двухуровневой схемы
- Построение гипотезы о геометрии оптимальных траекторий и ее верификация
- Условия существования, единственности и оптимальности
Введение к работе
0.1. Общее описание проблемы
Данная работа посвящена исследованию эффективности и границ применимости схем решения нелинейных задач оптимального управления со смешанными ограничениями путем их параметрического редуцирования к линейным задачам. Данный подход, основанный на схеме линеаризации исходной задачи путем превращения части переменных в параметры с последующим поиском их значений, оказывается достаточно эффективным при решении различных классов задач. Характерным примером его использования может служить задача поиска собственных векторов линейных преобразований в конечномерных линейных пространствах.
С другой стороны, проблема нахождения решений для оптимизационных задач нелинейных моделей с ограничениями, в которые входят, вообще говоря, одновременно как фазовые, так и управляющие переменные, представляет значительный практический интерес, поскольку развитые к настоящему времени методы решения задач оптимального управления, либо основаны на использовании специфики их условий (например, отсутствии ограничений по фазовым переменным), либо требуют для своей реализации чрезмерно больших затрат вычислительных ресурсов. Так, например, разнообразные варианты методов прогонки в случае задач со смешанными ограничениями оказываются практически малоэффективными из-за сложности выполнения полного перебора вариантов схода с фазовых ограничений на континуальном временном множестве, необходимого для построения оптимальной фазовых траекторий.
Поэтому разработка альтернативных методик и алгоритмов, позволяющих избегать затруднений данной природы, являются актуальными, практически значимыми и полезными.
0.2. Формулировка темы работы. Актуальность
Основная цель работы состоит в анализе условий и границ применимости, равно как и оценке практической эффективности схем решения нелинейных задач оптимального управления с ограничениями общего вида, допускающих линеаризацию путем превращения некоторого подмножества управлений в параметры, с последующим поиском их оптимальных значений.
Как известно [7,8,14,22,35,37,50,66] основным методам решения задач оптимального управления с фазовыми и смешанными ограничениями являются: прямые методы (спуск в пространстве управлений), метод вариации фазовых переменных; метод штрафных функций; метод приращения функционала; принцип максимума.
В настоящее время теоретически наиболее точным и эффективным методом решения задач указанного класса является принцип максимума. Однако его практическое применение требует разрешения ряда проблем и преодоления затруднений, что требует накопления опыта решения конкретных задач оптимального управления.
Последнее обстоятельство обусловлено, с одной стороны сложностью математического аппарата и формулировки принципа максимума для задач оптимального управления с фазовыми и смешанными ограничениями. С другой стороны, хотя принцип максимума и редуцирует исходную задачу к краевой задаче для обыкновенных дифференциальных уравнений, наличие в таких задачах специфических связей типа равенств и неравенств резко усложняет использование этого подхода на практике.
Как правило, возникающая в этом случае краевая задача требует решения трех основных проблем:
задачи Коши для обыкновенных дифференциальных уравнений;
задачи нелинейного программирования (для каждой расчетной точки /);
поиск нулей трансцендентных функций.
Совокупность информации, получаемой при решении указанных выше задач, определяет для всего временного горизонта геометрию оптимальной траектории, основой которой является зависящее от t множество активных индексов для ограничений типа неравенств.
Важно отметить, что практическое использование принципа максимума также осложняется неединственностью множителей Лагранжа, возможным вырождением принципа максимума, а также проблемой выбора момента схода оптимальной траектории с ограничения типа неравенств. Еще одна проблема связана с нерегулярностью принципа максимума. Это приводит к появлению обобщенных функции в правой части сопряженных дифференциальных уравнений.
Из вышеизложенного следует, что разработка и обоснование комплекса вычислительных процедур и методик решения задач оптимального управления с
фазовыми и смешанными ограничениями на базе принципа максимума, является актуальной и важной для практики.
Как известно, принцип максимума для простейшей нелинейной задачи оптимального управления был сформулирован Понтрягиным Л.С. и обоснован Болтянским В.Г, [54,55]. С тех пор появилось значительное число работ, посвященных использованию принципа максимума в различных задачах оптимального управления [58,49,68]. Приведем краткое изложение основных, полученных в них результатов.
Наиболее глубокие и серьезные теоретические исследования проблемы были проведены в работах Милютина А.А. и Дубовицкого А.Я. [5,25,29,30,48]. В этих работах теория принципа максимума была распространена на широкий класс задач с фазовыми и смешанными ограничениями (в том числе и нерегулярными). По существу, теоретическая проблема получения необходимых условий первого порядка для указанных задач в этих работах полностью решена. Однако с практической точки зрения при решении задач Коши в схемах основанных на этих условиях возникают дополнительные проблемы, которые требуют применения специальных методов. Прежде всего это, так называемая, жесткость задачи Коши, являющаяся отражением того факта, что в рассматриваемом объекте протекают разнотемповые процессы. Выделение жестких систем уравнения в отдельный класс вызвано трудностями их численного интегрирования классическими явными методами. Оказалось, что малый шаг интегрирования, используемый для временных интервалов с большими по модулю производными, не может быть увеличен для других интервалов, хотя производные там становятся существенно меньше. Для устранения указанного ограничения были предложены различные методы [9,31,40,45,20,46,33,49], однако и в настоящее время проблема численного решения жестких систем остается актуальной. Это связано с увеличением классов решаемых задач, общностью их постановки и разнообразием численных методов.
Работы по созданию численных методов ведутся в двух направлениях. Первое направление связано с применением неявных схем (Ваннер Г., Хайрэр Э., Фсдоренко Р.П. и др.[59,63,68,61]). Другое направление связано с расширением границ применимости явных схем (Лебедев В.И., Шалашилип В.И,, Кузнецов Е.Б., Дикусар В.В. и др.[65,43,41,26,27]) Отметим также и скрытые формы проявления жесткости. Например, большой класс гладких оптимизационных конечномерных задач с трудом поддается решению традиционными методами первого и второго порядка из-за овражного рельефа поверхностей уровней. Исследования этого явления показали, что трудности связанные с жесткостью системы, описывающих траекторию наискорейшего спуска могут существенно осложнить применение принципа максимума [56,64,33].)
Для предварительной оценки определения геометрии оптимальной траектории
используют метод приращения функционала, а также дискретизацию исходной
непрерывной задачи, В результате получается задача нелинейного программирования
большой размерности. Важным частным случаем такой задачи является задача
линейного программирования (ЛП). Возможностям использования нелинейного и
линейного программирования для решения задач оптимального управления посвящено
значительное количество исследований, в числе которых
[4,13,14,16,17,21,23,34,38,42,51,53,57], содержащие полезные для практики результаты.
Евтушенко Ю.Г. и Жадан Ю.Д. [34,36] распространили идеи проектирования градиента и метода барьерных функций на общие задачи нелинейного
программирования. Несколько вариантов метода было реализовано программно и включено в библиотеку ДИСО. Следует отметить, что метод внутренней точки для задач ЛП [3] следует из работ Евтушенко Ю.Г. и Жадана Ю.Д. как частный случай, что подтверждается публикацией вышеупомянутых авторов в 1973 году. Отметим, что при решении задач оптимального управления методы дискретизации приводят к задачам ЛП большой размерности, которые как правило, плохо обусловлены. Для такого рода задач применяют специальные методы регуляризации (Бакушинский А.Б., Гончарский Л.В., Васильев Ф.П. и др.). В работах Мапгасарьяна и его сотрудников [2] основное внимание уделялось нахождению нормальных решений в задачах ЛП. Левиков А.А., Умпов А.Е. сводили задачу ЛП к задачам нелинейной параметрической [44,63]. Для задач квадратичного и линейного программирования применяются конечные и итеративные методы (Поляк Б.Т., Афанасьев А.П., Дикусар В.В., и др. [10,6]). Основные трудности решения указанных задач связаны с их плохой обусловленностью.
Отметим, что при решении ряда задач оптимального управления с фазовыми и смешанными ограничениями принцип максимума вырождается, т.е. становится тривиальным. Последнее означает, что для исследования задачи необходимо применять методы высших порядков [1,18,19,28,67]. Многие авторы рассматривали этот вопрос в плане расширения границ применимости принципа максимума в вырожденных задачах. Их результаты в основном связаны с теоремами существования принципа максимума для вырожденного случая. В их числе следует указать работу Дикусара В.В.[24], который применил методы регуляризации структуры ограничений, что позволило распространить принцип максимума на вырожденные задачи.
Наконец, представляется необходимым отметить наиболее интересные результаты использования принципа максимума для решения прикладных задач оптимального управления с фазовыми и смешанными ограничениями [15,32,39,52,60,62].
0.3. Цель работы и предлагаемый подход к решению
Настоящая диссертация является частью направления современных исследований в области развития эффективных методов численного решения задач оптимального управления с фазовыми и смешанными ограничениями. При этом основное внимание уделено анализу условий и границ применимости, оценке практической эффективности схем решения нелинейных задач оптимального управления с ограничениями общего вида, допускающих линеаризацию путем превращения некоторого подмножества управлений в параметры, с последующим поиском их оптимальных значений.
В соответствии с целью исследования поставлены следующие задачи:
выделение класса нелинейных задач, допускающих линеаризацию методом параметризации подмножества управляющих переменных, и исследование применимости условий оптимальности согласно принципу максимума Понтрягина и формализма Дубовицкого-Милютина;
формулирование условий линеаризации и условий оптимальности для линеаризованных задач;
построение двухуровневого алгоритма решения исходной нелинейной задачи оптимального управления и выявление области его эффективного применения ;
оценка эффективности метода решения линеаризованной задачи, не требующего выполнения полного перебора в процессе анализа геометрии оптимальной траектории;
сравнение и оценка эффективности методов уменьшения погрешности схемы дискретизации линейных задач со смешанными ограничениями;
разработка про грам много комплекса для ПЭВМ класса IBM PC, обеспечивающую практическую реализацию предлагаемой методики;
оценка работоспособности и эффективности двухуровневой схемы решения параметрически линеаризуемых задач оптимального управления на примере нелинейных динамических моделей рынка ценных бумаг.
Идея исследуемого подхода заключается в сведении нелинейной, но линеаризуемой параметрически, задачи оптимального управления к линейной параметрической задаче. При этом решение исходной задачи выполняется по двухуровневой схеме, на верхнем уровне которой решается неявно формулируемая задача на множестве функций-параметров, а на нижнем уровне решаются линейные задачи оптимального управления со смешанными ограничениями для последовательно изменяемых, но фиксированных функций-параметров.
Основные полученные результаты состоят в следующем.
Предложена и обоснована двухуровневая схема решения задач оптимального управления со смешанными ограничениями, допускающих сведение к линейной методом параметризации некоторого подмножества управляющих переменных. Определен класс задач, для которых использование данной схемы может быть эффективным.
Сформулирована и обоснована схема решения линеаризованных задач оптимального управления со смешанными ограничениями, основанная на комбинации метода дискретизации времени и аналитической проверки оптимальности как на основе формализма Поптрягина и Дубовицкого-Милютина, так и прямых методов,
Для предлагаемой схемы реализована, экономичная с точки зрения затрат вычислительных ресурсов, программная реализация для ПЭВМ класса IBM-PC,
Исследуемая методика использована для анализа нелинейной динамической модели рынка ценных бумаг. Для возникающих в процессе этого анализа задач оптимального управления получены условия существования, единственности и оптимальности решений. Для найденных решений приведена содержательная интерпретация.
0.4. Методы исследования
Принцип максимума Понтрягина, схема Дубовицкого-Милютина-Лагранжа, методы решения некорректных задач линейного программирования, методы продолжения решений' по параметру, итеративные методы решения задач нелинейного и линейного программирования.
0.5. Объем и структура диссертации
Диссертация содержит 104 страницы текста, включая рисунки. Текст разделен на введение, 3 главы, заключение, приложение и список литературы из 76 наименований.
0.6. Основное содержание работы
В первой главе диссертации рассматриваются теоретические аспекты проблем постановки и подходов к решению для класса задач оптимального управления со смешанными ограничениями, допускающих параметрическую линеаризацию.
В начале обсуждаются постановка обшей задачи оптимального управления, условия оптимальности, использующие принцип максимума Понтрягина и формализм Дуоовицкого-Милютина. Затем детально рассматривается линейная задача оптимального управления со смешанными ограничениями, зависящими от времени и приводятся условия оптимальности для линейных моделей с ограничениями смешанного типа, зависящими от времени.
Далее приводится постановка параметрической задачи оптимального управления и рассматриваются условия сведения общей задачи оптимального управления к линейной параметрической задаче. Дается описание и обоснование двухуровневой схемы решения задачи оптимального управления, сводимой к линейной методом параметризации. Рассматриваются условия оптимальности для двухуровневой схемы и итерационные методы ее решения.
Вторая глава диссертации посвящена описанию и обоснованию общей схемы решения линейных задач оптимального управления со смешанными ограничениями как основной процедуры двухуровневой схемы решения нелинейных задач.
Детально рассматриваются вопросы построения дискретной аппроксимации решения прямой задачи, формирования гипотезы о геометрии оптимальных траекторий и ее верификации, построения аппроксимации решения сопряженной задачи.
Далее рассматривается аналитическая схема проверки условий оптимальности. Находится оценка погрешности метода дискретной аппроксимации линейных задач оптимального управления со смешанными ограничениями. Приводится обоснование схемы повышения разрешающей способности метода дискретной аппроксимации и выполняется оценка затрат вычислительных ресурсов необходимых на реализацию метода дискретной аппроксимации.
В третьей главе рассматриваются вопросы практической реализации предлагаемого подхода на примере параметрической линеаризации и дискретной
аппроксимации для динамических моделей рынка ценных бумаг.
Приводится детальное содержательное описание моделируемой системы, математическая для случая параметрической линеаризации, а также обоснование двухуровневой схемы поиска решения задач оптимального управления для рассм атри ваемой модел и.
Заключение посвяшено анализу полученных результатов и возможных направлений дальнейших исследований
В приложениях к диссертационной работе приводятся результаты численных расчетов, необходимых как для получения дискретного приближения к решению задачи оптимального управления, так и для формирования геометрии оптимальных траекторий.
На завершающей стадии проводится анализ оптимальной геометрии и нахождение аналитического решения прямой и сопряженных задач, которое затем проверяется с помощью формализма Понтрягина и Дубовицкого-Милютина.
В приложения также включены детальные входные и выходные листинги для всех этапов решения задачи.
0.7. Научная новизна работы
Проведен всесторонний анализ методов решения нелинейных динамических задач со смешанными ограничениями, допускающих линеаризацию путем превращения в параметры некоторого подмножества управляющих переменных, базирующихся на двухуровневой оптимизационной схеме, сводящейся к последовательному решению линейных задач оптимального управления.
Для предложенной методики приведено обоснование сходимости, получены количественные оценки эффективности, выполнена программная реализация и проведена практическая апробация. Исследование и тестирование предложенных методов и алгоритмов выполнялось на базе модельных примеров и прикладных задач.
Практическая ценность работы определяется универсальностью рассмотренных алгоритмов для решения задач оптимального управления. Самостоятельный научный интерес представляют, полученные в процессе выполненного исследования, результаты анализа эффективности операций на рынках цепных бумаг.
0.8. Апробация работы
Результаты диссертации докладывались и обсуждались в Математическом институте имени В.А. Стеклова РАН, ВЦ РАН, на научном семинаре кафедры высшей Московского физико-технического института, состоявшемся 25 сентября 2003г., на "XLIII научной конференции МФТИ" (г. Долгопрудный МО,23-24 ноября 2000г). заседании кафедры высшей математики 27 августа 2004г., на заседании
расширенного научного семинара лабораторий Института проблем управления им. В.А.Трапезникова РАН 17 января 2005г.
0.9. Публикации
Основные результаты диссертации опубликованы в девяти работах автора [69-77], список которых приведен в разделе "Литература".
0.10. Личный вклад диссертанта
Все результаты, вынесенные автором на защиту, получены самостоятельно. Личный вклад диссертанта в публикациях, выполненных в соавторстве: в [73]-[76] теоретическое обоснование сходимости используемой схемы, построение математических моделей и содержательная интерпретация результатов, в [77] все результаты, кроме постановок основных задач,
Автор выражает искреннюю благодарность коллективу кафедры высшей математики Московского физико-технического института, ее заведующему и научному руководителю, члену-корреспонденту РАПН, Яковлеву Г.Н., за помощь, поддержку и постоянное внимание, оказанные в процессе данной работы.
Постановка общей задачи оптимального управления. Условия оптимальности, использующие принцип максимума Понтрягина и формализм Дубовицкого-Мнлютина
Как известно, принцип максимума для простейшей нелинейной задачи оптимального управления был сформулирован Понтрягиным Л.С. и обоснован Болтянским В.Г, [54,55]. С тех пор появилось значительное число работ, посвященных использованию принципа максимума в различных задачах оптимального управления [58,49,68]. Приведем краткое изложение основных, полученных в них результатов.
Наиболее глубокие и серьезные теоретические исследования проблемы были проведены в работах Милютина А.А. и Дубовицкого А.Я. [5,25,29,30,48]. В этих работах теория принципа максимума была распространена на широкий класс задач с фазовыми и смешанными ограничениями (в том числе и нерегулярными). По существу, теоретическая проблема получения необходимых условий первого порядка для указанных задач в этих работах полностью решена. Однако с практической точки зрения при решении задач Коши в схемах основанных на этих условиях возникают дополнительные проблемы, которые требуют применения специальных методов. Прежде всего это, так называемая, жесткость задачи Коши, являющаяся отражением того факта, что в рассматриваемом объекте протекают разнотемповые процессы. Выделение жестких систем уравнения в отдельный класс вызвано трудностями их численного интегрирования классическими явными методами. Оказалось, что малый шаг интегрирования, используемый для временных интервалов с большими по модулю производными, не может быть увеличен для других интервалов, хотя производные там становятся существенно меньше. Для устранения указанного ограничения были предложены различные методы [9,31,40,45,20,46,33,49], однако и в настоящее время проблема численного решения жестких систем остается актуальной. Это связано с увеличением классов решаемых задач, общностью их постановки и разнообразием численных методов.
Работы по созданию численных методов ведутся в двух направлениях. Первое направление связано с применением неявных схем (Ваннер Г., Хайрэр Э., Фсдоренко Р.П. и др.[59,63,68,61]). Другое направление связано с расширением границ применимости явных схем (Лебедев В.И., Шалашилип В.И,, Кузнецов Е.Б., Дикусар В.В. и др.[65,43,41,26,27]) Отметим также и скрытые формы проявления жесткости. Например, большой класс гладких оптимизационных конечномерных задач с трудом поддается решению традиционными методами первого и второго порядка из-за овражного рельефа поверхностей уровней. Исследования этого явления показали, что трудности связанные с жесткостью системы, описывающих траекторию наискорейшего спуска могут существенно осложнить применение принципа максимума [56,64,33].)
Для предварительной оценки определения геометрии оптимальной траектории используют метод приращения функционала, а также дискретизацию исходной непрерывной задачи, В результате получается задача нелинейного программирования большой размерности. Важным частным случаем такой задачи является задача линейного программирования (ЛП). Возможностям использования нелинейного и линейного программирования для решения задач оптимального управления посвящено значительное количество исследований, в числе которых [4,13,14,16,17,21,23,34,38,42,51,53,57], содержащие полезные для практики результаты. Евтушенко Ю.Г. и Жадан Ю.Д. [34,36] распространили идеи проектирования градиента и метода барьерных функций на общие задачи нелинейного программирования. Несколько вариантов метода было реализовано программно и включено в библиотеку ДИСО. Следует отметить, что метод внутренней точки для задач ЛП [3] следует из работ Евтушенко Ю.Г. и Жадана Ю.Д. как частный случай, что подтверждается публикацией вышеупомянутых авторов в 1973 году. Отметим, что при решении задач оптимального управления методы дискретизации приводят к задачам ЛП большой размерности, которые как правило, плохо обусловлены. Для такого рода задач применяют специальные методы регуляризации (Бакушинский А.Б., Гончарский Л.В., Васильев Ф.П. и др.). В работах Мапгасарьяна и его сотрудников [2] основное внимание уделялось нахождению нормальных решений в задачах ЛП. Левиков А.А., Умпов А.Е. сводили задачу ЛП к задачам нелинейной параметрической [44,63]. Для задач квадратичного и линейного программирования применяются конечные и итеративные методы (Поляк Б.Т., Афанасьев А.П., Дикусар В.В., и др. [10,6]). Основные трудности решения указанных задач связаны с их плохой обусловленностью.
Отметим, что при решении ряда задач оптимального управления с фазовыми и смешанными ограничениями принцип максимума вырождается, т.е. становится тривиальным. Последнее означает, что для исследования задачи необходимо применять методы высших порядков [1,18,19,28,67]. Многие авторы рассматривали этот вопрос в плане расширения границ применимости принципа максимума в вырожденных задачах. Их результаты в основном связаны с теоремами существования принципа максимума для вырожденного случая. В их числе следует указать работу Дикусара В.В.[24], который применил методы регуляризации структуры ограничений, что позволило распространить принцип максимума на вырожденные задачи.
Наконец, представляется необходимым отметить наиболее интересные результаты использования принципа максимума для решения прикладных задач оптимального управления с фазовыми и смешанными ограничениями [15,32,39,52,60,62].
Настоящая диссертация является частью направления современных исследований в области развития эффективных методов численного решения задач оптимального управления с фазовыми и смешанными ограничениями. При этом основное внимание уделено анализу условий и границ применимости, оценке практической эффективности схем решения нелинейных задач оптимального управления с ограничениями общего вида, допускающих линеаризацию путем превращения некоторого подмножества управлений в параметры, с последующим поиском их оптимальных значений.
Двухуровневая схема решения задачи оптимального управления, сводимой к линейной методом параметризации. Условия оптимальности для двухуровневой схемы
Данная работа посвящена исследованию эффективности и границ применимости схем решения нелинейных задач оптимального управления со смешанными ограничениями путем их параметрического редуцирования к линейным задачам. Данный подход, основанный на схеме линеаризации исходной задачи путем превращения части переменных в параметры с последующим поиском их значений, оказывается достаточно эффективным при решении различных классов задач. Характерным примером его использования может служить задача поиска собственных векторов линейных преобразований в конечномерных линейных пространствах.
С другой стороны, проблема нахождения решений для оптимизационных задач нелинейных моделей с ограничениями, в которые входят, вообще говоря, одновременно как фазовые, так и управляющие переменные, представляет значительный практический интерес, поскольку развитые к настоящему времени методы решения задач оптимального управления, либо основаны на использовании специфики их условий (например, отсутствии ограничений по фазовым переменным), либо требуют для своей реализации чрезмерно больших затрат вычислительных ресурсов. Так, например, разнообразные варианты методов прогонки в случае задач со смешанными ограничениями оказываются практически малоэффективными из-за сложности выполнения полного перебора вариантов схода с фазовых ограничений на континуальном временном множестве, необходимого для построения оптимальной фазовых траекторий.
Поэтому разработка альтернативных методик и алгоритмов, позволяющих избегать затруднений данной природы, являются актуальными, практически значимыми и полезными.
Основная цель работы состоит в анализе условий и границ применимости, равно как и оценке практической эффективности схем решения нелинейных задач оптимального управления с ограничениями общего вида, допускающих линеаризацию путем превращения некоторого подмножества управлений в параметры, с последующим поиском их оптимальных значений.
Как известно [7,8,14,22,35,37,50,66] основным методам решения задач оптимального управления с фазовыми и смешанными ограничениями являются: прямые методы (спуск в пространстве управлений), метод вариации фазовых переменных; метод штрафных функций; метод приращения функционала; принцип максимума.
В настоящее время теоретически наиболее точным и эффективным методом решения задач указанного класса является принцип максимума. Однако его практическое применение требует разрешения ряда проблем и преодоления затруднений, что требует накопления опыта решения конкретных задач оптимального управления.
Последнее обстоятельство обусловлено, с одной стороны сложностью математического аппарата и формулировки принципа максимума для задач оптимального управления с фазовыми и смешанными ограничениями. С другой стороны, хотя принцип максимума и редуцирует исходную задачу к краевой задаче для обыкновенных дифференциальных уравнений, наличие в таких задачах специфических связей типа равенств и неравенств резко усложняет использование этого подхода на практике.
Как правило, возникающая в этом случае краевая задача требует решения трех основных проблем: - задачи Коши для обыкновенных дифференциальных уравнений; - задачи нелинейного программирования (для каждой расчетной точки /); - поиск нулей трансцендентных функций. Совокупность информации, получаемой при решении указанных выше задач, определяет для всего временного горизонта геометрию оптимальной траектории, основой которой является зависящее от t множество активных индексов для ограничений типа неравенств. Важно отметить, что практическое использование принципа максимума также осложняется неединственностью множителей Лагранжа, возможным вырождением принципа максимума, а также проблемой выбора момента схода оптимальной траектории с ограничения типа неравенств. Еще одна проблема связана с нерегулярностью принципа максимума. Это приводит к появлению обобщенных функции в правой части сопряженных дифференциальных уравнений. Из вышеизложенного следует, что разработка и обоснование комплекса вычислительных процедур и методик решения задач оптимального управления с фазовыми и смешанными ограничениями на базе принципа максимума, является актуальной и важной для практики. Как известно, принцип максимума для простейшей нелинейной задачи оптимального управления был сформулирован Понтрягиным Л.С. и обоснован Болтянским В.Г, [54,55]. С тех пор появилось значительное число работ, посвященных использованию принципа максимума в различных задачах оптимального управления [58,49,68]. Приведем краткое изложение основных, полученных в них результатов.
Наиболее глубокие и серьезные теоретические исследования проблемы были проведены в работах Милютина А.А. и Дубовицкого А.Я. [5,25,29,30,48]. В этих работах теория принципа максимума была распространена на широкий класс задач с фазовыми и смешанными ограничениями (в том числе и нерегулярными). По существу, теоретическая проблема получения необходимых условий первого порядка для указанных задач в этих работах полностью решена. Однако с практической точки зрения при решении задач Коши в схемах основанных на этих условиях возникают дополнительные проблемы, которые требуют применения специальных методов. Прежде всего это, так называемая, жесткость задачи Коши, являющаяся отражением того факта, что в рассматриваемом объекте протекают разнотемповые процессы. Выделение жестких систем уравнения в отдельный класс вызвано трудностями их численного интегрирования классическими явными методами. Оказалось, что малый шаг интегрирования, используемый для временных интервалов с большими по модулю производными, не может быть увеличен для других интервалов, хотя производные там становятся существенно меньше. Для устранения указанного ограничения были предложены различные методы [9,31,40,45,20,46,33,49], однако и в настоящее время проблема численного решения жестких систем остается актуальной. Это связано с увеличением классов решаемых задач, общностью их постановки и разнообразием численных методов.
Построение гипотезы о геометрии оптимальных траекторий и ее верификация
Наиболее глубокие и серьезные теоретические исследования проблемы были проведены в работах Милютина А.А. и Дубовицкого А.Я. [5,25,29,30,48]. В этих работах теория принципа максимума была распространена на широкий класс задач с фазовыми и смешанными ограничениями (в том числе и нерегулярными). По существу, теоретическая проблема получения необходимых условий первого порядка для указанных задач в этих работах полностью решена. Однако с практической точки зрения при решении задач Коши в схемах основанных на этих условиях возникают дополнительные проблемы, которые требуют применения специальных методов. Прежде всего это, так называемая, жесткость задачи Коши, являющаяся отражением того факта, что в рассматриваемом объекте протекают разнотемповые процессы. Выделение жестких систем уравнения в отдельный класс вызвано трудностями их численного интегрирования классическими явными методами. Оказалось, что малый шаг интегрирования, используемый для временных интервалов с большими по модулю производными, не может быть увеличен для других интервалов, хотя производные там становятся существенно меньше. Для устранения указанного ограничения были предложены различные методы [9,31,40,45,20,46,33,49], однако и в настоящее время проблема численного решения жестких систем остается актуальной. Это связано с увеличением классов решаемых задач, общностью их постановки и разнообразием численных методов.
Работы по созданию численных методов ведутся в двух направлениях. Первое направление связано с применением неявных схем (Ваннер Г., Хайрэр Э., Фсдоренко Р.П. и др.[59,63,68,61]). Другое направление связано с расширением границ применимости явных схем (Лебедев В.И., Шалашилип В.И,, Кузнецов Е.Б., Дикусар В.В. и др.[65,43,41,26,27]) Отметим также и скрытые формы проявления жесткости. Например, большой класс гладких оптимизационных конечномерных задач с трудом поддается решению традиционными методами первого и второго порядка из-за овражного рельефа поверхностей уровней. Исследования этого явления показали, что трудности связанные с жесткостью системы, описывающих траекторию наискорейшего спуска могут существенно осложнить применение принципа максимума [56,64,33].)
Для предварительной оценки определения геометрии оптимальной траектории используют метод приращения функционала, а также дискретизацию исходной непрерывной задачи, В результате получается задача нелинейного программирования большой размерности. Важным частным случаем такой задачи является задача линейного программирования (ЛП). Возможностям использования нелинейного и линейного программирования для решения задач оптимального управления посвящено значительное количество исследований, в числе которых [4,13,14,16,17,21,23,34,38,42,51,53,57], содержащие полезные для практики результаты. Евтушенко Ю.Г. и Жадан Ю.Д. [34,36] распространили идеи проектирования градиента и метода барьерных функций на общие задачи нелинейного программирования. Несколько вариантов метода было реализовано программно и включено в библиотеку ДИСО. Следует отметить, что метод внутренней точки для задач ЛП [3] следует из работ Евтушенко Ю.Г. и Жадана Ю.Д. как частный случай, что подтверждается публикацией вышеупомянутых авторов в 1973 году. Отметим, что при решении задач оптимального управления методы дискретизации приводят к задачам ЛП большой размерности, которые как правило, плохо обусловлены. Для такого рода задач применяют специальные методы регуляризации (Бакушинский А.Б., Гончарский Л.В., Васильев Ф.П. и др.). В работах Мапгасарьяна и его сотрудников [2] основное внимание уделялось нахождению нормальных решений в задачах ЛП. Левиков А.А., Умпов А.Е. сводили задачу ЛП к задачам нелинейной параметрической [44,63]. Для задач квадратичного и линейного программирования применяются конечные и итеративные методы (Поляк Б.Т., Афанасьев А.П., Дикусар В.В., и др. [10,6]). Основные трудности решения указанных задач связаны с их плохой обусловленностью.
Отметим, что при решении ряда задач оптимального управления с фазовыми и смешанными ограничениями принцип максимума вырождается, т.е. становится тривиальным. Последнее означает, что для исследования задачи необходимо применять методы высших порядков [1,18,19,28,67]. Многие авторы рассматривали этот вопрос в плане расширения границ применимости принципа максимума в вырожденных задачах. Их результаты в основном связаны с теоремами существования принципа максимума для вырожденного случая. В их числе следует указать работу Дикусара В.В.[24], который применил методы регуляризации структуры ограничений, что позволило распространить принцип максимума на вырожденные задачи.
Наконец, представляется необходимым отметить наиболее интересные результаты использования принципа максимума для решения прикладных задач оптимального управления с фазовыми и смешанными ограничениями [15,32,39,52,60,62]. Настоящая диссертация является частью направления современных исследований в области развития эффективных методов численного решения задач оптимального управления с фазовыми и смешанными ограничениями. При этом основное внимание уделено анализу условий и границ применимости, оценке практической эффективности схем решения нелинейных задач оптимального управления с ограничениями общего вида, допускающих линеаризацию путем превращения некоторого подмножества управлений в параметры, с последующим поиском их оптимальных значений. В соответствии с целью исследования поставлены следующие задачи: выделение класса нелинейных задач, допускающих линеаризацию методом параметризации подмножества управляющих переменных, и исследование применимости условий оптимальности согласно принципу максимума Понтрягина и формализма Дубовицкого-Милютина; формулирование условий линеаризации и условий оптимальности для линеаризованных задач; построение двухуровневого алгоритма решения исходной нелинейной задачи оптимального управления и выявление области его эффективного применения ; оценка эффективности метода решения линеаризованной задачи, не требующего выполнения полного перебора в процессе анализа геометрии оптимальной траектории; сравнение и оценка эффективности методов уменьшения погрешности схемы дискретизации линейных задач со смешанными ограничениями; разработка про грам много комплекса для ПЭВМ класса IBM PC, обеспечивающую практическую реализацию предлагаемой методики; оценка работоспособности и эффективности двухуровневой схемы решения параметрически линеаризуемых задач оптимального управления на примере нелинейных динамических моделей рынка ценных бумаг. Идея исследуемого подхода заключается в сведении нелинейной, но линеаризуемой параметрически, задачи оптимального управления к линейной параметрической задаче. При этом решение исходной задачи выполняется по двухуровневой схеме, на верхнем уровне которой решается неявно формулируемая задача на множестве функций-параметров, а на нижнем уровне решаются линейные задачи оптимального управления со смешанными ограничениями для последовательно изменяемых, но фиксированных функций-параметров.
Условия существования, единственности и оптимальности
В первой главе диссертации рассматриваются теоретические аспекты проблем постановки и подходов к решению для класса задач оптимального управления со смешанными ограничениями, допускающих параметрическую линеаризацию.
В начале обсуждаются постановка обшей задачи оптимального управления, условия оптимальности, использующие принцип максимума Понтрягина и формализм Дуоовицкого-Милютина. Затем детально рассматривается линейная задача оптимального управления со смешанными ограничениями, зависящими от времени и приводятся условия оптимальности для линейных моделей с ограничениями смешанного типа, зависящими от времени.
Далее приводится постановка параметрической задачи оптимального управления и рассматриваются условия сведения общей задачи оптимального управления к линейной параметрической задаче. Дается описание и обоснование двухуровневой схемы решения задачи оптимального управления, сводимой к линейной методом параметризации. Рассматриваются условия оптимальности для двухуровневой схемы и итерационные методы ее решения.
Вторая глава диссертации посвящена описанию и обоснованию общей схемы решения линейных задач оптимального управления со смешанными ограничениями как основной процедуры двухуровневой схемы решения нелинейных задач.
Детально рассматриваются вопросы построения дискретной аппроксимации решения прямой задачи, формирования гипотезы о геометрии оптимальных траекторий и ее верификации, построения аппроксимации решения сопряженной задачи.
Далее рассматривается аналитическая схема проверки условий оптимальности. Находится оценка погрешности метода дискретной аппроксимации линейных задач оптимального управления со смешанными ограничениями. Приводится обоснование схемы повышения разрешающей способности метода дискретной аппроксимации и выполняется оценка затрат вычислительных ресурсов необходимых на реализацию метода дискретной аппроксимации.
В третьей главе рассматриваются вопросы практической реализации предлагаемого подхода на примере параметрической линеаризации и дискретной аппроксимации для динамических моделей рынка ценных бумаг. Приводится детальное содержательное описание моделируемой системы, математическая для случая параметрической линеаризации, а также обоснование двухуровневой схемы поиска решения задач оптимального управления для рассм атри ваемой модел и. Заключение посвяшено анализу полученных результатов и возможных направлений дальнейших исследований В приложениях к диссертационной работе приводятся результаты численных расчетов, необходимых как для получения дискретного приближения к решению задачи оптимального управления, так и для формирования геометрии оптимальных траекторий. На завершающей стадии проводится анализ оптимальной геометрии и нахождение аналитического решения прямой и сопряженных задач, которое затем проверяется с помощью формализма Понтрягина и Дубовицкого-Милютина. В приложения также включены детальные входные и выходные листинги для всех этапов решения задачи. Проведен всесторонний анализ методов решения нелинейных динамических задач со смешанными ограничениями, допускающих линеаризацию путем превращения в параметры некоторого подмножества управляющих переменных, базирующихся на двухуровневой оптимизационной схеме, сводящейся к последовательному решению линейных задач оптимального управления. Для предложенной методики приведено обоснование сходимости, получены количественные оценки эффективности, выполнена программная реализация и проведена практическая апробация. Исследование и тестирование предложенных методов и алгоритмов выполнялось на базе модельных примеров и прикладных задач. Практическая ценность работы определяется универсальностью рассмотренных алгоритмов для решения задач оптимального управления. Самостоятельный научный интерес представляют, полученные в процессе выполненного исследования, результаты анализа эффективности операций на рынках цепных бумаг. Результаты диссертации докладывались и обсуждались в Математическом институте имени В.А. Стеклова РАН, ВЦ РАН, на научном семинаре кафедры высшей Московского физико-технического института, состоявшемся 25 сентября 2003г., на "XLIII научной конференции МФТИ" (г. Долгопрудный МО,23-24 ноября 2000г). заседании кафедры высшей математики 27 августа 2004г., на заседании расширенного научного семинара лабораторий Института проблем управления им. В.А.Трапезникова РАН 17 января 2005г. Основные результаты диссертации опубликованы в девяти работах автора [69-77], список которых приведен в разделе "Литература". Все результаты, вынесенные автором на защиту, получены самостоятельно. Личный вклад диссертанта в публикациях, выполненных в соавторстве: в [73]-[76] теоретическое обоснование сходимости используемой схемы, построение математических моделей и содержательная интерпретация результатов, в [77] все результаты, кроме постановок основных задач, Автор выражает искреннюю благодарность коллективу кафедры высшей математики Московского физико-технического института, ее заведующему и научному руководителю, члену-корреспонденту РАПН, Яковлеву Г.Н., за помощь, поддержку и постоянное внимание, оказанные в процессе данной работы.
