Развитие выпуклого анализа и его приложений в теории дифференциальных игр тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи I гр* -и (Й !

I !_____ '

(

Иванов Григорий Евгеньевич

РАЗВИТИЕ ВЫПУКЛОГО АНАЛИЗА

И ЕГО ПРИЛОЖЕНИЙ

В ТЕОРИИ ДИФФЕРЕНЦИАЛЬНЫХ

ИГР

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва — 2004

Работа выполнена на кафедре высшей математики Московского физико-технического института

(государственного университета).

Официальные оппоненты: доктор физико-математических наук, профессор, член-корреспондент РАН A.A. Меликян,

доктор физико-математических наук, профессор М.С. Никольский,

доктор физико-математических наук, профессор В.В. Дикусар.

Ведущая организация Институт математики и механики Уральского отделения РАН.

Защита диссертации состоится "_" _

2005г. в_час. _мин. на заседании диссертационного

совета Д002.017.02 в Вычислительном центре им. A.A. Дородницына РАН по адресу: 119991, ГСП-1, Москва, ул. Вавилова, д. 40.

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

Автореферат разослан "_" _ 2005г.

Ученый секретарь диссертационного совета Д002.017.02

д.ф.-м.н. ¿^с^с В.В. Рязанов

1<Ш

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

Актуальность темы.

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

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

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

В работах Б.Т.Поляка, Е.Г.Голыптейна, Н.В.Третьякова, Ч.Олеха, Г. Франко вской, Ж.Ф.Виаля, М.В.Балашова, Е.С.Половинкина и др. рассматривались классы сильно и слабо выпуклых функций и множеств. Было показано, что условия сильной и слабой выпуклости играют большую роль в задачах аппроксимации. Был^ выявлена связь между

; ¿'УН f-rt.ii.-Ol "ГГ^Р"!

( Ь .ОЬОУ<-- '

сильной выпуклостью функции и гладкостью сопряженной (по Лежандру-Юнгу-Фенхелю) к этой функции. Развитие аппарата сильно и слабо выпуклых функций и множеств позволило доказать аналоги теорем Каратеодори и Крейна-Мильмана для сильно выпуклых множеств, а также получить новые результаты в теории экстремальных задач. Стало ясно, что свойства сильной и слабой выпуклости приводят к определенной регулярности экстремальных задач, что должно также проявляться в задачах оптимального управления и теории дифференциальных игр. В теории дифференциальных игр методы сильно и слабо выпуклого анализа особенно актуальны.

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

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

Фундаментальные результаты в теории дифференциальных игр были получены в работах Р. Айзекса, H.JL Григоренко, П.Б. Гусятникова, Ф. Кларка, А.Н. Красовского, H.H. Красовского, A.B. Куржанского, Ю.С.Ледяева, A.A. Меликяна,

Е.Ф. Мищенко, М.С. Никольского, Ю.С. Осипова, J1.A. Петросяна, Е.С. Половинкинэ,, JI.C. Понтрягина, Б.Н. Пшеничного, А.И. Субботина, У. Флеминга,

A. Фридмана, A.C. Ченцова, Ф.Л. Черноусько и др. Большинство современных алгоритмов, исследующих

дифференциальные игры, используют следующий метод стабильного моста H.H. Красовского. Сначала вычисляется функция цены игры g(t0,х0), значение которой равно оптимальному гарантированному результату в игре с начальным условием :r(i0) = Для дифференциальной игры с терминальным множеством вместо функции цены игры вычисляется альтернированный интеграл Л.С. Понтрягина. Затем на основе вычисленной функции цены игры или альтернированного интеграла строятся оптимальные гарантированные стратегии управлений. В работах Н.Д. Боткина, М.А. Зарха,

B.М. Кейна, А.Ю. Коврижных, Р.В. Константинова,

C.С. Кумкова, М.Д. Локшина, Н.Ю. Лукоянова, B.C. Пацко,

A.П. Пономарева, Е.В. Сидоровой и H.H. Субботиной, Д.Б. Силина, A.M. Тарасьева, В.Е. Третьякова,

B.Л. Туровой, A.A. Успенского, В.И. Ухоботова, В.Н. Ушакова, А.П. Хрипунова, A.A. Чикрия и других предложены алгоритмы, вычисляющие цену игры или альтернированный интеграл и строящие оптимальные гарантированные стратегии.

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

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

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

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

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

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

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

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

свойствами устойчивости и регулярности.

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

Целью диссертации является:

1) исследование новых свойств сильно и слабо выпуклых множеств и функций, выяснение связи между понятиями гладкости и слабой выпуклости;

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

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

Методика исследований.

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

в области выпуклого анализа - сумма и разность множеств по Минковскому, эпи-сумма (инфимальная конволюция) и эпи-разность функций, опорная функция, сопряженная функция, выпуклая оболочка;

в теории экстремальных задач - седловая точка функции;

в теории дифференциальных игр - функция цены игры, альтернированный интеграл, оптимальный

гарантированный результат, оптимальные стратегии игроков.

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

Научная новизна. Все основные результаты диссертации являются новыми и получены автором. Перечислим их.

1) Показано, что гладкость (дифференцируемость и условие Липшица для производной) функции, заданной в гильбертовом пространстве, эквивалентна совокупности условий слабой выпуклости и слабой вогнутости этой функции. Аналогичный результат получен для множеств в гильбертовом пространстве.

2) Разработано исчисление констант и параметров сильной и слабой выпуклости для множеств и функций.

3) Получены достаточные условия липшицевой зависимости седловой точки сильно выпукло-вогнутой функции от параметра.

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

5) Для дифференциальных игр с эллипсоидальными штрафными функциями развит метод эллипсоидов А.Б. Куржанского.

6) Доказана теорема о существовании седловой точки в классе программных стратегий для сильно выпукло-вогнутых дифференциальных игр. Для таких игр получен принцип минимакса, аналогичный принципу максимума JI.C. Понтрягина; доказаны гладкость функции цены игры и непрерывность оптимальных программных и позиционных стратегий игроков.

7) Разработан эффективный алгоритм построения оптимальных гарантированных стратегий в дифференциальных играх с эллипсоидальными штрафами.

Теоретическая и практическая ценность.

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

Апробация работы. Результаты диссертации докладывались на математической школе " Понтрягинские чтения" (Воронеж, 1994, 1995, 2004гг.), Международной конференции, посвященной 90-летию со дня рождения JI.C. Понтрягина (Москва, 1998г.), научных конференциях и семинарах Московского физико-технического института (МФТИ), научных семинарах кафедры системного анализа (рук. академик РАН A.B. Куржанский) и кафедры оптимального управления (рук. академик РАН Ю.С.

Осипов) факультета вычислительной математики и кибернетики Московского государственного университета, научном семинаре (рук. профессор В.Н. Ушаков) Института математики и механики Уральского отделения РАН, а также использованы при чтении спецкурса "Новые результаты выпуклого анализа" для студентов и аспирантов МФТИ (2003, 2004гг.).

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

Структура и объем диссертации. Работа состоит из введения, 7 глав, разделенных на 48 параграфов, заключения, списка литературы (242 наименования), списка обозначений и предметного указателя, всего - 383 страницы. В начале каждой главы приводится краткое изложение ее основных результатов. В диссертации доказано 76 теорем и 167 лемм, приведено 62 определения и 23 предложения. Предложения здесь - это известные результаты, формулировки которых важны для изложения материала.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Определение. Пусть в линейном пространстве С заданы множества X, У С С. Геометрическими суммой и разностью

или, что то же самое, суммой и разностью Минковского множеств X и У называются соответственно множества

Х + У ={х + у : хеХ, у <Е У}, У -X = {г е С : г + Х СУ}.

Заметим, что не все аналоги свойств операций сложения и вычитания чисел справедливы для множеств. Например, равенство X + У — У = X может не выполняется.

