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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В. ЛОМОНОСОВА

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

Камзолкин Дмитрий Владимирович

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

01.01.02 — Дифференциальные уравнения

АВТОРЕФЕРАТ

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

Москва - 2005

Работа выполнена на кафедре оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова

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

профессор Н.Л. Григоренко

Официальные оппоненты

доктор физико-математических наук, профессор А.П Крищенко

кандидат физико-математических наук, доцент И.А. Смольникова

Ведущая организация:

Институт математики и механики УрО РАН, г.Екатеринбург

Защита диссертации состоится "25" Мйр-гэ 2005 г. в 14.30 на заседании Диссертационного совета К 501.001.07 при Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, второй учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат диссертации разослан 2005 г.

В.М. Говоров

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Объектом исследования в первом классе задач управления являются динамические управляемые системы, описываемые на отрезке времени дифференциальным уравнением

где х е Д" - фазовая переменная, а управлеинвйРеснено геометрическим ограничением и € Р С Др Для системы (1) с начальным условием рассматривается ряд задач оптимального управления со свободным правым концом и функционалом типа Больца, а также задачи с фиксированным правым концом х(Т) = и функционалом типа Лагран-жа или быстродействия Подобные задачи часто возникают при исследовании математических моделей механики, экономики, биологии, фундаментальной медицины

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

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

К первой группе относятся методы основанные на решении краевой задачи принципа максимума Понтрягина1 (Г Л Гродзовский, Ю Н Иванов, В В Токарев, Н Н Моисеев, Д Брайсон, Хо Ю-ши, С Н Аввакумов, Ю Н Киселев, М В Орлов и др ), градиентные методы в пространстве управлений2

1 Понтрягин Л С , Болтянский В Г, Гамкрелидзе Р В , Мищенко Е Ф Математическая теория опти мальных процессов М Наука 1976

2 Васильев Ф П Методы оптимизации М Факториал пресс 2002

(Л И Шатровский, Т М Энеев, Н Н Моисеев, Р Копп, X Мойер, А В Бала-кришнан, Ф П Васильев и др ), метод последовательных приближений (И А Крылов, Ф Л Черноусько, Н В Баничук, X Келли, Р Копп, X Мойер и др), методы, связанные с варьированием и перебором траекторий в пространстве фазовых координат (Н Н Моисеев, В С Михалевич, Н 3 Шор, Ф Л Черно-усько, Р П Федоренко и др )

Ко второй группе относятся методы, основанные на получении уравнений Гамильтона-Якоби-Беллмана3, исследовании существования и единственности решения различных краевых задач для таких уравнений и построении разностных аппроксимаций для решения этих краевых задач

В случае выполнения гипотезы о дифференцируемости функции цены для непрерывной управляемой системы, такие методы были предложены Р Белл-маном, Н Н Моисеевым4 и др

С другой стороны исследования конкретных задач оптимального управления показывают (Л С Понтрягин, Е Ф Мищенко и др ) что функция цены, как правило, дифференцируема не всюду и потому не является классическим глобальным решением уравнения Гамильтона-Якоби-Беллмана Таким образом, в этом случае, как и во многих других, где используются уравнения в частных производных (УЧП) первого порядка, возникает необходимость вводить понятие обобщенного решения, а также развивать теорию и методы построения таких решений

Задачи, связанные с изучением негладких решений УЧП первого порядка, исследовались в работах Н С Бахвалова Л Эванса, У Флеминга, И М Гельфанда, С К Годунова, Э Хопфа, Н Н Кузнецова, О А Ладыженской, П Лакса О А Олейник, Б Л Рождественского, А А Самарского, А Н Тихонова А Б Куржанского, Н С Кружкова, А А Меликяна, М С Никольского и др В начале 80-х годов М Крэндалл и П Л Лионе ввели понятие вязкостного решения (viscosity solution) Теория вязкостных решений продвинула исследования УЧП первого порядка и эллиптических уравнений В рамках этой теории были доказаны теоремы существования и единственности для различных типов уравнений и краевых задач, а также изучены некоторые приложения к задачам управления и дифференциальным играм

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

3Б«пман Р Динамическое программирование М ИЛ 1960 4 Моисеев Н Н Элементы теории оптимальных систем М Наука 1975

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

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

В работах А М Тарасьева. А А Успенского и В Н Ушакова предложены конечно-разностные операторы для построения минимаксного решения уравнения Гамильтона-Якоби-Беллмана-Айзекса. Поскольку точное вычисление этих операторов является достаточно сложной задачей, авторами предложена их аппроксимация кусочно-линейными функциями с вершинами в узлах фиксированной сетки в фазовом пространстве7. Расчеты конкретных задач, проведенные по этому методу, показали его эффективность

В девяностых годах В. П. Масловым, В Н Колокольцовым и С Н Самбор-ским в работах, базирующихся на идемпотентном анализе, была предложена другая концепция обобщенного решения. Она основана на существенной модернизации классического подхода к определению обобщенного (слабого) решения в математической физике. С помощью этого подхода были развернуты исследования УЧП с выпуклым гамильтонианом и их приложений к задачам математической физики

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

Объектом исследования во втором классе задач управления являются динамические управляемые системы с неопределенными параметрами, описы-

5 Субботин А И Обобщенные решения уравнений в частных производных первох о порядка Перспективы динамической оптимизации Москва-Ижевск Институт компьютерных исследований 2003, Субботин А И Минимаксные неравенства и уравнения Гамильтона-Якоби М Наука 1991

eSubbotina N N The maximum principle and the superdifferential of the value function // Probl Control Inform Theon 1989 V 18, N 3 P151-160

7Тарасьев A M , Успенский А А , Ушаков В Н Аппроксимационные операторы и конечно-разностные схемы для построения обобщенных решений уравнений Гамильтона-Якоби // Известия РАН, Техн кибернетика 1994 N 3 С 173-185

ваемые на отрезке времени [0,Т] дифференциальным уравнением

x = f(x,u,v), (2)

где х € Я" - фазовая переменная, управление и стеснено геометрическим ограничением и € Р С RP, помеха v выбирается из множества Q с ff Для этой системы с начальным условием а:(0) = xq рассматривается задача наведения траектории системы (2) на терминальное множество М С Rn в момент времени Т в классе позиционных управлений

