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

• Иванов, Григорий Евгеньевич
• доктор физико-математических наук
• 2004

Оглавление диссертации доктор физико-математических наук Иванов, Григорий Евгеньевич

Введение

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. Куржанский), кафедры общих проблем управления механико-математического факультета МГУ (рук. проф. В.М. Тихомиров), а также использованы при чтении спецкурса "Новые результаты выпуклого анализа" для студентов и аспирантов МФТИ.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Иванов, Григорий Евгеньевич

Заключение

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

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

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

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

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

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

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

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

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

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

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