В §1.1 рассматриваются свойства геометрических операций для множеств в линейном пространстве. В §1.2 исследуются свойства геометрических операций для множеств в топологическом векторном пространстве. В частности, рассматривается вопрос, при каких условиях геометрическая сумма или разность множеств будет открытым или замкнутым множеством. В §1.3 вводится отношение "выпукло сильнее" для множеств.

Определение. Пусть в линейном пространстве С заданы множества X, У. Будем говорить, что множество X выпукло сильнее множества У, если У —X ф 0 и У — (У —X) = X.

Иначе говоря, множество X выпукло сильнее множества У, если множество X является пересечением некоторого семейства множеств, полученных параллельным переносом множества У. Показано, что отношение "выпукло сильнее" рефлексивно и транзитивно. Приведены свойства этого отношения, связанные с операциями над множествами. В §1.4 получены необходимые и достаточные условия на выпуклые множества X, У, обеспечивающие равенство X + У — У = X. Кроме того, получены достаточные условия, при которых операция геометрической суммы сохраняет отношение "выпукло сильнее" для множеств. Соответствующая теорема является развитием результатов

Е.С. Половинкина и М.В. Балашова. Приведены примеры, показывающие существенность условий этой теоремы.

В §1.5 рассматривается класс сильно выпуклых множеств.

Определение. Множество X в нормированном пространстве С называется сильно выпуклым с константой R > О, если множество X выпукло сильнее шара BR = {xeC: |М|<Д}.

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

Для любых двух точек xq,Xi нормированного пространства, находящихся на расстоянии не более 2R, введено понятие сильно выпуклого отрезка

DR(x,y)= Pi (d + BR).

d&C: {x,y}Cd+BR

В теории сильно и слабо выпуклых множеств сильно выпуклый отрезок DR(x, у) играет ту же роль, что и обычный отрезок [х\у] в выпуклом анализе. В §1.5 рассмотрены свойства сильно выпуклого отрезка.

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

Определение. Будем говорить, что множество X банахова пространства удовлетворяет "прямому

определению" сильной выпуклости с константой Д > О, если для любых двух точек х, у £ X выполнено неравенство \\у — я|| < 2Я и сильно выпуклый отрезок Дк(:г, у) целиком содержится в X.

В §1.5 приведено новое доказательство известного утверждения о том, что для замкнутого множества в гильбертовом пространстве прямое и двойственное определения сильной выпуклости эквивалентны.

В §1.6 приведены различные определения слабо выпуклых множеств.

Определение. Будем говорить, что множество X банахова пространства удовлетворяет "прямому определению" слабой выпуклости (или, что то же самое, слабо выпукло по Виалю) с константой Я > О, если для любых двух точек х,у € X таких, что 0 < \\у — х\\ < 2Я множество Вц(х, у) \ {х, у} имеет непустое пересечение с X.

Определение. Будем говорить, что множество X банахова пространства С удовлетворяет "двойственному определению" слабой выпуклости (или, что то же самое, слабо выпукло по Стечкину) с константой Я > 0, если множество X выпукло сильнее множества

{х в С : ||х|| > Я}.

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

этому классу. Двойственное определение слабой выпуклости не имеет указанного недостатка. В §1.6 показано, что для замкнутого множества в гильбертовом пространстве из прямого определения слабой выпуклости следует двойственное определение слабой выпуклости, а обратное неверно.

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

В §1.7 исследована связь слабой выпуклости и гладкости множеств.

Определение. Пусть заданы число L > 0 и множество X в гильбертовом пространстве И. Будем говорить, что множество X является телесно-гладким с константой L, если X ф И, cl int X = cl X, int cl X = int X и для любых векторов хих2 G дХ, pi е Nx(xi), р2 6 Nxfa) таких, что ||pi|| = ЦргЦ = 1 выполнено неравенство

||P2-Pi|| < L\\X2-Xx\\.

Здесь и далее через int X, cl X, дХ, Xе обозначаются соответственно внутренность, замыкание, граница и дополнение множества X.

Теорема 1. Пусть в гильбертовом пространстве % задано множество X ф Н такое, что cl int X — cl X

и int cl X = int X. Пусть R > 0. Следующие условия эквивалентны

1) множество X является телесно-гладким с константой 1 /Я;

2) множества cl X и cl (Xе) слабо выпуклы по Виалю с константой R;

3) множества cl X и cl (Xе) слабо выпуклы по Стечкину с константой R.

Известно, что сумма сильно выпуклых множеств с константами R\,R2 является сильно выпуклым множеством с константой Ri + R2. В §1.8 получен следующий результат.

Теорема 2. Пусть в гильбертовом пространстве % заданы множества X и Y. Пусть множество X слабо выпукло по Виалю с константой R, множество Y сильно выпукло с константой г € (0; R). Тогда множество X + Y слабо выпукло по Виалю с константой R — г.

В §1.8 получены неулучшаемые оценки констант сильной и слабой выпуклости для множеств X + Y, X — Y и X + Y — Z, тем самым разработано исчисление констант сильной и слабой выпуклости для множеств.

В §1.9 доказана следующая теорема.

Теорема 3. Пусть в гильбертовом пространстве % заданы множества X, Y, Z. Пусть cl int X = cl X и int cl X — int X, множество cl X слабо выпукло с константой R\ > 0, множество cl (Xе) слабо выпукло с константой R2 > 0, множество Y сильно выпукло с константой гj € (0; Ri), множество Z сильно выпукло с константой г2 £ (0; R2). Тогда

1) множество (с\ X) + Y —Z слабо выпукло с константой Ri — г\ и справедливы равенства

cl int (X + Y ±Z) = cl (X + Y = (cl X) + Y-Z =

= cl int (X -Z + Y) = cl (X - Z + У) = (cl X) -S-Z 4- Y]

2) множество ((int X) + Y — Z)c слабо выпукло с константой R2 — г2 и справедливы равенства

int cl {X + Y ±Z) = int (X + V ±Z) = (int X) + Y = = int cl(X - Z + Y) = int (X ~Z + Y) = (int X) - Z + Y

Тем самым получены условия на множества X, У, Z, обеспечивающие равенство множество Х + Y —Z и X —Z + Y, а также их гладкость.

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

В §1.10 введено понятие слабо выпуклой оболочки множества. Показано, что выпуклая и сильно выпуклая оболочки множества сохраняют слабую выпуклость дополнения к множеству, а слабо выпуклая оболочка дополнения множества сохраняет выпуклость и сильную выпуклость самого множества. Объединяя эти результаты с теоремой о связи слабой выпуклости и гладкости множества (теорема 1), получаем достаточные условия гладкости выпуклой, сильно и слабо выпуклой оболочек множеств. Приведен пример, показывающий, что слабо выпуклая оболочка дополнения множества может не сохранять слабую выпуклость самого множества.

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

Определение. Пусть С - линейное пространство. Для функций /, д : С —> Ш = Жи{+оо, —оо} определим эпи-сумму или, что то же самое, инфимальную конволюцию

inf

f(x-u)<+oo д(и)<+оо

эпи-разностъ

(/В <?)(*)

Г /(х+и)> I *?(«)<+

эир

(/(х + и)-д(и))

и :

—оо

0<+оо

(как это принято, предполагаем, что верхняя грань пустого множества равна —оо, а нижняя +оо).

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

В §2.3 вводится отношение "выпукла сильнее" для функций.

Определение. Будем говорить, что функция / : С —»• Ш. выпукла сильнее функции д : С М, если д В (д В /) = /.

Показано, что в линейном пространстве Ь:

1) функция / : С Ш выпукла сильнее функции д : С —> М тогда и только тогда, когда надграфик функции / является множеством, выпуклым сильнее надграфика функции д\