В работах Н Н Красовского и А И Субботина8 введены конструкции стабильных мостов и показано, что если построен максимальный w-стабильный мост W С [0,Т] х Rn в данной задаче то задача наведения имеет решение в классе позиционных процедур управления для любой начальной точки

Для линейной дифференциальной игры при помощи альтернированного интеграла Л С Понтрягина решение задачи построения множества W сводится к интегрированию многозначных отображений Исследованию этой задачи посвящены работы Е Ф Мищенко, А Б Куржанского, М С НикольСКОГо, Е С Половинкина, Н Л Григоренко, Н X Розова, В С Пацко, В И Максимова, А А Чикрий и др

В случае нелинейной управляемой системы для построения множества W используюхся операторные конструкции, исследованные в работах Н Н Кра-совского, А И Субботина, А Б Куржанского, Б Н Пшеничного В В Остапенко9 В Н Ушакова, Н Н Субботиной, А А Меликяна В общем случае вычисление этих операторов представляет собой сложную задачу Поэтому для практической реализации в вычислительных программах требуются дальнейшие аппроксимации этих операторов

В работах А М Тарасьева, В Н Ушакова и А П Хрипунова10 рассмат ривается аппроксимация операторов программного поглощения многогранниками, которые могут быть, вообще говоря, не выпуклыми Данный метод эффективен для решения дифференциальных игр на плоскости Но уже в трехмерном пространстве алгоритмы вычисления множеств, являющихся, например, пересечением не выпуклых многогранников сложны и с трудом поддаются программированию

Новым направлением в построении максимальных и-стабильных мостов являются сеточные методы В этих методах в фазовом пространстве задает

8Красовский Н Н Субботин А И Позиционные дифференциальные игры М Наука 1974 'Пшеничный Б Н Остапенко В В Дифференциальные игры Киев Наукова думка 1992 '"Tipauen \М Утаков ВН, Хрипунов KTL О построении множеств позиционного поглощения в игровых задачах управтения // Труды Инст матем механ УрО РАН 1992 Т 1 С 160-177

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

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

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

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

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

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

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

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

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

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

Методы исследования. В работе используется принцип максимума Понт-рягина, теория минимаксных решений для краевых задач уравнений Гамильтона - Якоби-Беллмана А И Субботина, теоремы о разрешимости нелинейных дифференциальных игр Н Н Красовского и А И Субботина

Апробация работы. Результаты работы были представлены в виде докладов на семинарах

1 Семинар кафедры оптимального управления факультета ВМиК МГУ (рук академик РАН Ю С Осипов, профессор М С Никольский)

2 Семинар "Математические модели в экономике и биологии", Планерное, Моск обл , 24 26 января 2003 г

3 Семинар "Математические модели в экономике и экологии" Химки, Моск обл , 27-29 января 2004 г

и на следующих конференциях

1 Международная конференция студентов и аспирантов по фундаментальным наукам "Ломоносов 2001", секция "Вычислительная математика и кибернетика" Москва, МГУ, 10-13 апреля 2001 г

2 Школа-семинар молодых ученых факультета ВМиК МГУ г Дубна, 2001

г

3 Конференция "Динамические управляемые процессы и приложения", Москва, кафедра Оптимального управления факультета Вычислительной математики и кибернетики МГУ, 24 апреля 2001 г

4 Научная школа-конференция "Мобильные роботы и мехатронные системы", Москва, Институт механики МГУ, 17-18 ноября 2003 г

Публикации Основные результаты диссертации опубликованы к работах

[1]-[5]

Структура и объем диссертации. Диссертация состоит из введения четырех глав и приложения Общий объем диссертации 116 страниц, включая 34 рис Библиография содержит 62 наименования

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

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

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

Ф(аг(Т|4о,х0>и( )))-»- и*

и()е<

на решениях системы (1) Функция цены ищется в заданной прямо-

угольной области [О, Т] х X С К х Л"

Известно, что при выполнении ряда условий, функция цены является обобщенным (в минимаксном или вязкостном смысле) решением задачи Коши для уравнения Гамильтона-Якоби-Беллмана

с краевым условием В случае, если функция является

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

Также используется ют факт11, что для уравнения Гамильтона-Якоби-Беллмана характеристики Коши совпадают с экстремалями и коэкстрема-лями принципа максимума Понтрягина Получаем представление значения функции цены как минимума целевой функции Ф(ж(Т)) на всех допустимых нарах (£(•),«( )), удовлетворяющих принципу максимума Это представление является основой для разработки конструктивного метода аппроксимации функции цены При этом при практическом применении описанного способа вычисления функции цены для построении соответствующих экстремалей принципа максимума требуется однозначное определение управления

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

11 Субботина Н Н Унифицированные условия оптимальности в задачах управления // Труды Института математики и механики УрО РАН Екатеринбург ИММ УрО РАН 1992 Т 1 С 147 159

некоторой вспомогательной задачи Коши для гамильтоновой системы

проходящих через точку

Таким образом лемма 1.4 по сути позволяет исходную задачу оптимального управления, являющуюся бесконечномерной задачей минимизации, свести к задаче конечномерной минимизации на некотором компактном множестве К С Я". Множество К в данном случае является произвольной внешней аппроксимацией множества достижимости системы (1) из любой начальной точки (¿о,£о) £[0,Т]хХ.

Далее на основе леммы 1.4 предлагается следующая аппроксимационная схема для приближенного вычисления функции цены.

На множестве [0, Т]хХ задается равномерная сетка. Временной интервал разбивается на одинаковых частей точками

Т I '

О = 70 < Г! < • • • < Т1 = Т, Т,+ 1

Т,

Каждый из отрезков [а;, ,а;1+],г = 1,...,п, определяющих множество X, разбивается на т одинаковых частей точками

= а < я < • • • < 0п = , Он - а = —

ТП

Получаем на множестве [0,Г]х! равномерную сетку с узлами в точках Эта сетка разбивает множество [О, Т] х X на прямоугольные ячейки

Множество всех ячеек обозначим через

О- = {?ЛЛ, „ьЬ'о = 1, = 1,... ,т; » = 1,... ,п}.

Аналогично множеству X задается равномерная сетка на прямоугольном множестве К Узлами сетки будут точки г)3и Л = (г^,... ,77" ).

Множество всех узлов этой сетки обозначим через

Для приближенного решения задачи Коши (3) в обратном времени предлагается использовать произвольный конечно-разностный метод с постоянным шагом (при вычислении оценки погрешности аппроксимации рассматривался метод Эйлера).

Для каждой ячейки q определяется множество М{д) С Л/", представляющее собой множество всех точек г? £ «V, для которых приближенное решение задачи Коши (3) с конечным условием х(Т) = г} проходит через ячейку q

Если множество не пусто, то минимальное значение функционала на

этом множестве обозначается как

Аппроксимация функции цены определяется как кусочно-постоянная функция, принимающая постоянное значение в каждой ячейке q а Q, равное И^д)

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

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