2) множество X С С выпукло сильнее множества У С £ тогда и только тогда, когда индикаторная функция множества X выпукла сильнее индикаторной функции множества У.

В §2.4 рассматривается понятие выпуклости функций с параметром А.

Определение. Пусть А - линейный непрерывный оператор, действующий в гильбертовом пространстве Н. Будем говорить, что функция / : % —> Ш выпукла с

параметром А, если функция / выпукла сильнее функции х ь-» ¿(х,Ах).

Здесь и далее через (х, у) обозначается скалярное произведение векторов хну.

Иными словами, выпуклость функции / с параметром А означает, что надграфик функции / можно представить в виде пересечения семейства множеств, полученных параллельными переносами надграфика квадратичной формы | (х,Ах). Поэтому данное определение можно назвать "двойственным определением" выпуклости функции / с параметром А. Следующая теорема показывает, что для полунепрерывной снизу функции / "двойственное определение" выпуклости с параметром А эквивалентно "прямому определению" выпуклости с параметром А, состоящему в том, что функция х (->■ /(ж) — \{х,Ах) выпукла.

Теорема 4. Пусть А - обратимый самосопряженный оператор на гильбертовом пространстве Функция / : % —> Ж выпукла с параметром А тогда и только тогда, когда функция х н-» /(х) — ^(х, Ах) выпукла, полунепрерывна снизу и не обращается в — оо.

Заметим, что в случае, когда оператор А неотрицательно определен данный результат был известен ранее.

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

Теорема 5. Пусть А1}А2 - обратимые самосопряженные операторы на гильбертовом пространстве Н. Пусть оператор А\ + А2 обратим и пусть А — Ах(А1 + А2)~1А2. Пусть заданы функции /х, /2 : Н —> Ш. Тогда

1) если функция fi выпукла с параметром Ai, функция /2 выпукла с параметром А2, оператор Ai + А2 положительно определен, то функция /1 ЕВ f2 выпукла с параметром А\

2) если функция /1 выпукла с параметром Ai, функция —/2 выпукла с параметром А2, оператор А\ + А2 отрицательно определен, то функция /1 В f2 выпукла с параметром А.

В §2.5 рассмотрены классы сильно и слабо выпуклых функций, которые являются важными частными случаями классов функций, выпуклых с параметром А, рассмотренных в §2.4.

Определение. Пусть задано выпуклое множество X С С и задана функция f : X М. Функпия / называется сильно выпуклой с константой С на множестве X, если функция / — f||x||2 ьыпукла на X. Функшя / называется слабо выпуклой с константой С на множестве X, если функция / + у11х112 выпукла на X.

В качестве следствия результатов §2.4 в §2.5 построено исчисление констант сильной и слабой выпуклости функций.

В §2.6 доказана следующая теорема, позволяющая " расщепить" свойство гладкости функции / на два свойства: слабую выпуклость функции / и слабую выпуклость функции -/.

Теорема 6. Пусть X - выпуклое открытое множество в гильбертовом пространстве Пусть задана функция / : X JR. Пусть L > 0. Следующие условия эквивалентны

1) функция / дифференцируема на X и производная функции / удовлетворяет условию Липшица на X с константой L;

2) функции / и —/ слабо выпуклы на множестве X с константой L.

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

1) Для множеств прямое и двойственное определения слабой выпуклости не эквивалентны, а для функций соответствующие определения равносильны.

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

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