тором в формуле (4) достигается минимум. В дальнейшем гарантирующее управление вычисляется по формуле и(Ь) = и*{х{Ь), ф^)). где ~

решение задачи Коши (3) с краевым условием В теореме 1 2

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

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

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

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

В разделе 1.2 рассматривается задача оптимального управления с функционалом типа Больца. состоящим из терминальной и интегральной частей

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

В теореме 1 4 приводятся достаточные условия сходимости метода и оценка погрешности аппроксимации.

В разделе 1 2 4 на основе метода вычисления функции цены в задаче оптимальною управления с функционалом типа Больца предлагается гладкая аппроксимация для задачи оптимального управления с терминальным функционалом в случае линейной по управлению системы вида

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

где а 6 параметр В лемме 1 14 доказывается равномерная сходимость

в области [0, Т]к X функции цены вспомогательной задачи к исходной при стремлении параметра а к нулю

Данная аппроксимационная задача обладает свойством единственности и липшицевости максимизатора и*(х,ф), что позволяет существенно расширить круг решаемых задач оптимального управления с терминальным функционалом В теореме 1 6 доказывается сходимость метода вычисления функции цены для аппроксимационной задачи

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

и фиксированным правым концом х(Т) = Х\ Конечный момент времени Т тоже считается заданным

Задача с фиксированным правым концом имеет ряд существенных отличий от ранее рассматриваемых задач Так для некоторых начальных точек может не иметь решения даже задача управляемости, поэтому на задачу накладывается условие управляемости из каждой начальной точки А' и функция цены ищется только для момента времени ¿о = 0 Кроме тою при гех же условиях гладкости, что и для задач со свободным правым концом, функция цены не всегда обладает свойством липшицевости

Для этой задачи оптимального управления предлагается аналог метода аппроксимации функции цены для задачи со свободным правым концом, позво-значение функции цены в виде минимума функционала на экстремалях принципа максимума Понтрягина В теореме 1 7 доказывается сходимость метода при условии липшицевости функции цены

Также в этом разделе приводится пример задачи оптимального управле-чия, удовлетворяющей всем требованиям теоремы 1 7 кроме липшицевости функции цены, функция цены в которой имеет разрывную производную

В следующем разделе 1 4 рассматривается еще одна постановка задачи оптимального управления с фиксированным правым концом, а именно задача быстродействия Считается, что конечный момент времени заранее не известен В качестве минимизируемого функционала рассматривается время Т перевода системы (1) из начального положения х(0) = хо в конечное

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

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

В главе 2 приводятся примеры вычисления функции цены для ряда конкретных задач оптимального управления В разделе 2 1 рассматриваются задачи оптимального управления, для которых известно аналитическое выражение для функции цены Результаты применения указанных методов аппроксимации функции цены иллюстрируют хорошую точность получаемого решения

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

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

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

мент времени Т Сначала рассматривается случай отсутствия фазовых ограничений

Известно, что если построен максимальный и-стабильный мост IV в данной задаче, то задача наведения имеет решение в классе позиционных про цедур управления для любой начальной точки

Для построения максимальных стабильных мостов применяются попятные процедуры, использующие на каждом шаге некоторые операторы программного поглощения и их конечно-разностные аппроксимации Эти процедуры дают достаточно точную аппроксимацию при выполнении некоторых условий невырожденности В данной работе рассматриваются операторные конструкции предложенные Б Н Пшеничным и В В Остапенко12 В этих конструкциях для построения множества позиционного поглощения точное решение дифференциального уравнения (2) заменяется конечно-разностной схемой Временной интервал [0,Т] разбивается на N одинаковых частей точ-

12Пшеничный Б Н Остапенко В В Дифференциальные игры Киев Наукова думка 1992 С 42 73, 132 200

ками

Т

О = ¿0 < < • • ■ < — Т, — = — = Л.

Вводится оператор ЩЛ, ставящий в соответствие любому компактному множеству Ас. Я.п множество

Используя оператор Щ-А, задается рекуррентная последовательность множеств

Считаем множества Щ аппроксимацией точных множеств , являющих-

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

Будем обозначать 5а = {г £ й" : ||:г|| < а} - шар радиуса а с центром в нуле. Также для произвольного компактного множества А СЙ"и некоторой константы обозначим

некоторая непрерывная функция,

Компактное множество Л С Я" удовлетворяет условию телесности с положительными константами а,ш,г и функцией 1а<А, если для любого х €

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

Выберем некоторые малые величины Д > 0 и 5 > 0. На множестве Р зададим конечное множество точек такое, что для любого

и £ Р найдется иг £ Рг, для которого ||и — ы,|| < 6. Аналогично определим множество Qs = {г^ 6 Q}.

В пространстве зададим равномерную сетку с узлами в точках

■■■ <Ь'_1<Ь'0 = 0<Ь\< .г ., Ь3+1 - Ь, = з - -оо,..., с», г — 1,. ., п. Множество всех точек обозначим через

Вд = {Ь,ь ,,„ : г3 = -оо,..., оо, з = 1,..., п}.

Для каждой точки

сд(6) = {х в Д" : К - < г = 1,..., п}.

Будем называть множество

Для произвольного компактного множества определим множество

Вд(Л) с Вд-

Вл(А) = {6 е Вд : сд(Ь) П А Ф 0}.

Далее для произвольного множества зададим множество

Х(В) = У сд(Ь). ьев

Для произвольного ограниченного множества определим отображение

= {ЪеВ&: Рн(Ъ,и,у) € *(В) + 5д}.

С использованием отображения для произвольного ограниченного множества В С .Вд определим оператор

ПЛ,ДВ = р| иI ^¿(В,«,,«,).

Также для множества В С .Вд определим аналог сг-окрестности множества, где а > 0 - произвольная величина

ВЦВ) = {6 е Вд : сд(6) П Х(В) + Ба ф 0}

Далее зададим рекуррентную последовательность множеств Щ - Вд(М),

Ш1+1 = ВЦП^Щ, г — 0, ■ ■ ■, N — 1, 16

где а > 0 некоторый параметр

В диссертации исследуется сходимость множеств Х(\¥1) к искомым множествам

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

В теореме 3.1 доказывается сходимость предложенного метода аппроксимации максимальных мостов и приводятся условия согласования параметров при которых эта сходимость имеет место.

В разделе 3.4 рассматриваются дифференциальные игры с фазовыми ограничениями, задаваемыми компактным множеством N С Яп Определяется рекуррентная последовательность множеств для игр с фазовыми ограничениями.

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

В главе 4 приводятся примеры приближенного построения максимальных и-стабильных мостов для конкретных дифференциальных игр В частности приводится пример дифференциальной игры, для которой имеется точное аналитическое решение Сравнение приближенного и точного решений свидетельствует о хорошей точности предложенного в работе метода

В приложении содержится описание программной реализации метода аппроксимации максимальных мостов в дифференциальных играх

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Камзолкин Д.В. Численный метод решения одного класса нелинейных дифференциальных игр // Мобильные роботы и мехатронные системы: Материалы научной школы-конференции. М.: Изд-во Моск. ун-та. 2004. С 253-263.

[2] Камзолкин Д.В. Метод нахождения функции Беллмана для задачи оптимального управления с терминальным функционалом // Математические модели в экономике и экологии: Материалы научного семинара. М.: МАКС Пресс. 2004. С. 44-48.

[3] Камзолкин Д.В. Аппроксимация множеств позиционного поглощения для нелинейных дифференциальных игр // Математические модели в экономике и биологии: Материалы научного семинара. М.: МАКС Пресс. 2003. С. 49-53.

[4] Камзолкин Д.В. Численный метод приближенного вычисления функции цены для задачи оптимального управления с терминальным функционалом // Вычислительные методы и программирование. М.: Изд-во Моск. ун-та. 2004. Т. 5. N 2. С. 121-132.

[5] Камзолкин Д.В. О построении максимальных стабильных мостов для одного класса нелинейных дифференциальных игр с фазовыми ограничениями // Факультет вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова. Москва, 2004, деп. в ВИНИТИ 29.11.04, N 1872-В2004, 14 С.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от01.12.99 г. Подписано к печати 18.02.200S г. Формат 60x90 1/16. Усл.печл. 1,25. Тираж 100 экз. Заказ 071. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

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

1.1 Задача оптимального управления с терминальным функционалом.

1.1.1 Постановка задачи.

1.1.2 Функция цены и обобщенное решение уравнения Гамильтона-Якоби-Беллмана.

1.1.3 Представление значения функции цены с помощью экстремалей принципа максимума Понтрягина.

1.1.4 Исследование решения вспомогательной задачи Коши.

1.1.5 Метод приближенного вычисления функции цены.

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

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

1.2 Задача оптимального управления с функционалом типа Больца.

1.2.1 Постановка задачи.

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

1.2.3 Модифицированный алгоритм. Приближенное решение задачи оптимального управления с функционалом типа Больца.

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

1.3 Задача оптимального управления с фиксированным правым концом.

1.3.1 Постановка задачи.

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

1.3.3 Метод приближенного вычисления функции цены для задачи оптимального управления с фиксированным правым концом.

1.4 Задача быстродействия.

1.4.1 Постановка задачи.

1.4.2 Представление значения функции цены для задачи быстродействия на основе экстремалей принципа максимума Понтрягина.

1.4.3 Метод приближенного вычисления функции цены для задачи быстродействия

1.4.4 Достаточные условия непрерывности функции цены в задаче быст

• родействия.

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

2.1 Расчет тестовых примеров.

2.1.1 Линейно-квадратичная задача.

2.1.2 Задача быстродействия для модели "тележка".

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

2.2.1 Модель "РОСТ".

2.2.2 Модель "хищник-жертва".

2.2.3 Модель физического маятника.

2.2.4 Задача наискорейшего пространственного разворота твердого тела

3 О построении максимальных и-стабильных мостов для одного класса нелинейных дифференциальных игр сближения

3.1 Постановка задачи.

3.2 Дискретная по времени схема приближенного построения максимальных и-стабильных мостов.

3.3 Дискретная по времени, фазовым координатам и множествам управления схема приближенного построения максимальных и -стабильных мостов

3.4 Дифференциальные игры с фазовыми ограничениями.

4 Приближенное построение максимальных и-стабильных мостов для кон

1 кретных дифференциальных игр

4.1 Модельный пример.

4.2 Модель физического маятника.

4.3 Модель "хищник - жертва".

4.4 Пример с фазовыми ограничениями.

4.5 Модель трехколесной тележки на плоскости.

А Описание программной реализации метода приближенного построения максимальных «-стабильных мостов

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

Объектом исследования в первом классе задач управления являются динамические управляемые системы, описываемые на отрезке времени [ioj^] дифференциальным уравнением x = f(x,u), (1) где х € Rn - фазовая переменная, а управление и £ Rp стеснено геометрическим ограничением и € Р С ЯР. Для системы (1) с начальным условием x(t0) = хо рассматривается ряд задач оптимального управления со свободным правым концом и функционалом типа Больца, а также задачи с фиксированным правым концом х(Т) = Х\ и функционалом типа Лагранжа или быстродействия. Подобные задачи часто возникают при исследовании математических моделей механики, экономики, биологии, фундаментальной медицины.

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

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

К первой группе относятся методы, основанные на решении краевой задачи принципа максимума Понтрягина [33, 25] (Г.Л. Гродзовский, Ю.Н. Иванов, В.В. Токарев, H.H. Моисеев, Д. Брайсон, Хо Ю-ши, С.Н. Аввакумов, Ю.Н. Киселев, М.В. Орлов и др.), градиентные методы в пространстве управлений [11] (Л.И. Шатровский, Т.М. Энеев, H.H. Моисеев, Р. Копп, X. Мойер, A.B. Балакришнан, Ф.П. Васильев и др.), метод последовательных приближений [55] (И.А. Крылов, Ф.Л. Черноусько, Н.В. Баничук, X. Келли, Р. Копп, X. Мойер и др.), методы, связанные с варьированием и перебором траекторий в пространстве фазовых координат [26] (H.H. Моисеев, B.C. Михалевич, Н.З. Шор, Ф.Л. Черноусько, Р.П. Федоренко и др.).

Ко второй группе относятся методы, основанные на получении уравнений Гамильтона-Якоби-Беллмана [8, 40], исследовании существования и единственности решения различных краевых задач для таких уравнений и построении разностных аппроксимаций для решения этих краевых задач.

В случае выполнения гипотезы о дифференцируемости функции цены для непрерывной управляемой системы, такие методы были предложены Р. Беллманом, H.H. Моисеевым [55, 25, 26] и др.

С другой стороны исследования конкретных задач оптимального управления показывают (Л.С.Понтрягин [33], Е.Ф.Мищенко и др.), что функция цены, как правило, дифференцируема не всюду и потому не является классическим глобальным решением уравнения Гамильтона-Якоби-Веллмана. Таким образом, в этом случае, как и во многих других, где используются уравнения в частных производных (УЧП) первого порядка, возникает необходимость вводить понятие обобщенного решения, а также развивать теорию и методы построения таких решений.

Задачи, связанные с изучением негладких решений УЧП первого порядка, исследовались в работах Н.С. Бахвалова, J1. Эванса, У. Флеминга, И.М. Гельфанда, С.К. Годунова, Э. Хопфа, H.H. Кузнецова, O.A. Ладыженской, П. Лакса, O.A. Олейник, Б.Л. Рождественского, A.A. Самарского, А.Н.Тихонова, А.Б. Куржанского, Н.С. Кружкова, A.A. Меликя-на, М.С. Никольского и др.

В начале 80-х годов М. Крэндалл и П.Л. Лионе ввели понятие вязкостного решения (viscosity solution [56]). Теория вязкостных решений продвинула исследования УЧП первого порядка и эллиптических уравнений. В рамках этой теории были доказаны теоремы существования и единственности для различных типов уравнений и краевых задач, а также изучены некоторые приложения к задачам управления и дифференциальным играм.

В конце семидесятых годов А.И Субботиным был предложен другой подход к построению обобщенных решений, который может быть рассмотрен, как неклассический метод характеристик. Следуя этому подходу, обобщенное решение (называемое минимаксным) должно быть инвариантно относительно потока, порождаемого так называемыми характеристическими дифференциальными включениями. Теория минимаксных решений изложена в работах А.И. Субботина [40, 41, 42]. В них получены теоремы существования и единственности таких решений, поставлены задачи численной аппроксимации минимаксных решений и решения на их основе задач оптимального управления и дифференциальных игр.

Развитие теории минимаксных решений, в том числе метода характеристик, для задач оптимального управления, предложено в работах H.H. Субботиной [44, 45, 46, 47, 57], в которых получено условие первого порядка, дополняющее принцип максимума Понтрягина до необходимых и достаточных условий оптимальности.

В работах A.M. Тарасьева, A.A. Успенского и В.Н. Ушакова предложены конечно-разностные операторы для построения минимаксного решения уравнения Гамильтона-Якоби-Беллмана-Айзекса. Поскольку точное вычисление этих операторов является достаточно сложной задачей, авторами предложена их аппроксимация кусочно-линейными функциями с вершинами в узлах фиксированной сетки в фазовом пространстве [48]. Расчеты конкретных задач, проведенные по этому методу, показали его эффективность.

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

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

Объектом исследования во втором классе задач управления являются динамические управляемые системы с неопределенными параметрами, описываемые на отрезке времени

О, Т] дифференциальным уравнением х = f(x,u,v), (2) где х € Rn - фазовая переменная, управление и стеснено геометрическим ограничением и € Р С RP, помеха v выбирается из множества Q С Rq. Для этой системы с начальным условием ж(0) = х0 рассматривается задача наведения траектории системы (2) на терминальное множество М С Rn в момент времени Т в классе позиционных управлений.