В §2.7 показано, что выпуклая, сильно выпуклая и слабо выпуклая оболочки сохраняют сильную и слабую вогнутость функции. Получены достаточные условия гладкости выпуклых, сильно выпуклых и слабо выпуклых оболочек функций. Показано, что из полученных результатов вытекает известный результат Е.Г. Голынтейна и Н.В. Третьякова о связи гладкости функции / и сильной выпуклости ее сопряженной /*.

В §2.8 изложен метод построения гладких аппроксимаций непрерывной функции, основанный на эпи-операциях.

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

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

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

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

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

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

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

В §3.2 получены достаточные условия, при которых седловая точка удовлетворяет условию Липшица относительно параметра. Показано, что в случае, когда множества, задающие ограничения, липшицевым образом зависят от параметра, седловая точка в зависимости от параметра может не удовлетворять условию Липшица, а удовлетворяет условию Гельдера с показателем |. Указанный результат используется для доказательства непрерывности оптимальных управлений в дифференциальных играх с сильно выпукло-вогнутым функционалом (§6.4).

В §3.3 получено достаточное условия существования седловой точки в задаче

тГ эир/(х — и + и), иеРьеЬ

состоящее в том, что лебеговы множества функции / замкнуты и телесно-гладкие с константой а множества Р и Q сильно выпуклы с константой г < R.

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

Рассматривается линейная дифференциальная игра

^- = A(t)z(t)-B(t)u(t) + C(t)v(t) (1)

на отрезке времени t £ Здесь z(t) G 2Rn -

фазовый вектор системы, t - время, A(t), B(t), C(t) -матрицы размеров соответственно п х п,п х р,п х ç, кусочно-непрерывно зависящие от времени, u(t) G Mр -управление первого игрока, v(t) G ïïtq - управление второго игрока. Управления игроков подчиняются геометрическим ограничениям

u{t) G Р, v{t) G g, (2)

где P С JRP, Q С M9 - выпуклые компакты. Задана терминальная функция платы 7 : jR"1 —> jRtJ{-|-oo}.

Цель первого игрока и состоит в минимизации значения 7(112(19)), где z($) - значение фазового вектора системы в конечный момент времени П - заданная матрица размера гахп. Цель второго игрока v - противоположная: j(IIz(i9)) —>■ max. Матрица П позволяет сократить размерность задачи в случае, когда терминальная функция платы зависит не от всех компонент фазового вектора.

Предполагается, что игрокам известны динамика системы (1), ограничения на управления (2), отрезок времени матрица П и функция платы 7. При выборе своего управления в момент времени t каждый игрок может пользоваться информацией о значениях фазового вектора

в предшествующие моменты времени V Е информация, относящаяся к моментам времени > считается недоступной.

Выполним преобразование системы (1). Пусть Ф(£, г) -фундаментальная матрица решений системы ¿(¿) = то есть

г) = А{1)Ф(*, г), Ф(г, г) - Еп, (3)

где Еп - единичная матрица размера пхп. Вместо фазового вектора введем вектор

х(г) = ПФ(<М)*(*)- (4)

Система (1) примет вид

^ = ПФ(Л, г) (-Я(*)иЮ + С(ф(*)) • (5)

Поскольку ж(^) = то в терминах вектора цель игрока и состоит в минимизации значения а цель

игрока V в максимизации этого значения.

Введем разбиение Т = о отрезка времени [т?о;$]-

Для удобства построения конструкций в обратном времени точки разбиения будем нумеровать в обратном порядке:

*?о = < Ьс-\ < ■ ■ ■ < к < к = -в. (6)

Определение. Будем говорить, что определена кусочно-программная стратегия игрока и, соответствующая разбиению Т = если для любого индекса к €

{1 ,...,/С} и для любого вектора х = х{Ьь) определена интегрируемая по Лебегу функция и : —> Р.

Если определена кусочно-программная стратегия игрока и,

то наибольшее (то есть наихудшее для игрока и) значение 7(х(19)) будем называть гарантированным результатом для данной стратегии игрока и. Оптимальной гарантированной стратегией игрока и называется кусочно-программная стратегия игрока и, обеспечивающая наименьшее значение гарантированного результата. Это наименьшее значение гарантированного результата для игрока и будем называть оптимальным гарантированным результатом для игрока и.

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

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

Через Рк,С}к обозначим следующие интегралы Аумана:

Рк = [ ПФ(0,t)B{t)P dt, Qk= f П ${ö,t)C{t)Qdt. Jtk Jtk

(7)

Через 7* (ж) обозначим оптимальный гарантированный результат для игрока и на отрезке времени \tk при начальном условии x(tk) = х. В силу принципа динамического программирования оптимальный

гарантированный результат для игрока и определяется следующей попятной конструкцией

7о(я) = 7(я)> = min max7k_i(a:-u + i>), к € {1,...,К).

и ер* veQk

(8)

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

Оптимальный гарантированный результат для игрока и, соответствующий разбиению Т = {4}£=о на всем отрезке при начальном условии х($о) — х, равен

7(х;Т) = 7к{х), где функция у/с{%) определяется попятной конструкцией (8).

Аналогично, оптимальный гарантированный результат t

для игрока V, соответствующий разбиению Т = {ifc}fc=0 на всем отрезке [^о;^] Для начального условия х(-до) = х, равен ^

ß(x; Т) = ßic(x), где функция ßic(x) определяется следующей попятной конструкцией.

ßo(x) = j(x), ßk(x) = шах min ßk_i(x-u+v), k G {1,.. . ,£}.

veQk uepk

(9)

Обозначим через ДТ мелкость (максимальный шаг) разбиения Т:

ДТ = шах (ijb-1-tfc). (10)

Определение. Если существует функция 7 : lRm —> iR(J{+oo} такая, что для любого х G JRm справедливы соотношения

ß(x;T)->j(x), 7(*;Т)-> %х) при ДТ->0, (11)

то значение у(х) будем называть предельным оптимальным гарантированным результатом .

В §4.2 доказана следующая теорема.

Теорема 7. Пусть терминальная функция платы 7 удовлетворяет условию Липшица, а множество Р, "

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

результату с квадратичной относительно мелкости разбиения скоростью. А именно, существует константа С такая, что для любого равномерного разбиения отрезка времени, мелкость которого удовлетворяет неравенству ||Л||ДТ < 1 и для любого х € Ш™ справедливы неравенства

В §4.3 рассмотрена дифференциальная игра с терминальным множеством М. Указанная игра эквивалентна рассмотренной выше дифференциальной игре с терминальной функцией платы, равной индикаторной функции множества М:

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

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

С целью исследования вопросов сеточных аппроксимаций выпуклых положительно однородных функций вводится

7(х)-С(ДГ)2 </?(*; Л <7(*).

О, х£ М +оо, х £ М

сеточный оператор, результат действия которого на функцию /(р) равен /(р) если вектор ^ принадлежит сетке и +оо, если вектор ^ не принадлежит сетке. Показано, что сеточная реализация алгоритма вычисления альтернированных сумм эквивалентна действию сеточного оператора на каждом шаге алгоритма. При сеточной ,

аппроксимации выпуклого компакта погрешность аппроксимации пропорцианольна мелкости сетки, а для сильно выпуклого множества - квадрату мелкости сетки. »

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

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

В главе 5 рассматриваются дифференциальные игры с эллипсоидальными штрафными функциями и эллипсоидальной терминальной функцией платы.

Определение. Пусть РОп - это класс симметрических положительно определенных (п х п)-матриц. Через С1п ,

обозначим следующее множество наборов, состоящих из матрицы и двух чисел:

Пп = {(К, в, а) | К е РБп,0 > 0,а € м}. Для любого набора и> = (К, 9, а) € определим функцию

</?(•; и) векторной переменной х 6 Ш4:

-о - 0\/1 - хтК~1х, хтК~хх < 1

Графиком функции ш) является часть поверхности эллипсоида в Мп+1, поэтому функции (р(-;и>) называется эллипсоидальными.

В главе 5 рассматривается дифференциальная игра

Предполагается, что для любого £ е [0; штрафные функции а(£, •), /?(£, •) и терминальная функция платы 7(-) являются эллипсоидальными: а(1, •), /?(£, •), 7(-) € Ф".

Эллипсоидальные штрафы учитывают требования минимизации затрат на управления. Затраты считаются минимальными, если вектор управления совпадает с центром эллипсоида. При приближении вектора управления к границе допустимых значений затраты на управления возрастают. Известные классы дифференциальных игр, такие как линейные игры с квадратичным критерием качества и линейные игры с эллипсоидами в качестве терминального множества и допустимых множеств управлений игроков, рассматриваемые в методе эллипсоидов А.Б. Куржанского, являются предельными случаями дифференциальных игр данного класса.

Определение. Будем говорить, что непрерывно-дифференцируемая функция и> : [0;$] -» является

= „(0 - и(*), «е[0;*1 (12)

с терминально-интегральным функционалом платы

и-стратегической в дифференциальной игре (12), (13), если <p{-,u){v)) = 7(-) и при всех t G ф G Rn

FM). (14)

где через a*(t, •), /?*(£, •) обозначены функции, сопряженные к a(t, •),/?(*,.)•

На основе метода эллипсоидов А.Б. Куржанского, в §5.2 предлагается эффективный метод вычисления и-стратегической функции.

В §5.3 введено понятие гарантированного результата для позиционной стратегии и сформулирована следующая теорема о гарантированном управлении.

Теорема 8. Пусть функция uj(t) является и-стратегической. Тогда функция

upos{t,x) = щ(х,ш(г),шр{г)) является позиционной стратегией игрока и. А функция

W(t,x) = <p(x;u>(t))

является гарантированным результатом для этой стратегии.

В §5.4, §5.5 изложено доказательство теоремы о гарантированном управлении, основанное на теореме о выживании для дифференциальных уравнений и технике дифференциальных неравенств А.И. Субботина.

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

В главе 6

дифференциальная игра

рассматривается нелинейная

^ = f(t,x(t)Mt),v(t)),

х{0) = х0 (15)

на отрезке времени t G [0; с функционалом качества

J = 7(Ф))+J (ф, x(t), u(t), v(t))+a(t, u{t))-P(t, v(t))) dt,

(16)

Предполагается, что функции /, a, /3, 7, борелевские по совокупности переменных и при любом фиксированном t в [О;0] функции f(t,x,u,v), 7(2;), p(t,x,u,v) дифференцируемы по x,u,v и соответствующие частные производные удовлетворяют условию Липшица, а функции a(t,u), /3(t,v) сильно выпуклы по и и v соответственно, причем константы сильной выпуклости больше некоторого выражения, зависящего от констант Липшица функций /, а, /3, 7, <р и констант Липшица частных производных этих функций.

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

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

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

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

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

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

В главе 7 рассматривается дифференциальная игра

x(t) = A(t)x(t) + Bu(t)u(t) + Bv(t)v(t), а:(0) = Xq (17)

на отрезке времени t € [0; с функционалом качества

ê

J = ^T(i9)Fx(tf) + J{-Pu{t, u(t)) + 0v{t, v{t))) dt, (18)

о

ßu(t,u) = lu{t)^\-uTGu{t)u,

ßv(t,v) = ъ^)^ - vTGv(t)v.

Указанная постановка задачи близка к постановке, рассматриваемой в главе 5. И в том и в другом случае штрафные функции ßu(t, и), ßv(t, v) являются эллипсоидальными относительно управлений игроков, то есть их графики лежат на поверхностях эллипсоидов. Отличие состоит в том, что в главе 5 предполагается, что терминальная функция платы эллипсоидальна, а в главе 7 терминальная функция платы |xT{ß)Fx{'d) является квадратичной формой. Однако методы анализа дифференциальных игр, рассмотренных в главах 5 и 7, существенно различаются. В главе 5 на основе метода эллипсоидов A.B. Куржанского приводится алгоритм построения гарантированных, но вообще говоря не оптимальных стратегий игроков. В главе 7 при некоторых предположениях строятся оптимальные гарантированные стратегии.

Обозначим через т ранг матрицы F. Приведем квадратичную функцию xTFx к каноническому виду. Получим существование матриц S е Мт*п и Fi е jRmxm таких, что F = STFiS, где

Пусть матрично-значная функция Ф : [0; ]Rmxn

является решением задачи Коши

г + s = т.

(20)

Ф(г) = -<&(t)A(t), Ф(0) = S. При t G [0; определим матрицы

(21)

Pu(t) = Ф (t)Bu(t)G'\t)BlmT(t), Pv(t) = Ф^ДДОСчТ1

»tivift А.,

вИБЛМОГЕК. СЯетсубУРГ 09 W ш

Обозначим

V V

К = ¡Ш™*' 7' = 1шт*- (23)

Теорема 9. Пусть матрицы Ри + РиР\Ри иР„- РУЕХРЬ неотрицательно определены. Тогда для дифференциальной игры (17) - (19) существует седловая точка в классе программных стратегий. Соответствующие оптимальные программные стратегии игроков определяются формулами

т = _ с-\1)в1{фТт = с-\1)вту{фт{г)Ф у/ШТ^ШФ' у/-г+

(24)

где вектор ф 6 Мп определяется путем решения уравнения

ЪФ = ( ~ , ] Л.

РиШ РуЩ

у/>№ + ФтРи№ VI+

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

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

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

В §7.4 предполагается, что

1) матрица Г, определяющая терминальное слагаемое функционала качества игры, неотрицательно определена;

2) весовой коэффициент 7„ при штрафной функции для игрока, максимизирующего функционал качества, достаточно велик, то есть выполнено неравенство ||Р„|| < 1;

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

Для игр рассматриваемого вида построена е-стратегия управления игрока, минимизирующего функционал качества. Рассматриваемая е-стратегия имеет два преимущества по сравнению с точной оптимальной гарантированной стратегией в дифференциальной игре с чисто геометрическими ограничениями на управление игрока-минимизирующего. Во первых, е-стратегия удовлетворяет условию Липшица как функция времени и параметров игры. Во вторых, алгоритм, определяющий е-стратегию, прост и эффективен с вычислительной точки зрения. Следует иметь в виду, что при е —0 константы Липшица е-стратегии стремятся к бесконечности, а скорость сходимости рассматриваемых алгоритмов падает. Это говорит о том, что параметр е, характеризующий точность е-стратегии, следует выбирать не слишком маленьким.

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

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

В §7.6 рассмотрен пример дифференциальной игры в четырехмерном пространстве. На этом примере проиллюстрированы некоторые качественные свойства дифференциальных игр исследуемого класса.

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

[1] Иванов Г.Е. Теорема о минимаксе для интегрального функционала. // Некоторые проблемы математики в задачах физики, механики, экономики. М.: МФТИ. 1990. С.61-66.

[2] Иванов Г.Е. Критерий сводимости альтернированного интеграла Понтрягина к альтернированной сумме. // Математическое моделирование процессов управления и обработки информации. М.: МФТИ. 1993. С.178-183.

[3] Иванов Г.Е. Квадратичная сходимость алгоритма вычисления цены линейной дифференциальной игры с выпуклой функцией платы. / / Математическое моделирование процессов управления и обработки информации. М.: МФТИ. 1993. С.184-191.

[4] Иванов Г.Е. Оценка погрешности алгоритма вычисления альтернированного интеграла Понтрягина, связанной с дискретизацией по пространству. / / Численные методы интегральных уравнений в прикладных задачах: Научно-метод. матер. ВВИА им. Н.Е. Жуковского. М. 1994. С.76-90.

[5] Иванов Г.Е. Квадратичная оценка сходимости алгоритма вычисления альтернированного интеграла Понтрягина. / / Численные методы интегральных уравнений в прикладных задачах.: Научно-метод. матер. ВВИА им. Н.Е. Жуковского. М. 1994. С.91-111.

[6] Иванов Г.Е., Половинкин Е.С. О квадратичной сходимости алгоритма решения линейных дифференциальных игр. // Тезисы докладов школы "Понтрягинские чтения - 5". Воронеж. ВГУ, 1994. С.59.

[7] Иванов Г.Е. Логарифмическая гладкость в задаче управления стохастическими системами. // Моделирование процессов управления и обработки информации. М.: МФТИ. 1994. С.175-181.

[8] Иванов Г.Е., Половинкин Е.С. Второй порядок сходимости алгоритма вычисления цены линейной дифференциальной игры. // Доклады РАН. 1995. 340. № 2. С.151-154.

[9] Иванов Г.Е., Половинкин Е.С. О сильно выпуклых линейных дифференциальных играх. // Дифференц. уравнения. 1995. 31. № 10. С.1641-1648.

[10] Иванов Г.Е. Дифференциальные игры с сильно выпуклыми штрафами. // Тезисы докладов школы "Понтрягинские чтения - 6". Воронеж. ВГУ. 1995. С.39.

[11] Иванов Г.Е. Оптимальное гарантированное управление линейными системами при наличии возмущений. // Мат. заметки. 1996. 60. № 2. С.198-205.

[12] Иванов Г.Е. Седловая точка для дифференциальных игр с сильно выпукло-вогнутым интегрантом. // Мат. заметки. 1997. 62. J№ 5. С.725-743.

[13] Иванов Г.Е. Гарантированное управление в дифференциальных играх с эллипсоидальной платой. // Прикл. матем. и мех. 1998. 62. № 4. С.598-607.

[14] Иванов Г.Е. Метод эллипсоидов для дифференциальных игр с терминально-интегральной платой. // Доклады РАН. 1998. 362. № 3. С.300-303.

[15] Ivanov G.E. Regularization of Kurzhanskii's ellipsoidal techniques. // Междунар. конф., посвящ. 90-летию со дня рождения JI.C. Понтрягина, Москва 31 авг. - 6 сент. 1998: Тез. докл. Т.З. Оптимальное управление и добавления. Москва. 1998. Р.92-93.

[16] Иванов Г.Е. Непрерывность оптимальных управлений в дифференциальных играх и некоторые свойства слабо и сильно выпуклых функций. // Мат. заметки. 1999. 66. № 6. С.816-839.

[17] Иванов Г.Е. Гладкость и выпуклость в задаче на минимакс. // Тезисы докладов 42-ой научной конференции МФТИ, 1999. Часть 2. С.93.

[18] Иванов Г.Е. Гладкость и выпуклость маргинальных функций. // Некоторые проблемы фундаментальной и прикладной математики. М.: МФТИ. 1999. С.79-92.

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

[20] Иванов Г.Е. Явный вид оптимальных стратегий в дифференциальной игре с геометрическими ограничениями на управления. / / Материалы

Воронежской весенней математической школы "Понтрягинские чтения - 15". Воронеж. ВГУ, 2004. С.100-101.

[21] Иванов Г.Е. Дифференциальные игры с эллипсоидальными штрафами. // Прикл. матем. и мех. 2004. 68. № 5. С.725-745.

[22] Иванов Г.Е. Отношение "выпукло сильнее" для множеств. // Некоторые проблемы фундаментальной и прикладной математики. М.: МФТИ. 2004. С.75-102.

[23] Иванов Г.Е. Слабая выпуклость множеств по Виалю и чебышевский слой. // Труды XLVII научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук". Часть VII. 2004. С.7-9.

Работы автора по теме диссертации были поддержаны грантами РФФИ по проектам 98-01-00645, 01-01-00743, 0301-14053, 04-01-00787.

»

»

Иванов Григорий Евгеньевич

Развитие выпуклого анализа и его приложений в теории дифференциальных игр

Подписано в печать 23.12.2004

Формат бумаги 60x84 1/16 Уч.-изд.л. 1,9. Усл.-печ.л. 2,5 Тираж 100 экз. Заказ 61

Отпечатано на ротапринтах в Вычислительном центре им. A.A. Дородницына РАН 119991, Москва, ул. Вавилова, 40

<

1

i

»

«

<

I

I

I

I

II

РНБ Русский фонд

2006-4 1991

Введение

1 Сильно и слабо выпуклые множества.

1.1 Операции над множествами.

1.2 Топологические свойства суммы и разности множеств.

1.3 Отношение "выпукло сильнее" для множеств.

1.4 Сохранение отношения "выпукло сильнее" при суммировании множеств.

1.5 Сильно выпуклые множества.

1.6 Слабо выпуклые множества.

1.7 Слабая выпуклость и гладкость множеств.

1.8 Исчисление констант сильной и слабой выпуклости для множеств.

1.9 Перестановочность геометрических операций.

1.10 Гладкость сильно и слабо выпуклых оболочек множеств.

1.11 Теорема об альтернативе для дифференциальных игр.

2 Сильно и слабо выпуклые функции.

2.1 Операции над функциями.

2.2 Связь операций над множествами и операций над функциями.

2.3 Отношение "выпукла сильнее" для функций.

2.4 Исчисление параметоров выпуклости для функций.

2.5 Сильно и слабо выпуклые функции.

2.6 Слабая выпуклость и гладкость функций.

2.7 Выпуклая, слабо выпуклая и сильно выпуклая оболочки функций.

2.8 Аппроксимации непрерывной функции гладкими функциями.

2.9 Верхняя и нижняя производные второго порядка.

2.10 Сильная выпуклость множества и гладкость его опорной функции.

2.11 Некоторые свойства операций с функциями и множествами.

2.12 Сильно выпуклые штрафные функции.

3 Регулярность задачи на минимакс.

3.1 Теоремы о существовании седловой точки.

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

3.3 Условия существования седловой точки в терминах множеств уровня.'.

4 Квадратичная сходимость алгоритмов решения линейных дифференциальных игр.

4.1 Кусочно-программные стратегии.

4.2 Дифференциальная игра с липшицевой функцией платы.

4.3 Дифференциальная игра с терминальным множеством.

4.4 Оценки погрешностей, связанных с дискретизацией по пространству.

4.5 Пример.

5 Гарантированное управление в дифференциальных играх с эллипсоидальной платой.

5.1 Дифференциальная игра с эллипсоидальной платой.

5.2 Стратегическая функция.

5.3 Теорема о гарантированном управлении.

5.4 Лемма о нижней производной.

5.5 Доказательство теоремы о гарантированном управлении.

6 Дифференциальные игры с сильно выпукло-вогнутым функционалом.

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

6.2 Существование седловой точки в классе программных стратегий.

6.3 Принцип минимакса.

6.4 Непрерывность оптимальных стратегий и гладкость функции цены игры.

6.5 Пример.

6.6 Игры с сильно выпуклыми ограничениями.

7 Дифференциальные игры с эллипсоидальными штрафами.

7.1 Теорема о седловой точке.

7.2 Вычисление вектора сопряженных переменных методом простой итерации.

7.3 Вычисление вектора сопряженных переменных методом Ньютона.

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

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

7.6 Пример.

В теории экстремальных задач математический аппарат классического гладкого анализа необходим, но не достаточен. Например, максимум двух сколь угодно гладких функций является в общем случае не дифференцируемой функцией. Так естественным образом в экстремальных задачах возникают негладкие объекты, необходимость работы с которыми привела к появлению и развитию негладкого анализа [27, 29, 30, 64, 90, 91, 104, 113, 114, 199, 200, 204].

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

Основы выпуклого анализа заложены в работах Минковского, Фенхеля, Моро, Рокафеллара и др. [94, 156, 189, 203, 204, 211, 212, 219, 220, 228, 229, 230, 231, 233]. К настоящему времени написано большое количество трудов по выпуклому анализу и его приложениям [2, 7, 18, 26, 28, 31, 32, 61, 99, 105, 110, 115, 136, 137, 138, 145, 153, 180, 181, 198].

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

В работах [25, 165, 201, 207, 224, 240] разработан аксиоматический подход к понятию выпуклости, который состоит в следующем. В множестве С выбирается семейство подмножеств Ф, называемое базой выпуклости. Множество X С С называется Ф-выпуклым, если оно представимо в виде пересечения некоторого подсемейства множеств из данного семейства Ф. Также предлагались различные понятия выпуклости для функций, соответствующие различным понятиям выпуклости множеств - надграфиков этих функций.

В настоящей работе рассматривается отношение " выпукло сильнее" для множеств и для функций. Отношение "выпукло сильнее" является важным частным случаем понятия Ф-выпуклости. Будем говорить, что множество X в линейном пространстве С выпукло сильнее множества У С если множество X является Ф-выпуклым для семейства Ф, состоящего из всевозможных сдвигов У + <1 множества У на векторы в. 6 С. Функция / называется выпуклой сильнее функции д, если надграфик функции / является множеством, выпуклым сильнее над-графика функциии д.

Множество X в нормированном пространстве называется сильно выпуклым с константой Я > 0, если множество X выпукло сильнее замкнутого шара радиуса Я. Сильно выпуклые множества рассматривались в работах [8, 9, 10, 41, 42, 43, 44, 47, 48, 62, 71, 129, 130, 131, 132, 133, 134, 136, 215, 235, 236, 241].

В работе [33] С.Б. Стечкиным и Н.В. Ефимовым в связи с исследованием чебышевских множеств было введено понятие о-выпуклого множества. Множество X в нормированном пространстве называется а-выпуклым, если оно представимо в виде пересечения дополнений к открытым шарам радиуса о. В нашей работе вместо термина "а-выпуклое множество" используется термин "множество, слабо выпуклое по Стечкину с константой а". Таким образом, множество X в нормированном пространстве С слабо выпукло по Стечкину с константой Я, если оно выпукло сильнее множества {х 6 С : ||аг|| > Я}. В работе [241] Ж.-Ф. Виаль ввел другое определение слабо выпуклого множества. В нашей работе установлена связь различных определений слабо выпуклых множеств и получены новые свойства этих множеств.

В работах [18, 51, 54, 55, 134, 136, 138, 241] рассмотрены сильно и слабо выпуклые функции. Функция /, определенная в нормированном пространстве, называется сильно выпуклой с константой С > О, если функция х i-> f(x) — j || х j|2 выпукла. Функция / называется слабо выпуклой с константой С > О, если функция х /(я)+§1М|2 выпукла. Функция / называется сильно (слабо) вогнутой с константой С > О, если функция —/ сильно (слабо) выпукла с константой С.

Напомним, что геометрические операции суммы и разности (по Минковскому) множеств X и У в линейном пространстве определяются следующим образом:

X + Y = {x + y : хеХ, yeY}, Y^X = {z : z + XcY}.

Пусть на линейном пространстве С заданы функции /, д : С —М, со значениями из расширенной числовой Ж = E|J{—со, +оо}. Определим эпи-сумму В </)(*)= inf (f(x-u) + g(u))

U * X д(и)<+оо и эпи-разность

Б <7)(®)= sup (/(® + «)-p(ii)). u . Г/(х+и)>-00 \ p(u)<+oo

Операция эпи-суммы рассматривалась в работах [61, 156], где она называется инфимальной конволюцией. Мы используем названия "эпи-сумма" и "эпи-разность", которые подчеркивают тот факт, что над-графики (эпиграфы) эпи-суммы и эпи-разности функций / и д с точностью до замыкания равны соответственно геометрической сумме и геометрической разности надграфиков функций fug.

Отношение "выпукло сильнее" для множеств можно сформулировать через геометрическую разность, а для функций - через эпи-разность. Множество X выпукло сильнее множества Y тогда и только тогда, когда У — = У — (У — X). Функция / выпукла сильнее функции д тогда и только тогда, когда / = д В (д В /). Поэтому определения сильно и слабо выпуклых множеств и функций удобно формулировать в терминах геометрических операций с множествами и эпи-операций с функциями.

В связи с развитием выпуклого анализа важно установить связь между понятиями выпуклости и гладкости. В работе [18] показана связь между сильной выпуклостью функции / и гладкостью сопряженной (по Лежандру-Юнгу-Фенхелю) функции /*.

В нашей работе установлена связь между гладкостью и слабой выпуклостью функций. Мы показали, что для функции /, заданной в гильбертовом пространстве, дифференцируемость / и условие Липшица для производной функции / с константой Ь эквивалентны совокупности условий слабой выпуклости и слабой вогнутости функции / с константой Ь (§2.6). Аналогичный результат получен и для множеств (§1.7). Тем самым, подобно тому, что непрерывность функции можно представить как совокупность условий полунепрерывности сверху и снизу, гладкость функции можно представить в виде совокупности условий слабой выпуклости и слабой вогнутости.

Как известно, для существования минимума функции / на компакте нужна не непрерывность, а полунепрерывность снизу функции /. Подобно этому для регулярности задачи на минимум нужна сильная выпуклость. В частности, если на гильбертовом пространстве И заданы полунепрерывные снизу функции /, д : Н ®ЦЛ+оо}, причем функция д сильно выпукла с константой Я, а функция / дифференцируема и ее производная удовлетворяет условию Липшица с константой

Ь < Я,, то при любом х Е % минимум т'т(/(х — и) + д(и)) достигается иен в некоторой единственной точке гхтш(а;), причем функция ггт1П удовлетворяет условию Липшица с константой (лемма 3.2.3).

В нашей работе построено исчисление параметров сильной и слабой выпуклости для геометрических операций с множествами (§1.8) и эпи-операций с функциями (§2.4). Тем самым для экстремальных задач, представимых в терминах эпи-операций, решается проблема негладкости.

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

Важным разделом теории экстремальных задач является исследование задачи на минимакс. В работе [105] доказана теорема о существовании седловой точки в минимаксной задаче для выпукло-вогнутой функции. В третьей главе нашей работы доказана липшицева зависимость от параметра седловой точки в минимаксной задаче для сильно выпукло-вогнутой функции.

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

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

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

Понятие "дифференциальная игра" было введено Р. Айзексом в книге [5], где разобраны многочисленные примеры, но еще отсутствует четкая математическая формализация дифференциальной игры. В нашей стране труды академиков JI.C. Понтрягина [147] и Н.Н. Красов-ского [81] положили начало развития двух направлений в исследовании дифференциальных игр, различающихся математической формализацией игры и классами стратегий игроков.

Фундаментальные результаты в теории дифференциальных игр получены в работах Р. Айзекса [5], H.J1. Григоренко [19, 20], П.Б. Гу-сятникова [21, 22, 23, 24], Ф. Кларка [65], А.Н. Красовского [72], Н.Н. Красовского [73, 74, 75, 76, 77, 78, 79, 80, 81, 82], А.Б. Кур-жанского [86, 87, 88, 89, 222, 223], Ю.С.Ледяева [65], А.А. Меликя-на [101, 195], Е.Ф. Мищенко [102, 103, 148, 232], М.С. Никольского [107, 108, 109, 111, 112], Ю.С. Осипова [83, 116, 117, 118], Л.А. Пет-росяна [123, 124], Е.С. Половинкина [22, 23, 125, 128], JT.C. Понтрягина [142, 143, 144, 146, 147, 148], Б.Н. Пшеничного [149, 150, 151, 152], А.И. Субботина [65, 73, 74, 75, 167,168, 169, 170, 171, 172, 173, 174, 175], У. Флеминга [213, 214], А. Фридмана [216], А.С. Ченцова [170, 175, 191, 192, 193, 194], Ф.Л. Черноусько [195] и др.

Будем рассматривать дифференциальную игру на фиксированном отрезке времени [¿о! Пусть динамика системы определена уравнением x(t) = /(i, x(t), u(t), v(t)), t G [i0; Я (0.0.1) где x(t) - фазовый вектор системы, u(t),v(t) - управления игроков. Задано начальное состояние системы x(to) = xq. Управления игроков подчиняются геометрическим ограничениям u{t) G P(t), v(t) G Q(t), t G [t0; ??]. (0.0.2)

Задан функционал платы (функционал качества игры ) х)

J = 7(х(0)) + J ф, x(t), u(t), v(t)) dt. (0.0.3) to в

Здесь 7(a;(i9)) - терминальное слагаемое, f cp(t, x(t), u(t), v(t)) dt - интегральное слагаемое функционала качества.

Цель игрока и состоит в минимизации значения функционала 3, цель игрока v - в максимизации этого значения.

В другой постановке вместо функционала платы задано терминальное множество М. Цель игрока и состоит в приведении фазового вектора на множество М в конечный момент времени: £($) Е М; цель игрока V - противоположная: ^ М. Заметим, что дифференциальную игру с терминальным множеством можно рассматривать как игру с терминальным функционалом платы

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

Если определены функции iipos(i, я), ^pos(i,:r) и в каждый момент времени t Е [¿о!^] игроки строят свои управления по закону = upos(t, x(t)), v(t) = ^pos(i, x(t)), то будем говорить, что определены позиционные стратегии игроков. Стратегия, при которой игроки перед началом игры определяют свои управления как функции времени u(t), v(t), называются программной стратегией. Стратегия, при которой строится разбиение отрезка времени ¿о < h < • • • < tic = $ и на каждом отрезке [i^ifc+i] в зависимости от x(tk) строятся программные стратегии u{t), v(t), называется кусочно-программной стратегией.

Разумеется, при определении той или иной стратегии нужно требовать существование решения дифференциального уравнения (0.0.1) и выполнение ограничений (0.0.2).

Большинство современных алгоритмов, исследующих дифференциальные игры, используют следующий метод стабильного моста H.H. Красовского [81]. Сначала вычисляется функция цены игры Q(to,Xo), значение которой равно оптимальному гарантированному реt0

Е М х($) <£ М. t'e[t0-t]. зультату в игре с начальным условием x(to) = xq. Для дифференциальной игры с терминальным множеством вместо функции цены игры вычисляется альтернированный интеграл Л.С. Понтрягина [147]. Затем на основе вычисленной функции цены игры или альтернированного интеграла строятся оптимальные гарантированные стратегии управлений. В работах Н.Д. Боткина [12, 13, 14, 15, 16, 202], М.А. Зарха [34, 35, 36], В.М. Кейна [13, 63, 202], А.Ю. Коврижных [66, 67], Р.В. Константинова [70, 135], С.С. Кумкова [84, 85], М.Д. Локшина [95], Н.Ю. Луко-янова [96, 97, 98], B.C. Пацко [13, 35, 63, 85, 202, 234], А.П. Пономарева [139, 140, 141], Е.В. Сидоровой и H.H. Субботиной [160], Д.Б. Силина [161, 162], A.M. Тарасьева [122,176, 177, 178, 179], В.Е. Третьякова [80], В.Л. Туровой [63, 182, 202], A.A. Успенского [122, 178], В.И. Ухоботова [3, 106, 183, 184], В.Н. Ушакова [73, 176, 177,178,179,185, 186, 187, 188], А.П. Хрипунова [177, 179, 187, 190], A.A. Чикрия [154, 196, 197, 206] и других предложены алгоритмы, вычисляющие цену игры или альтернированный интеграл и строящие оптимальные гарантированные стратегии.

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

Для расширения области практического применения аппарата теории дифференциальных игр требуется найти такие математические постановки, которые охватывают широкие классы реальных задач и в то же время допускают эффективное их решение. В виду сложности и многообразия практических задач, по-видимому не существует единого алгоритма решения, подходящего сразу для всех классов дифференциальных игр. Различные авторы рассматривают разные по общности классы дифференциальных игр, предлагая для них алгоритмы различной эффективности [1, 3, 4, 17, 37, 69, 83, 92, 100, 119, 120, 121, 158,

164, 163, 182, 183, 184, 210, 221, 226, 227, 237, 238, 239, 242].

Среди достаточно широких классов дифференциальных игр первое место по эффективности алгоритмов решения занимает класс линейно-квадратичных игр, то есть игр (0.0.1)—(0.0.3), для которых динамика линейна, геометрические ограничения на управления отсутствуют, функционал платы является квадратичной формой относительно фазового вектора и управлений игроков. Известно [81, с.159], что для линейно-квадратичной дифференциальной игры оптимальные гарантированные позиционные стратегии игроков определяются формулами роз (Ъх) = К^х, Уроц(г,х) = К2(Ь)х, (0.0.4) где матрицы К\({), .Кг 00 определяются путем решения матричного дифференциального уравнения Риккати. Простота реализации алгоритма решения линейно-квадратичных дифференциальных игр позволяет довольно широко применять этот алгоритм на практике [11, 155, 205, 208, 225].

Существенным ограничением применимости линейно-квадратичной постановки является принципиальная невозможность учитывать геометрические ограничения на управления игроков, так как, согласно формулам (0.0.4), оптимальные управления неограниче-ны, если фазовый вектор неограничен.

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

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

Наряду с традиционным математическим аппаратом в нашем исследовании дифференциальных игр принципиальное значение имеет аппарат сильно и слабо выпуклого анализа, в том числе результаты, полученные в первых главах диссертации. Действительно, для линейной дифференциальной игры с терминальным функционалом платы функцию цены игры можно определить в терминах эпи-операций с функциями (см. §4.1), а для линейной игры с терминальным множеством альтернированный интеграл определяется через геометрические операции с множествами (см. §4.3). Свойства геометрических операций с множествами и эпи-операций с функциями, изученные в первых двух главах диссертации, используются в последующих главах при анализе дифференциальных игр.

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

В главе 5 рассматривается класс линейных дифференциальных игр на фиксированном отрезке времени с эллипсоидальным функционалом платы. Этот класс игр охватывает задачи, предполагающие как жесткие ограничения на управления игроков, так и требования по минимизации расходов на управления. Известные классы дифференциальных игр, такие как линейные игры с квадратичным критерием качества и линейные игры с эллипсоидами в качестве терминального множества и допустимых множеств управлений игроков, рассматриваемые в методе эллипсоидов А.Б. Куржанского, являются предельными случаями ДИ данного класса. Введено понятие ^-стратегической функции, которое выражает свойство ^-стабильности для эллипсоидальных функций. Приведен эффективный алгоритм вычисления и-стратегической функции, основанный на методе эллипсоидов A.B. Куржанского. Основной результат главы состоит в том, что гарантированная позиционная стратегия игрока и определяется некоторой явной формулой через u-стратегическую функцию. Приведено доказательство указанного результата, основанное на теореме выживания для дифференциальных уравнений.

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

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

Работа состоит из введения, 7 глав, разделенных на 48 параграфов, заключения, списка литературы (242 наименования), списка обозначений и предметного указателя, всего - 383 страницы. В начале каждой главы приводится краткое изложение ее основных результатов. В диссертации доказано 76 теорем и 167 лемм, приведено 62 определения и 23 предложения. Предложения здесь - это известные результаты, формулировки которых важны для изложения материала.

Основной материал диссертации опубликован в работах [4160,135,217,218].

Результаты диссертации докладывались на ежегодной Воронежской математической школе "Понтрягинские чтения" (1994, 1995, 2004гг.), Международной конференции 1998г., посвященной 90-летию со дня рождения J1.C. Понтрягина, научных конференциях и семинарах Московского физико-технического института (МФТИ), научных семинарах Института математики и механики Уральского отделения РАН (рук. проф. В.Н. Ушаков), кафедры системного анализа факультета вычислительной математики и кибернетики, МГУ (рук. академик РАН A.B. Куржанский), кафедры общих проблем управления механико-математического факультета МГУ (рук. проф. В.М. Тихомиров), а также использованы при чтении спецкурса "Новые результаты выпуклого анализа" для студентов и аспирантов МФТИ.

Автор выражает глубокую благодарность научному консультанту доктору физико-математических наук профессору Е.С. Половинкину, кандидатам физико-математических наук доцентам М.В. Балашову и Р.В. Константинову и другим сотрудникам кафедры высшей математики МФТИ за моральную поддержку при работе над диссертацией и полезное обсуждение полученных результатов.

Заключение

В работе получены следующие основные результаты: В теории выпуклого анализа .

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

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

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

В теории дифференциальных игр

• Доказана теорема о существовании седловой точки в классе программных стратегий для сильно выпукло-вогнутых дифференциальных игр. Для таких игр получен принцип минимакса, аналогичный принципу максимуму Л.С. Понтрягина.

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

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

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

1. Азамов A.A., Яхшимов Х.К. Задача качества для одной линейной дифференциальной игры с критическими свойствами. // Мат. заметки. 2000. 67. № 4. С.484-488.

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

3. Алеева С.Р., Ухоботов В.И. Однотипная игра с интегральным ограничением первого игрока. // Вестн. Челяб. ун-та. Сер. Мат. Мех. 1999. № 1. С.16-29.

4. Алеева С.Р. Стратегия преследования в дифференциальной игре "мальчик и крокодил" с интегральным ограничением. // Мат. структуры и моделир. 2000. № 6. С.55-61.

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

6. Балашов М.В., Иванов Г.Е. Сильная выпуклость множеств уровня сильно выпуклой функции. // Некоторые проблемы фундаментальной и прикладной математики. М.: МФТИ. 1996. С.35-45.

7. Балашов М.В. О максимизации выпуклой функции на компакте. // Некоторые проблемы фундаментальной и прикладной математики. М.: МФТИ. 1997. С. 17-25.

8. Балашов М.В., Половинкин Е.С. Сильно выпуклая оболочка и её свойства. // Некоторые проблемы фундаментальной и прикладной математики. М.: МФТИ. 1995. С.27-36.

9. Балашов М.В., Половинкин Е.С. М-сильно выпуклые множества n их порождающие подмножества. // Мат. сборник. 2000. 191. № 1. С.27-64.

10. Балашов М.В. Об аналоге теоремы Крейна-Мильмана для сильно выпуклой оболочки в гильбертовом пространстве. // Мат. заметки. 2002. 71. № 3. С.37-42.

11. Барабанов А.Е. Скользящий режим в решении линейно-квадратичной задачи. // Дифференц. уравнения. 1999. 35. № 11. С.1452-1459.

12. Боткин Н.Д. Оценка погрешности численных построений в дифференциальной игре с фиксированным моментом окончания. // Пробл. управл. и теории информ. 1982. 11. № 4. С.283-295.

13. Боткин Н.Д., Кейн В.М., Пацко B.C. Применение методов теории дифференциальных игр к задаче управления самолетом на посадке. // Позиционное управление с гарантированным результатом. Свердловск. 1988. С.33-44.

14. Боткин Н.Д., Красов А.И. Позиционное управление в модельной задаче о разбеге самолета. // Позиционное управление с гарантированным результатом. Свердловск. 1988. С.22-33.

15. Боткин Н.Д., Жуков С.П., Красов А.И. Комбинированный способ управления самолетом на посадке. // Управление в динамических системах. Свердловск. 1990. С. 18-30.

16. Боткин Н.Д., Рязанцева Е.А. Алгоритм построения множества разрешимости в линейной дифференциальной игре высокой размерности. // Тр. ин-та мат. и мех. УрО РАН. 1992. 2. С.128-134.

17. Брыкалов С.А. Непрерывные стратегии в дифференциальных играх. 2002. 38. № 4. С.453-459.

18. Гольштейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. / М.: Наука, 1989.19