В работах H.H. Красовского и А.И. Субботина [20, 21, 43] введены конструкции стабильных мостов и показано, что если построен максимальный «-стабильный мост W С [0,Т] х Rn в данной задаче, то задача наведения имеет решение в классе позиционных процедур управления для любой начальной точки (£о,£о) £ W.

Для линейной дифференциальной игры при помощи альтернированного интеграла JI.C. Понтрягина [37, 34] решение задачи построения множества W сводится к интегрированию многозначных отображений. Исследованию этой задачи посвящены работы Е.Ф. Мищенко, A.B. Куржанского, М.С. Никольского, Е.С. Половинкина, H.JI. Григоренко, Н.Х. Розова, B.C. Пацко, В.И. Максимова, A.A. Чикрий и др.

В случае нелинейной управляемой системы для построения множества W используются операторные конструкции, исследованные в работах H.H. Красовского, А.И. Субботина, A.B. Куржанского, Б.Н. Пшеничного, В.В. Остапенко, В.Н. Ушакова, H.H. Субботиной, A.A. Меликяна [20, 38, 52]. В общем случае вычисление этих операторов представляет собой сложную задачу. Поэтому для практической реализации в вычислительных программах требуются дальнейшие аппроксимации этих операторов.

В работах A.M. Тарасьева, В.Н. Ушакова и А.П. Хрипунова [49, 50, 54] рассматривается аппроксимация операторов программного поглощения многогранниками, которые могут быть, вообще говоря, не выпуклыми. Данный метод эффективен для решения дифференциальных игр на плоскости. Но уже в трехмерном пространстве алгоритмы вычисления множеств, являющихся, например, пересечением не выпуклых многогранников, сложны и с трудом поддаются программированию.

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

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

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

Ф(я(Г|*о,яо,и(0))->> inf и[-)еи на решениях системы (1). Функция цены V(t,x) ищется в заданной прямоугольной области [О,Г] х X С R х Rn.

Известно, что при выполнении ряда условий, функция цены является обобщенным (в минимаксном или вязкостном смысле) решением задачи Коши для уравнения Гамильтона-Якоби-Беллмана dV(t,x) . / аУ(*,д:)\ . + min ( f(x, и), —£-) = О дЬ иеР V дх с краевым условием У(Т,х) = Ф(х). В случае, если функция У^,х) является гладкой, для решения этой задачи применим классический метод характеристик, позволяющий свести решение задачи Коши для уравнения в частных производных к интегрированию системы обыкновенных дифференциальных уравнений, называемой характеристической. В общем случае функция цены может не являться гладкой, и для ее вычисления рассматривается обобщение метода характеристик, заключающееся в применении операции минимума при вычислении функции цены в точке (¿о,хо) в случае, если существует более одной характеристики, компонента х которых пересекает в момент ¿о точку хо.

Также используется тот факт [47], что для уравнения Гамильтона-Якоби-Беллмана характеристики Коши совпадают с экстремалями и коэкстремалями принципа максимума Понтрягина. Получаем представление значения функции цены как минимума целевой функции Ф(х(Т)) на всех допустимых парах (х(-),и(-)), удовлетворяющих принципу максимума. Это представление является основой для разработки конструктивного метода аппроксимации функции цены. При этом при практическом применении описанного способа вычисления функции цены для построении соответствующих экстремалей принципа максимума требуется однозначное определение управления и*(х,ф), максимизирующего функцию Гамильтона-Понтрягина Н(х, и, ф). Кроме того необходимо исключить случай вырожденности принципа максимума, когда ему удовлетворяют все допустимые управления. В лемме 1.4 приводятся достаточные условия, при которых значение функции цены в точке (¿(ь^о) можно представить как минимум целевой функции на всех решениях некоторой вспомогательной задачи Коши для гамильтоновой системы х = f(x, и*{х, ф)) = F(x, ф), ф = - дНф = в(х,ф)ф, Y дх и=и'(х,ф) V «=«'<*W х{т) = хт,

Ф(Т) =

3) проходящих через точку (^,х0).

Таким образом лемма 1.4 по сути позволяет исходную задачу оптимального управления, являющуюся бесконечномерной задачей минимизации, свести к задаче конечномерной минимизации на некотором компактном множестве К С Яп. Множество К в данном случае является произвольной внешней аппроксимацией множества достижимости системы (1) из любой начальной точки £ [0)^1 х X.

Далее на основе леммы 1.4 предлагается следующая аппроксимационная схема для приближенного вычисления функции цены.

На множестве [0, Т] х X задается равномерная сетка. Временной интервал [0, Т] разбивается на I одинаковых частей точками т*: Т

Каждый из отрезков [ж,- = 1 ,.,п, определяющих множество X, разбивается на т одинаковых частей точками хг = £о < < • ' ' < Ст = &+1 ~ Ск ~ 1 1 • Получаем на множестве [О, Т] х X равномерную сетку с узлами в точках о^.^'--•>£"„)> -7° = О»---.*; Л = 0,.,т; г = 1,.,п. Эта сетка разбивает множество [О, Т] х X на прямоугольные ячейки

Я]~ [тзо-1> тдо\ Х Х ••• X [^,-1'^.]'

Эо = 1,., I; К = 1,.,га; г - 1,. . ,п.

Множество всех ячеек Я^,^,.,^ обозначим через

2 = Ь'о = 1, • • •,Л = 1, • • •, т; « = 1,., п}.

Аналогично множеству X задается равномерная сетка на прямоугольном множестве К. Узлами сетки будут точки — (л}^- ■ •, ?7"п):

7?г1 < ^ < = Я-р г)Ъ+1-г)1 = ™, г = 1,., п.

Множество всех узлов этой сетки обозначим через {^ь.-^пЬ'г = 1. • • •»к] г = 1,., п}.

Для приближенного решения задачи Коши (3) в обратном времени предлагается использовать произвольный конечно-разностный метод с постоянным шагом у (при вычислении оценки погрешности аппроксимации рассматривался метод Эйлера).

Для каждой ячейки д определяется множество Л/\д) С Л/*, представляющее собой множество всех точек г) € Л/", для которых приближенное решение задачи Коши (3) с конечным условием х(Т) = т) проходит через ячейку д.

Если множество .Л/(д) не пусто, то минимальное значение функционала на этом множестве обозначается как д)= тш Ф(и). (4) чел(д)

Аппроксимация функции цены определяется как кусочно-постоянная функция, принимающая постоянное значение в каждой ячейке <7 € (2, равное д.

В теореме 1.1 приводятся достаточные условия для равномерной сходимости предложенной аппроксимационной схемы, состоящие из условий, налагаемых на исходную задачу оптимального управления, и условий согласования параметров т, I, к и е. Также в теореме приводится оценка погрешности аппроксимации, имеющая порядок О + О (у).

Далее в том же разделе исследуется возможность применения данного метода для вычисления некоторого программного управления, решающего поставленную задачу оптимального управления приближенно, то есть гарантирующего значение целевой функции близкое к оптимальному. Для этого требуется для каждой ячейки я запоминать то значение 77(9), на котором в формуле (4) достигается минимум. В дальнейшем гарантирующее управление вычисляется по формуле и(£) = и*{х{Ь),ф{£)), где ф^)) - решение задачи Коши (3) с краевым условием х(Т) = В теореме 1.2 доказывается сходимость гарантированного результата к оптимальному.

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

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

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

В разделе 1.2 рассматривается задача оптимального управления с функционалом типа Больца, состоящим из терминальной и интегральной частей: г

1(ь0,х0,и(')) = / /0{х(Цг0,х0,и(')),и(г))(И + Ф(х(Т\г0,х0,и(-)))ы . о

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

В теореме 1.4 приводятся достаточные условия сходимости метода и оценка погрешности аппроксимации.

В разделе 1.2.4 на основе метода вычисления функции цены в задаче оптимального управления с функционалом типа Больца предлагается гладкая аппроксимация для задачи оптимального управления с терминальным функционалом в случае линейной по управлению системы вида = Мх) +/2(х)и.

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

1а(к,х0,и{-)) = а [ \\и{Щ2сН + Ф(х{Т\Ьо,Хо,и{-)))Ы , J и(-)€(/ где о; € Д+ - параметр. В лемме 1.14 доказывается равномерная сходимость в области [О, Т] х X функции цены вспомогательной задачи к исходной при стремлении параметра а к нулю.

Данная аппроксимационная задача обладает свойством единственности и липшицево-сти максимизатора и*(х,ф), что позволяет существенно расширить круг решаемых задач оптимального управления с терминальным функционалом. В теореме 1.6 доказывается сходимость метода вычисления функции цены для аппроксимационной задачи.

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

1{х(-),и(-)) = J /0(х№,и(г))(И ^ Ы о и фиксированным правым концом х(Т) = хг. Конечный момент времени Т тоже считается заданным.

Задача с фиксированным правым концом имеет ряд существенных отличий от ранее рассматриваемых задач. Так для некоторых начальных точек может не иметь решения даже задача управляемости, поэтому на задачу накладывается условие управляемости из каждой начальной точки ж(0) = хо € X, и функция цены ищется только для момента времени ¿о = 0. Кроме того при тех же условиях гладкости, что и для задач со свободным правым концом, функция цены не всегда обладает свойством липшицевости.

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

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

В следующем разделе 1.4 рассматривается ещё одна постановка задачи оптимального управления с фиксированным правым концом, а именно задача быстродействия. Считается, что конечный момент времени заранее не известен. В качестве минимизируемого функционала рассматривается время Т перевода системы (1) из начального положения х(0) =1о в конечное х(Т) = Х\.

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

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

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

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

В главе 3 диссертации исследуется задача приближенного вычисления максимальных и-стабильных мостов для нелинейных дифференциальных игр сближения, описываемых уравнением (2). Рассматривается задача наведения траектории системы на компактное терминальное множество Мей" в момент времени Т. Сначала рассматривается случай отсутствия фазовых ограничений.

Известно, что если построен максимальный и-стабильный мост IV в данной задаче, то задача наведения имеет решение в классе позиционных процедур управления для любой начальной точки (Ь0,хо) € \У.

Для построения максимальных стабильных мостов применяются попятные процедуры, использующие на каждом шаге некоторые операторы программного поглощения и их конечно-разностные аппроксимации. Эти процедуры дают достаточно точную аппроксимацию при выполнении некоторых условий невырожденности. В данной работе рассматриваются операторные конструкции, предложенные В.Н. Пшеничным и В.В. Остапенко [38]. В этих конструкциях для построения множества позиционного поглощения точное решение дифференциального уравнения (2) заменяется конечно-разностной схемой. Временной интервал [0,Т] разбивается на N одинаковых частей точками Т

О = ¿о < < • • • < % = Т, £(+1 — и = — = к.

Вводится оператор ЩА, ставящий в соответствие любому компактному множеству А С Яп множество

ЩА = р| е Яп : х + к/(х,и,у) € А}. veQueP

Используя оператор ЩА, задается рекуррентная последовательность множеств И^: г = О, ./V — 1.

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

Будем обозначать 50 = {ж € Яп : ||а?|| < а} - шар радиуса а с центром в нуле. Также для произвольного компактного множества А С Яп и некоторой константы а > 0 обозначим

В(а,А) = дА + За, \¥(а, А) = В(а, А) П А, 1аА:В(а,А)^д31некоторая непрерывная функция,

К(х и>, г, 1а,л) = (я + 1а,л(х)т + Ятг).

0 <т<ы

Компактное множество А С В,п удовлетворяет условию телесности с положительными константами а, и, г и функцией 1а,л > если для любого х € И/(а, А)

К(х,и,г,1аА) С А.

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

Выберем некоторые малые величины Д > 0 и 6 > 0. На множестве Р зададим конечное множество точек Р5 = {щ 6 Р} такое, что для любого и € Р найдется щ € Р$, для которого ||м — «гII <5. Аналогично определим множество = {vj £

В пространстве Дп зададим равномерную сетку с узлами в точках ¿»¿х = (Ьг-,,., Ь"п):

• • • < < = 0 < Ь\ < ., Ьу+1 - 6,- = -^,3 = -оо,., оо, г = 1,. ,п.

Множество всех точек £>гь.,гп обозначим через в а = {ъ^.г„ : ч = -оо,., оо, з = 1,., п}.

Для каждой точки Ь = (б1,., Ьп) £ ВА определим множество са(Ь) = {х е Дп : - Ь{\ < г = 1,., п}.

Будем называть множество сА(Ь) ячейкой, а точку Ь - ее центром.

Для произвольного компактного множества А С Я" определим множество Ва(А) С ВА:

Ва(А) = {ЬеВА: Сд(6) С\АфЩ. Далее для произвольного множества В С ВА зададим множество

Х(В) = ЦсА(Ь). ь£в

Для произвольного ограниченного множества В С ВА и любых и £ Р, у 6 <2 определим отображение

Р^А(В,и,у) = {ЬеВА : и,«) € Х{В) + 5Д}.

С использованием отображения для произвольного ограниченного множества В С ВА определим оператор

Пл.дВ = П

Также для множества В С -Вд определим аналог а-окрестности множества, где а > 0 -произвольная величина.

ВА(В) = {ЬеВА : сд(Ь) П Х(В) + 0}.

Далее зададим рекуррентную последовательность множеств И^:

У0 = ВД(М),

ТУ<+1 = Я£(ПЛ|дИГО, г = 0,., N — 1, где а > 0 - некоторый параметр.

В диссертации исследуется сходимость множеств Х(Й^) к искомым множествам IV(Ьг), г = 0,., N.

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

В теореме 3.1 доказывается сходимость предложенного метода аппроксимации максимальных и-стабильных мостов и приводятся условия согласования параметров /V, Д, 8 и сг, при которых эта сходимость имеет место.

В разделе 3.4 рассматриваются дифференциальные игры с фазовыми ограничениями, задаваемыми компактным множеством N С В.71. Определяется рекуррентная последовательность множеств И^ для игр с фазовыми ограничениями:

Щ = ВА{М), В£{ПН,№ П Вд(АО), г = 0,., т - 1.

В теореме 3.2 доказывается сходимость предложенной аппроксимационной схемы для игр с фазовыми ограничениями и приводятся условия согласования параметров N, А, 5 и сг, при которых эта сходимость имеет место.

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

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

Основные результаты диссертации:

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

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

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

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

Основные результаты диссертации опубликованы в работах [58]—[62].

Автор выражает глубокую благодарность своему научному руководителю Николаю Леонтьевичу Григоренко за постановку задачи, постоянное внимание к работе и ценные замечания, а также Аркадию Викторовичу Кряжимскому за многочисленные обсуждения работы.

1. Аввакумов С.H. Гладкая аппроксимация выпуклых компактов // Екатеринбург: УрО РАН. Труды института математики и механики. 1996. Т. 4. С. 184-200.

2. Аввакумов С.Н., Киселев Ю.Н. Численный метод поиска оптимального решения: Модель "РОСТ" // Математические модели в экономике и биологии: Материалы научного семинара: Планерное, Московская обл., 24-26 января 2003 г. М.: МАКС Пресс. 2003. С. 5-15.

3. Айзеке Р. Дифференциальные игры. М.: Мир. 1967.

4. Алексеев В.М., Тихомиров В.М., Фомин C.B. Оптимальное управление. М.: Наука. 1979.

5. Афанасьев В.Н., Колмановский В.Б., Носов В.Р. Математическая теория конструирования систем управления. М.: Высшая школа. 1998.

6. Бабалыев Т.Х., Хрипунов А.П. Один метод приближенного вычисления множеств позиционного поглощения в дифференциальных играх сближения // Ж. вычисл. матем. и матем. физ. 1995. Т. 35. N 11. С. 1749-1758.

7. Бахвалов Н.С. Численные методы. М.: Наука. 1973.

8. Беллман Р. Динамическое программирование. М.: ИЛ. 1960.

9. Благодатских В.И., Григоренко Н.Л., Киселев Ю.Н. Практикум по оптимальному управлению. М.: Издательство Московского университета. 1986.

10. Болтянский В.Г. Математические методы оптимального управления. М.: Наука. 1969.

11. Васильев Ф.П. Методы оптимизации. М.: Факториал пресс. 2002.

12. Григоренко Н.Л., Киселев Ю.Н., Лагунов Н.В., Силин Д.Б. Методы решения дифференциальных игр. Математическое моделирование. М.: Изд-во Московского университета. 1993.

13. Григорьева C.B., Тарасьев A.M., Успенский A.A., Ушаков В.Н. Конструкции теории дифференциальных игр при решении уравнений Гамильтона-Якоби // Екатеринбург: Изд-во УрО РАН. Труды института матем. и мех. УрО РАН. 2000. Т. 6. N 2. С. 320336.

14. Гусейнов Х.Г., Моисеев А.Н., Ушаков В.Н. Об аппроксимации областей достижимости управляемых систем // Прикл. матем. механ. 1998. Т. 62. N 2. С. 179-187.

15. Ильин В.А., Ким Г.Д. Линейная алгебра и аналитическая геометрия. М.: Издательство Московского университета. 2002.

16. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. М.: Наука. 1979.

17. Камке Э. Справочник по обыкновенным дифференциальным уравнениям. М.: Наука. 1976.

18. Киселев Ю.Н. Оптимальное управление. М.: Изд-во Моск. ун-та. 1988.

19. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука. 1976.

20. Красовский H.H., Субботин А.И. Позиционные дифференциальные игры. М.: Наука. 1974.

21. Красовский H.H. Управление динамической системой. М.: Наука. 1985.

22. Кряжимский A.B. К теории позиционных дифференциальных игр сближения и уклонения // Доклады АН СССР. Т. 239. N 4. С. 779-782.

23. Ли Э.Б., Маркус Л. Основы теории оптимального управления. М.: Наука. 1972.

24. Мищенко Е.Ф. Задачи преследования и уклонения от встречи в теории дифференциальных игр // Изв. АН СССР. Техн. кибернетика. 1971. N 5. С. 787-791.

25. Моисеев H.H. Численные методы в теории оптимальных систем. М.: Наука. 1971.

26. Моисеев H.H. Элементы теории оптимальных систем. М.: Наука. 1975.

27. Мордухович Б.Ш. Аппроксимационные методы в задачах оптимизации и управления. М.: Наука. 1988.

28. Никольский М.С. О нижнем альтернированном интеграле Понтрягина в линейных дифференциальных играх преследования // Математический сборник. 1985. Т. 128. N 1. С. 35-49.

29. Никольский М.С. Краткий обзор работ Л.С. Понтрягина по дифференциальным играм // Вестник Моск. университета, сер. 15, вычисл. матем. и киберн. 1993. N 3. С. 3-8.

30. Никольский М.С. О локальной липшицевости функции Веллмана в одной оптимизационной задаче // Труды Института математики и механики УрО РАН. 2004. Т. 10. N. 2. С. 106-115.

31. Петровский И.Г. Лекции по теории обыкновенных дифференциальных уравнений. М.: Наука. 1964.

32. Половинкин Е.С., Иванов Г.Е., Балашов М.В., Константинов Р.В., Хорев A.B. Об одном алгоритме численного решения линейных дифференциальных игр // Математический сборник. 2001. Т. 192. N 10. С. 95-122.

33. Понтрягин JI.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Наука. 1976.

34. Понтрягин Л.С., Линейные дифференциальные игры преследования // Математический сборник. 1980. Т. 112. N 3. С. 307-330.

35. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. М.: Наука. 1974.

36. Понтрягин Л.С. О линейных дифференциальных играх. I // Докл. АН СССР. 1967. Т. 174. N 6. С. 1278-1280.

37. Понтрягин Л.С. О линейных дифференциальных играх. II // Докл. АН СССР. 1967. Т. 175. N 4. С. 764-766.

38. Пшеничный Б.Н., Остапенко В.В. Дифференциальные игры. Киев: Наукова думка. 1992.

39. Раушенбах Б.В., Токарь E.H. Управление ориентацией космических аппаратов. М.: Наука. 1974.

40. Субботин А.И. Обобщенные решения уравнений в частных производных первого порядка. Перспективы динамической оптимизации. Москва-Ижевск: Институт компьютерных исследований. 2003.

41. Субботин А.И. Минимаксные неравенства и уравнения Гамильтона-Якоби. М.: Наука. 1991.

42. Субботин А.И. Минимаксные решения уравнений с частными производными первого порядка // 1996. Успехи мат. наук. Т. 51. N 6. С. 105-138.

43. Субботин А.И., Ченцов А.Г. Оптимизация гарантии в задачах управления. М.: Наука. 1981.

44. Субботина H.H. Необходимые и достаточные условия оптимальности управлений и траекторий // Сборник научных трудов "Синтез оптимального управления в игровых системах". ИММ УНЦ АН СССР. Свердловск. 1986. С. 86-96.

45. Субботина H.H. Необходимые и достаточные условия оптимальности в терминах принципа максимума и супердифференциала функции цены. Свердловск. ИММ УрО АН СССР. 1988. Деп. в ВИНИТИ, N 2898-В.88.

46. Субботина H.H. Метод характеристик Коши и обобщенные решения уравнений Гамильтона-Якоби-Беллмана // Докл. АН СССР. 1991. Т. 320. N 3. С. 556-561.

47. Субботина H.H. Унифицированные условия оптимальности в задачах управления // Труды Института математики и механики УрО РАН. 1992. Т. 1. С. 147-159.