«КУМКОВ СЕРГЕЙ СЕРГЕЕВИЧ ОСОБЕННОСТИ МНОЖЕСТВ УРОВНЯ ФУНКЦИИ ЦЕНЫ В ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ ИГРАХ 05.13.18 математическое моделирование, численные методы и комплексы программ ДИССЕРТАЦИЯ на соискание ученой степени ...»

РОССИЙСКАЯ АКАДЕМИЯ НАУК

УРАЛЬСКОЕ ОТДЕЛЕНИЕ

ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

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

КУМКОВ СЕРГЕЙ СЕРГЕЕВИЧ

ОСОБЕННОСТИ МНОЖЕСТВ УРОВНЯ ФУНКЦИИ ЦЕНЫ

В ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ ИГРАХ

05.13.18 математическое моделирование, численные методы и комплексы программ

ДИССЕРТАЦИЯ

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

Научный руководитель:

кандидат физико-математических наук В.С.Пацко Екатеринбург Оглавление Введение Список обозначений 1 Узкие шейки в линейных дифференциальных играх 1.1 Линейные дифференциальные игры.............. 1.2 Построение множеств уровня функции цены......... 1.3 Задача воздушного перехвата.................. 1.3.1 Задача перехвата: случай быстрого преследователя. 1.3.2 Задача перехвата: случай медленного преследователя 1.4 Обобщенный контрольный пример Л.С.Понтрягина..... 1.4.1 Пример 1......................... 1.4.2 Пример 2......................... 1.4.3 Пример 3......................... 2 Уровневое выметание функции цены 2.1 Альтернированные суммы.................... 2.2 Связь операций над множествами и опорными функциями. 2.3 Локальная выпуклость

2.4 Разность выпуклых функций.................. 2.4.1 Контрпример к обобщению лемм 2.4.1 и 2.4.2. .... 2.5 Доказательство факта о сохранении уровневого выметания. 2.5.1 Сохранение полного выметания при алгебраической сумме........................... 2.5.2 Сохранение полного выметания при геометрической разности.......................... Оглавление 2.5.3 Контрпример к обобщению леммы 2.5.2........ 2.5.4 Сохранение полного выметания при предельном переходе........................... 3 Численное построение сингулярных поверхностей 3.1 Оптимальные движения..................... 3.2 Типы сингулярных поверхностей................ 3.3 Игры со скалярными управлениями.............. 3.3.1 Построение сингулярностей в случае скалярных ограничений.......................... 3.3.2 Пример 1: материальная точка на прямой....... 3.3.3 Пример 2: конфликтно-управляемый осциллятор... 3.3.4 Пример 3: кнопка

3.3.5 Сравнение с аналитическими результатами...... 3.3.6 Замечание к таблице классификации сингулярностей 3.3.7 Пример линии переключения за второго игрока с покиданием......................... 3.3.8 Уточнение таблицы классификации сингулярностей. 3.3.9 Структура сингулярных поверхностей......... 3.4 Игры с нескалярными управлениями............. 3.4.1 Построение сингулярностей в случае нескалярных ограничений........................ 3.4.2 Пример 1: задача воздушного перехвата........ 3.4.3 Пример 2: обобщенный контрольный пример Л.С.Понтрягина..................... Литература Список иллюстраций Введение Теория дифференциальных игр в настоящее время развитая математическая дисциплина. Первые отчеты Р.Айзекса по дифференциальным играм относятся к 1951-1954 годам [58, 59, 60, 61]. В 1965 году была опубликована его книга Дифференциальные игры, переведенная на русский язык в 1967 году [1]. В нашей стране динамические задачи конфликтного управления рассматриваются с начала 60-х годов прошлого века. Первыми были работы Л.С.Понтрягина [27, 28] и Н.Н.Красовского [12, 13].

В 1967 году вышли две знаменитые статьи [29, 30] Л.С.Понтрягина о линейных дифференциальных играх. В 1968 году опубликована книга [14] Н.Н.Красовского по оптимальному управлению, в заключительной части которой был большой раздел, связанный с дифференциальными играми. В 1974 году вышла книга Н.Н.Красовского и А.И.Субботина Позиционные дифференциальные игры. В ней, в частности, предложена позиционная формализация дифференциальных игр и доказана теорема об альтернативе, родственная теореме существования функции цены.

В эти же годы были опубликованы основополагающие работы [33, 34] Б.Н.Пшеничного о структуре дифференциальных игр.

Среди работ зарубежных авторов конца 60-х – начала 70-х годов прошлого века отметим работы L.D.Berkovitz [46], A.Blaqui`re [48], e J.V.Breakwell [50, 64], W.H.Fleming [56, 57], G.Leitmann [63]. В этих работах рассматривались теоремы существования функции цены в подходящем классе стратегий и развивался метод Айзекса решения дифференциальных игр при помощи построения сингулярных поверхностей.

Более поздние результаты, относящиеся к 1980-м годам, связаны с истолкованием функции цены игры как обобщенного решения уравнения Гамильтона–Якоби–Беллмана–Айзекса. Теория, опирающаяся на понятие шения было введено в работах M.G.Crandall и P.L.Lions [55]. В этом направлении интенсивно работают в настоящее время M.Bardi и I.CapuzzoDolcetta [43].

Параллельно с развитием теории разрабатывались и численные методы. Опыт создания первых универсальных алгоритмов решения некоторых классов дифференциальных игр отражен в сборнике [2], опубликованном в 1984 г. в Екатеринбурге. Большую роль в создании алгоритмов и их обосновании сыграли работы Н.Л.Григоренко, М.С.Никольского, В.С.Пацко, Е.С.Половинкина, В.Н.Ушакова. Соответствующие результаты изложены в работах [39, 38, 7, 72, 31, 19].

За рубежом численные методы интенсивно разрабатываются с начала 1990-х годов. В этой области проводят исследования итальянские математики M.Bardi, M.Falcone, P.Soravia [44, 43, 45]; французские P.Cardaliaguet, M.Quincampoix, P.Saint-Pierre [52, 53, 54]; немецкие M.H.Breitner, H.J.Pesch [51].

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

Стимулом этой модернизации явилось желание получить результаты счета с хорошей точностью, что позволило использовать современные методы научной компьютерной визуализации для адекватного представления результатов. Программы для визуализации решений дифференциальных игр были созданы в 1997–2000 годах в процессе совместной работы с В.Л.Авербухом, А.И.Зенковым, Д.А.Юртаевым (сектор компьютерной визуализации отдела системного обеспечения ИММ УрО РАН). Другим стимулирующим фактором явилась попытка создания алгоритмов и программ автоматического построения сингулярных поверхностей в указанном классе игр. Такие программы были созданы автором, и они базируются на программе построения множеств уровня функции цены.

Перейдем к изложению содержания диссертации по главам.

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

Далее рассматривается задача воздушного перехвата одного слабоманеврирующего объекта другим (ракеты или самолета антиракетой). Задача рассматривается в линеаризованной постановке. При помощи разработанной программы детально исследуются особенности множеств уровня функции цены. Изучаемые особенности заключаются в том, что t-сечения множеств уровня функции цены могут иметь пустую внутренность. Такое явление создает узкую шейку множества уровня. Адекватное воспроизведение формы множества уровня вблизи узкой шейки требует хорошей точности вычислений. Исследование узких шеек важно, поскольку значительная часть тонкостей решения дифференциальной игры (в частности, наличие сингулярных поверхностей) сосредоточена именно в районе узкой шейки. Некоторое теоретическое исследование дифференциальной игры, связанной с задачей перехвата, проводилось в работах J.Shinar и его сотрудников [70, 71, 67]. Результаты численных построений, приведенные в первой главе, сравниваются с результатами этих работ.

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

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

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

Рассмотрение сингулярных поверхностей составляет основу книги Р.Айзекса. Им предложена классификация сингулярных поверхностей:

экивокальные, рассеивающие, универсальные, поверхности переключения. Необходимые условия, связанные с различными типами сингулярных поверхностей, рассматривались в работах P.Bernhard [47] и А.А.Меликяна [66]. Автору неизвестны работы, в которых описывались бы численные алгоритмы автоматического глобального построения сингулярных поверхностей.

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

В настоящее время пока не удалось провести полное аккуратное обоснование разработанных алгоритмов. Однако правильность их работы тщательным образом проверялась на примерах, в которых сингулярные поверхности были исследованы аналитическими методами [22, 23, 70, 71].

На защиту выносятся следующие результаты:

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

2) формулировка и доказательство теоремы о свойстве уровневого выметания функции цены;

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

Список обозначений R+ множество положительных вещественных чисел R множество вещественных чисел, расширенное ± Rn евклидово пространство размерности n z фазовая переменная размерности n в исходной дифференциальной игре T момент окончания в рассматриваемых дифференциальных играх V(t, z) функция цены исходной дифференциальной игры Wc множество уровня функции цены исходной дифференциальной игры, соответствующее константе c X(T, t) фундаментальная матрица Коши исходной дифференциальной игры, вычисленная в момент t для момента окончания T Xi,j (T, t) матрица, составленная из i-й и j-й строк фундаментальной матрицы Коши X(T, t), соответствующих компонентам фазового вектора, определяющим эквивалентная фазовая переменная размерности V (t, ) функция цены эквивалентной дифференциальной Wc множество уровня функции цены эквивалентной дифференциальной игры, соответствующее константе c (l, A), A (l) значение опорной функции выпуклого компактного a, b скалярное произведение векторов a и b AT, a T транспонирование матрицы A или вектора a обратное время в рассматриваемых дифференциальных играх AB геометрическая разность множеств (разность Минковского) conv f операция взятия выпуклой оболочки функции f conv A f операция взятия выпуклой оболочки функции f на O (x0 ) открытая -окрестность точки x diam A, |A| диаметр множества A: |A| = sup x y N (t, x) конус внешних нормалей в точке (t, x) к временнму сечению W (t) соответствующего максимального стабильного моста W (множества уровня функции цены) P многогранная аппроксимация множества P ограничений на управление первого игрока Q многогранная аппроксимация множества Q ограничений на управление второго игрока Wc аппроксимация максимального стабильного моста Wc P(t) вектограмма первого игрока в момент t (точная или Q(t) вектограмма второго игрока в момент t (точная или nP (t) в случае скалярного управления первого игрока нормаль к отрезку его вектограммы в момент t nQ (t) в случае скалярного управления второго игрока нормаль к отрезку его вектограммы в момент t Глава Узкие шейки в линейных дифференциальных играх Исследуются четыре примера линейных антагонистических дифференциальных игр с геометрическими ограничениями на управления игроков, фиксированным моментом окончания и квазивыпуклой терминальной функцией платы. Предполагается, что функция платы зависит только от двух компонент фазового вектора в момент окончания. Это позволяет осуществить переход к эквивалентной игре с двумерным фазовым вектором.

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

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

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

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

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

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

1.1 Линейные дифференциальные игры Рассматривается линейная антагонистическая дифференциальная игра [16] с фиксированным моментом окончания T и квазивыпуклой непрерывной функцией платы, зависящей от двух компонент zi, zj фазового вектора. Квазивыпуклой называем такую функцию, все множества уровня которой выпуклые множества. Первый (второй) игрок распоряжается управлением u (v), выбирая его из выпуклого компакта P (Q) в своем конечномерном пространстве так, чтобы минимизировать (максимизировать) значение функции в момент T.

Известно [16], что такая игра обладает функцией цены V(t, z), которая является основным элементом решения. Знание функции цены позволяет получить оптимальные стратегии игроков, пучки оптимальных движений и др.

Одним из способов описания функции является представление ее припомощи множеств уровня. Для заданной константы c обозначим через множество уровня функции цены, соответствующее этой константе. В дальнейшем также будет использоваться обозначение временнго сечения (t-сечения) множества уровня в момент t: Wc (t) = z Rn : (t, z) Wc.

Удобство такого представления заключается в том, что вместо достаточно сложного объекта функции изучается более простой множество.

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

Используя линейность динамики игры (1.1) и тот факт, что ее функция платы терминальная и зависит лишь от двух компонент фазового вектора, можно понизить размерность задачи. Это производится при помощи замены переменных (см., например, [15, стр. 354], [4, стр. 334–335], [16, стр. 160]). Здесь новая фазовая переменная размерности 2, а Xi,j (T, t) матрица, составленная из i-й и j-й строк фундаментальной матрицы Коши X(T, t) для системы линейных дифференциальных уравнений z = A(t)z. Новая переменная (t) имеет смысл прогноза целевых i-й и j-й компонент фазового вектора z вдоль свободного движения системы (при нулевых управлениях u и v) на момент окончания T.

После применения указанной замены переменных приходим к игре с квазивыпуклой терминальной функцией платы 1 (T ), 2 (T ). Часто называется эквивалентным фазовым вектором, а игру (1.3) эквивалентной дифференциальной игрой. Символом V (t, z) обозначим функцию цены эквивалентной игры, а Wc множество уровня функции цены, соответствующее константе c.

По отношению к игре (1.3) термин эквивалентный означает, что если позиции t, (t) и t, z(t) игр (1.3) и (1.1) удовлетворяют соотношению (1.2), то значения V t, (t) и V t, z(t) функций цены этих игр совпадают.

Отметим, что если исходная игра уже имела двумерный фазовый вектор, то замена (1.2) является взаимно однозначной. В этом случае можно пересчитывать элементы решения эквивалентной игры (1.3) (множества уровня функции цены, оптимальные движения, сингулярные поверхности) в исходные координаты.

1.2 Построение множеств уровня функции цены Для линейных дифференциальных игр вида (1.1) в 1980–90-е годы в Институте математики и механики Уральского отделения Академии Наук были разработаны попятные алгоритмы построения множеств уровня функции цены [2, 38, 72]. Для случая игр вида (1.3) с двумерной фазовой переменной разрабатывались специализированные алгоритмы [9], использующие специфику задачи. Позже эти алгоритмы были улучшены автором диссертации, были разработаны их версии для параллельных вычислительных машин [82, 76, 77].

Ниже, следуя статье [9], будет вкратце изложен алгоритм построения набора многоугольников, приближающих сечения Wc (t) некоторого множества уровня Wc функции цены V (t, ) игры (1.3) на основе многоугольника, приближающего некоторое множество уровня M функции платы.

Пусть на промежутке [t0, T ] задано разбиение Разбиение не обязательно должно быть равномерным, но для простоты изложения положим, что все шаги i одинаковы и равны.

Заменим динамику (1.3) кусочно-постоянной динамикой = D(t)u + E(t)v, D(t) = D(ti ), E(t) = E(ti ) при t [ti, ti+1 ). (1.4) Вместо множеств P и Q будем рассматривать их многогранные аппроксимации P, Q. Пусть также аппроксимирующая функция платы, такая что для любого значения c ее множество уровня Mc = : () c, соответствующее этому значению, является выпуклым многоугольником.

Считаем, что аппроксимирующие множества P, Q, Mc близки в метрике Хаусдорфа к множествам P, Q, M, соответственно.

Аппроксимирующая игра (1.4) выбрана так, что на каждом шаге [ti, ti+1 ] попятной процедуры мы имеем игру с простыми движениями, выпуклыми многогранными ограничениями на управления игроков и выпуклым многоугольным целевым множеством. Положим Wc (tN ) = Mc. Далее найдем множество разрешимости Wc (tN 1 ) игры с простыми движениями, затем множество Wc (tN 2 ) и т.д. В качестве результата получим набор выпуклых множеств, которые приближают в метрике Хаусдорфа множество уровня Wc функции цены V (t, ) игры (1.3).

Обозначим P(ti ) = D(ti )P, Q(ti ) = E(ti )Q. Эти множества описывают возможные вклады игроков в скорость системы на очередном промежутке времени. В дальнейшем множества P(t) и Q(t) будут называться вектограммами первого и второго игрока в момент t, а множества трубками вектограмм.

Построения ведутся в терминах опорных функций многоугольников Wc (ti ), Wc (ti+1 ), P(ti ) и Q(ti ).

Напомним определение опорной функции. Пусть имеется выпуклое замкнутое множество A в пространстве Rn. Тогда оно взаимно однозначно сопоставляется [35] со своей опорной функцией A (·):

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

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

Опорная функция l l, Wc (ti ) множества Wc (ti ) совпадает [34] с выпуклой оболочкой функции Функция (·, ti ) является положительно-однородной и кусочно-линейной.

При этом свойство локальной выпуклости этой функции может нарушаться лишь на границе конусов линейности функции ·, Q(ti ), т.е. на границе конусов, порождаемых нормалями к ребрам многоугольника Q(ti ).

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

В дальнейшем аргумент ti в записи функции будет опускаться для упрощения записи. Вместо множеств P(ti ), Q(ti ) будем писать просто P, Q. Также вместо Wc (ti ) и Wc (ti+1 ) будем писать Wc и Wc, соответственно.

Конусы линейности функции определяются нормалями к выпуклым многоугольникам Wc, P, Q. Собирая внешние нормали к этим множествам и упорядочивая их по часовой стрелке, получим набор векторов L.

Набор значений (l) функции на векторах l L обозначим. Наборы L, полностью описывают функцию.

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

Положим L(1) = L, (1) =, S (1) = S. Шаг с номером (k + 1) процесса овыпукления заключается в замене наборов L(k), (k) некоторыми другими наборами L(k+1) L(k), (k+1) (k). При этом S (k) также подменяется новым набором S (k+1).

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

Возьмем вектор l S (k) и проверим локальную выпуклость функции (k) на конусе, порожденном вектором l и двумя соседними к нему векторами l и l+, взятыми по и против часовой стрелки из набора L(k). (Определение 2.3.1 локальной выпуклости дано в разделе 2.3 на стр. 51.) В силу того, что функция (k) является положительно-однородной на плоскости, проверка локальной выпуклости сводится к проверке, является ли неравенство l, y (l ) существенным в тройке неравенств l, y (l ), l, y (l ), l+, y (l+ ). Существенным называем такое неравенство, которое дает вклад в решение соответствующей системы неравенств. Иными словами, неравенство l, y (l ) существенно в этой системе, если для множества выполняется соотношение Заметим, что в силу упорядоченности векторов l, l, l+ лишь средний из них может быть несущественным.

Алгоритм проверки существенности: найдем точку y, в которой пересекаются прямые l, y = (l ) и l, y = (l ). Затем проверим неравенство l+, y < (l+ ). Если оно выполняется, то локальная выпуклость имеет место (среднее неравенство существенно). В противном случае, локальная выпуклость отсутствует (среднее неравенство не является существенным).

В случае существенности неравенства вектор l исключается из набора S (k). Полученное множество обозначается S (k+1). При этом L(k+1) = L(k), (k+1) = (k).

В противном случае возможны две ситуации. Обозначим через угол между векторами l и l+, отсчитываемый по часовой стрелке:

• <. Вектор l извлекается из набора S (k), и, одновременно, векторы l и l+ туда включаются. (При этом один из них или оба уже могут присутствовать в наборе S (k).) Полученный таким образом новый набор подозрительных векторов обозначается через S (k+1). Набор L(k+1) получается из L(k) исключением вектора l. Аналогично, при переходе от (k) к (k+1) из набора (k) выкидывается значение (k) (l ) = (l );

•. Данное неравенство означает, что рассматриваемая тройка неравенств несовместна. И, стало быть, выпуклая оболочка функции не существует, т.е. Wc =. Дальнейшие построения прекращаются. (Если =, то возможно, что Wc (ti ) является вырожденным многоугольником, т.е. Wc (ti ) – точка или отрезок. В этом случае дальнейшие построения также прекращаются.) Тем самым завершено описание одного шага овыпукления. Процесс завершается на шаге с номером j, когда впервые S (j) =, т.е. когда в первый раз множество подозрительных нормалей становится пустым. Последнее означает, что функция (j), определяемая наборами L(j) и (j), является локально выпуклой всюду. Таким образом, она и является выпуклой оболочкой функции. В этом случае обозначим окончательные наборы L(j) и (j) через L и, соответственно. Другой вариант завершения процедуры:

на каком-то шаге угол между векторами l и l+ становится больше или равным после исключения проверяемого вектора l из набора подозриi тельных векторов. Это означает, что Wc =.

Доказательство сходимости алгоритма и оценки погрешности приведены в [49, 3]. Сходимость аналогичных схем обоснована в [26].

1.3 Задача воздушного перехвата Множества уровня функции цены игры (1.3) могут быть представлены как трубки в пространстве фазовые переменные (1, 2 ) время t. Такие трубки начинаются на множестве уровня функции платы и тянутся обратно во времени. При этом возможны различные ситуации: множество уровня тянется бесконечно во времени, или же оно может в какой-то момент обрываться.

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

В работах [70, 71, 67] рассматривалась трехмерная задача воздушного перехвата, сформулированная в виде игры преследования-уклонения. Преследователем выступала ракета-перехватчик, убегающим маневренная воздушная цель (самолет или другая ракета). Естественной платой в такой игре является расстояние наименьшего сближения, т.е. промах, который минимизируется преследователем и максимизируется убегающим. Векторы номинальных скоростей (VP )nom и (VE )nom являются постоянными и направленными так, что имеется точная встреча на номинальных траекториях. Управляющее ускорение каждого объекта перпендикулярно вектору его текущей скорости. Максимальные значения боковых ускорений Рис. 1.1: Система координат в задаче трехмерного преследования ограничены константами aP и aE. Полагается, что aP > aE. Убегающий непосредственно управляет своим ускорением, а догоняющий инерционно, с постоянной времени P.

Выбор координат производится следующим образом. Начало координат O совмещается с номинальным положением Pnom догоняющего в начальный момент. Ось OX направлена вдоль начальной номинальной линии визирования. Ось OY перпендикулярна OX и лежит в плоскости, определяемой векторами номинальных скоростей объектов (рис. 1.1).

Ось OZ направлена перпендикулярно первым двум осям.

Как отмечено, начальные условия таковы, что на номинальных курсах существует точное сближение:

Также полагаем, что реализации векторов скоростей преследователя VP (t) и убегающего VE (t) близки к номинальным значениям (VP )nom и (VE )nom, соответственно. Такое предположение разумно, поскольку время сближения мало (скорость сближения весьма велика) и за это время боковые управляющие ускорения не успевают существенно развернуть векторы скоростей. Иными словами, объекты являются слабо маневрирующими.

Считается, что выполняются соотношения Принимая во внимание предположения (1.7) и (1.8), относительные траектории могут быть линеаризованы вдоль начальной линии визирования (оси OX). Более того, относительное движение вдоль оси OX может рассматриваться как равномерное. Таким образом, от начального трехмерного движения можно перейти к двумерному в плоскости Y Z. Для заданного начального расстояния равномерная скорость сближения определяет время T номинальной встречи. И, стало быть, задача минимизации трехмерного промаха в нефиксированный момент времени сводится к минимизации (максимизации) расстояния в плоскости Y Z в зафиксированный момент номинальной встречи.

Поскольку, вообще говоря, векторы номинальных скоростей (VP )nom и (VE )nom неколлинеарны линии визирования в начальный момент, то проекции в плоскость Y Z исходных круговых ограничений на управления игроков, перпендикулярных соответствующим векторам, становятся эллипсами. Эксцентриситеты этих эллипсов определяются величинами cos(P )nom и cos(E )nom, а поскольку углы (P )nom и (E )nom различны, то и эксцентриситеты будут разными.

Таким образом, получаем следующую линейную дифференциальную игру:

Здесь x вектор положения первого (догоняющего) игрока, y вектор положения второго (убегающего) игрока, P постоянная времени, характеризующая инерционность отработки управления первого игрока. Множества P и Q, ограничивающие управления первого и второго игроков соответственно, являются эллипсами:

AP BP A E BE

Полуоси AP, BP, AE, BE параллельны координатным осям и вычисляются на основе ограничений aP, aE на ускорения игроков и косинусов угЗадача воздушного перехвата лов (P )nom и (E )nom. Момент окончания игры предполагается фиксированным. Платой является геометрическое расстояние между объектами в момент окончания.

Исключая компоненту F в динамике (1.9) и обозначая = 1/P, приходим к следующему виду динамики:

Чтобы привести динамику (1.10) к виду (1.1), произведем замену Получаем игру в стандартной форме (1.1):

В таком виде линейная дифференциальная игра с фиксированным моментом окончания записана в [70].

В работах [70, 71] явно производился переход от игры (1.12) к эквивалентной игре вида (1.3). В силу блочности матриц A, B и C матрицы D(t) и E(t) в динамике эквивалентной игры (1.3) приобретают вид где I2 единичная матрица размера 2 2. В целом эквивалентная игра будет выглядеть как Для того, чтобы малый промах был достижим, преследователь должен иметь преимущество в управлении. Это означает, что множество P, ограничивающее управление преследователя, должно полностью содержать ограничение Q управления убегающего. Иными словами, должны выполняться неравенства описывающие отношение полуосей эллипсов P и Q. Такое преимущество позволяет преследователю уменьшить начальный промах (если такой есть) и парировать маневры убегающего в процессе сближения. Однако в силу инерционности отработки управления преследователя и безынерционности динамики убегающего нулевой промах не может быть достигнут при условии оптимальности стратегии убегающего.

В работах [70, 71, 67] приведено аналитическое исследование дифференциальной игры (1.13)–(1.15). На качественном уровне изучены структура сингулярных поверхностей и геометрия множеств уровня функции цены.

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

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

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

При численных построениях мы конструируем множества уровня функции цены на некотором конечном промежутке времени [t, T ]. Определение критического множества при этом можно дать следующим образом: множество уровня функции цены с непустыми t-сечениями на [t, T ] назовем 1.3.1. Задача перехвата: случай быстрого преследователя критическим, если оно имеет на интервале (t, T ) хотя бы одно t-сечение с пустой внутренностью.

1.3.1 Задача перехвата: случай быстрого преследователя Первый, более простой случай задачи (1.12) соответствует ситуации, когда скорость (VP )nom преследователя превосходит скорость (VE )nom убегающего. Геометрия номинального перехвата для этого случая изображена на рис. 1.2.

Соотношение (1.6), определяющее наличие номинального перехвата, вместе с неравенством (VP )nom > (VE )nom влечет, что экцентриситет эллипса P меньше эксцентриситета эллипса Q (см. рис. 1.3).

Для численного исследования были взяты следующие данные:

Следовательно, эллиптические ограничения на управления игроков описываются как Ниже, символом будет обозначаться обратное время задач (1.1) и (1.3): = T t.

Рис. 1.2: Геометрия номинального перехвата для случая быстрого преследователя 1.3.1. Задача перехвата: случай быстрого преследователя Рис. 1.3: Эллиптические ограничения на управления игроков в случае быстрого преследователя. Эллипс P изображен красным цветом, Q зеленым. Эксцентриситет эллипса P меньше, чем эксцентриситет Q Пример был просчитан на интервале времени [0, 2] обратного времени. Шаг по времени был взят равным 0.025. Круги множеств уровня платы и эллипсы P, Q ограничений на управления игроков подменялись соответствующими 100-угольниками.

Рис. 1.4 представляет трубки вектограмм. Трубка вектограмм первого игрока изображена голубым цветом, второго пурпурным.

Увеличенная часть предыдущего рисунка для другой точки зрения приведена на рис. 1.5. На трубке вектограмм второго игрока нанесены контуры Рис. 1.4: (слева) Трубки вектограмм для случая быстрого преследователя Рис. 1.5: (справа) Увеличенный фрагмент трубок вектограмм. Первый игрок получает преимущество в горизонтальном направлении в момент и полное преимущество в момент 1.3.1. Задача перехвата: случай быстрого преследователя t-сечений.

Поскольку Q(t) = E(t)Q = (t)I2 Q = (t)Q, где (·) описывается соотношением (1.14), пурпурная трубка расширяется линейно по. Для трубки P имеем P(t) = (t)P, где (·) берется из (1.13). Поэтому вначале (для малых значений обратного времени ) голубая трубка растет медленнее, чем линейно, но для бльших значений рост становится почти линейным, и эта трубка расширяется быстрее, чем Q. Более быстрый рост обуславливается неравенствами (1.16).

Итак, имеем, что при < второй игрок (убегающий) имеет полное преимущество, т.е. его вектограмма Q( ) для этих моментов обратного времени полностью покрывает вектограмму первого игрока P( ) (рис. 1.6а).

Момент определяется тем, что горизонтальные размеры эллипсов P( ) и Q( ) совпадают (рис. 1.6б). На промежутке < < ни один из игроков не имеет полного преимущества: первый игрок сильнее в горизонтальном направлении, а второй в вертикальном (рис. 1.6в). Когда =, вертикальные размеры эллипсов становятся равными (рис. 1.6г), и для > первый игрок получает полное преимущество (рис. 1.6д). Такое поведение вектограмм P( ) и Q( ) объясняется соотношением эксцентриситетов, размеров эллипсов ограничений P, Q и видом функций (t), (t).

Переход преимущества от второго игрока к первому приводит к появлению узкой шейки. Рис. 1.7 содержит изображение множества уровня, близкого сверху к критическому. Это множество уровня соответствует значению c = 0.141. Узкая шейка расположена около момента = 0.925.

Рис. 1.6: Сечения трубок вектограмм в некоторые моменты времени. Сечения трубки вектограмм первого игрока нарисованы голубым цветом, второго пурпурным.

Рис. 1.7: Множество уровня, близкое сверху к кртическому, c = 0.141. Момент наиболее узкого сечения = 0. Рис. 1.8: Увеличенный фрагмент множества уровня, близкого к критическому для начального промежутка обратного времени; нанесены контуры некоторых t-сечений 1.3.1. Задача перехвата: случай быстрого преследователя Рис. 1.9: Наложение трубок вектограмм. Трубка второго игрока изображена прозрачной Рис. 1.10: Наложение трубок вектограмм и множества уровня, близкого к критическому. Трубки вектограмм изображены прозрачными 1.3.2. Задача перехвата: случай медленного преследователя Крупный фрагмент узкой шейки изображен на рис. 1.8. Показаны контуры некоторых t-сечений. Можно видеть, что сечения Wc (t) множества уровня около узкой шейки вытянуты горизонтально. Это происходит в силу имеющегося соотношения возможностей игроков. При < второй игрок в вертикальном направлении более силен, чем в горизонтальном. Поэтому сечения Wc (t) по вертикали сжимаются сильнее. Когда немногим больше, первый игрок получает преимущество по горизонтали (рис. 1.6в), что приводит к растяжению сечений в горизонтальном направлении. Для достаточно больших значений обратного времени преимущество первого игрока по вертикали становится больше, чем преимущество по горизонтали, t-сечения начинают по вертикали расти быстрее, чем по горизонтали и в какой-то момент становятся вытянутыми вертикально.

Для представленного примера вертикальная вытянутость t-сечения множества уровня появляется уже вне промежутка времени, для которого приведены изображения на рис. 1.7, 1.8.

Следующий рисунок 1.9 опять показывает трубки вектограмм игроков.

Трубка вектограмм второго игрока сделана прозрачной. Ось обратного времени идет справа налево, ось 2 направлена вверх. Ось 1 направлена на читателя перпендикулярно листу.

Для той же точки зрения приведена (рис. 1.10) сцена, содержащая в дополнение к трубкам вектограмм множество уровня, близкое к критическому. Обе трубки вектограмм сейчас сделаны прозрачными. Наложение трубок и множества уровня ясно показывает влияние отношения вектограмм игроков на изменение размеров и геометрии сечений множества уровня. Например, можно видеть, что в момент получения первым игроком полного преимущества (момент = 0.925) узкая шейка прекращается и начинается расширение множества уровня. Также можно видеть, что до этого трубка сжимается вследствие преимущества второго игрока (полного или частичного).

Результаты численного исследования, приведенные в этом параграфе, качественно согласуются с теми, которые были получены в результате аналитического исследования в работах [70, 67].

1.3.2. Задача перехвата: случай медленного преследователя 1.3.2 Задача перехвата: случай медленного преследователя В этом параграфе приводятся результаты численного исследования задачи воздушного перехвата (1.14)–(1.15) для случая медленного преследователя: (VP )nom < (VE )nom. Геометрия номинальных траекторий выглядит так, как это показано на рис. 1.1. Эксцентриситет эллипса P в рассматриваемой ситуации больше экцентриситета Q (см. рис. 1.11).

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

Эти данные определяют такие параметры системы: = 1/P = 1, Пример просчитывался на промежутке обратного времени [0, 7] с шагом = 0.01. Круги множеств уровня функции платы и эллипсы ограничений P, Q на управления игроков приближались 100-угольниками.

Так же, как и в примере из предыдущего параграфа, здесь тоже имеется узкая шейка. На рис. 1.12 можно видеть общий план множества уровaP Рис. 1.11: Эллиптические ограничения на управления игроков в случае медленного преследователя. Эллипс P изображен красным, Q зеленым. Эксцентриситет эллипса P больше, чем эксцентриситет Q 1.3.2. Задача перехвата: случай медленного преследователя Рис. 1.12: Общий вид множества уровня функции цены с узкой шейкой ня Wc, соответствующего значению c = 1.546, которое чуть больше критического. В отличие от примера, описанного в параграфе 1.3.1, здесь узкая шейка имеет более сложную структуру: направление вытянутости t-сечений меняется весьма хитрым образом. Крупный план узкой шейки изображен на рис. 1.13.

1.3.2. Задача перехвата: случай медленного преследователя Для объяснения формы сечений множества уровня вблизи узкой шейки опять обратимся к трубкам вектограмм игроков. Трубки вектограмм показаны на рис. 1.14. Трубка вектограмм первого игрока (P) изображена красным цветом, второго (Q) зеленым. В рассматриваемом случае трубка Q растет линейно по, в то время как трубка P растет медленнее, чем линейно, для малых значений обратного времени и становится почти линейной по времени при больших значениях обратного времени. В конце концов, для больших моментов трубка P растет быстрее, чем Q, в силу соотношений (1.16).

Поскольку эллипсы P и Q имеют разные эксцентриситеты, вектограмма первого игрока P( ) начинает покрывать вектограмму второго игрока Q( ) по различным направлениям в различные моменты времени.

Так, при < = 4.18 эллипс Q( ) полностью включает эллипс P( ) (рис. 1.15а). В некоторый момент = размеры эллипсов совпадают по вертикали (рис. 1.15б). На интервале < < эллипс P( ) все больше и больше захватывает эллипс Q( ). И, наконец, в момент = = 5.3 множество P( ) покрывает Q( ) и по горизонтали (рис. 1.15в). Для >, множество P( ) полностью покрывает множество Q( ) (рис. 1.15г).

Описанное соотношение между вектограммами игроков объясняет специфическое изменение t-сечений около узкой шейки, что показано на рис. 1.12, 1.13 и 1.16. Последний рисунок содержит группы сечений на различных интервалах для показа различных фаз изменения формы сечений.

При < второй игрок имеет полное преимущество над первым.

Поскольку в обратном времени второй игрок пытается сжать множество уровня функции цены, то t-сечения трубки Wc сокращаются на интервале 0 < <. На рис. 1.16а эти сечения показаны для интервала [0, 3.8]. Поскольку преимущество второго игрока больше в вертикальном направлении, то трубка множества уровня сжимается больше по вертикали. Поэтому к моменту = сечения становятся вытянутыми по горизонтали.

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

1.3.2. Задача перехвата: случай медленного преследователя Рис. 1.14: Общий вид трубок вектограмм первого (1) и второго (2) игроков. Трубка вектограмм второго игрока изображена прозрачной, показаны контуры некоторых t-сечений Рис. 1.15: Сечения трубок вектограмм для некоторых моментов времени. Вектограммы первого игрока изображены красным, второго зеленым Рис. 1.16: Группы t-сечений множества уровня, близкого к критическому для некоторых промежутков обратного времени: а) [0, 3.8]; б) [, ]; в) [, ];

г) [5.41, 7.0] Между и = 4.95 сечения имеют форму криволинейного прямоугольника, как это показано на рис. 1.16б. Форма сечения постепенно меняет свою вытянутость с горизонтальной на вертикальную.

В момент горизонтальная дуга полностью пропадает, и форма t-сечения напоминает вертикальную линзу. В этот же момент вертикальное растяжение сменяется сжатием, несмотря на преимущество первого игрока в вертикальном направлении (рис. 1.16в), поскольку сжатие в горизонтальном направлении (вызванное преимуществом второго игрока в 1.3.2. Задача перехвата: случай медленного преследователя Рис. 1.17: Сокращение размера t-сечения по вертикали вследствие сжатия по горизонтали горизонтальном направлении) приводит к сжатию и по вертикали из-за такой формы сечений. Сказанное поясняется на рис. 1.17. Боковые дуги предыдущего сечения Wc (i ) увеличиваются по вертикали под действием первого игрока и сближаются под действием второго. Следующее сечение Wc (i+1 ) ограничено пересечением новых дуг.

Наконец, в момент =, когда первый игрок получает полное преимущество, множество уровня имеет наиболее узкое сечение (рис. 1.13 и 1.16в), которое вытянуто по вертикали. При > первый игрок продолжает обладать полным преимуществом, и t-сечения множества уровня начинают монотонно расти по всем направлениям. Однако скорость роста по разным направлениям неодинакова, хотя сечения сохраняют вертикальную вытянутость (рис. 1.16г).

Следующие два рисунка показывают множество уровня функции цены, близкое к критическому, в сравнении с соседними множествами уровня. Первый из них рис. 1.18 показывает критическую трубку (прозрачная, изображена желтым цветом) и трубку, просчитанную для значения c = 1.48 функции платы, которое меньше, чем критическое. Трубка обрывается (конечна во времени) и изображена красным цветом. На рис. 1.19 представлены критическая трубка (красная) и трубка, просчитанная для значения c = 1.67 (на рисунке прозрачная желтая). Видно, что большее множество имеет гладкую границу. Это означает, что именно около узкой шейки сосредоточены нерегулярности функции цены. Чтобы правильно отразить их, нужны очень аккуратные вычисления в районе узкой шейки.

Отметим, что строение узкой шейки, описанное в этом параграфе, типично для ситуации медленного преследователя. Конечно, при изменении Рис. 1.18: Множество уровня с узкой шейкой, просчитанное для значения c = 1.546, (желтое прозрачное) и множество уровня, просчитанное для меньшего значения c = 1.48 (красное) Рис. 1.19: Множество уровня с узкой шейкой, просчитанное для значения c = 1.546, (красное) и множество уровня, просчитанное для большего значения c = 1.67 (желтое прозрачное) параметров задачи длительность узкой шейки во времени и размеры tсечений в районе шейки будут меняться.

1.4 Обобщенный контрольный пример Л.С.Понтрягина В работах [27, 28] в качестве иллюстрации к теоретическим результатам был взят пример следующей дифференциальной игры двух лиц Здесь, положительные константы, x, y положения объектов, u, v управляющие воздействия первого и второго игроков. Под окончанием игры понимается совпадение геометрических координат x = y. Первый игрок минимизирует время поимки, второй препятствует этому.

Позже дифференциальные игры с такой или более общей линейной динамикой двух объектов и с условием окончания в терминах геометрических координат стали называть контрольным примером Л.С.Понтрягина (иногда обобщенным контрольными примером [18, 42]). Контрольный пример использовался во многих исследованиях [18, 42, 8, 6, 25, 41, 24] для проверки работоспособности теоретических методов. Имеются работы [17, 5], посвященные изучению конкретно этого примера.

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

В разделе рассматривается линейная дифференциальная игра вида обобщающая пример (1.17). Здесь ai, bj константы, T фиксированный момент окончания, u, v управляющие воздействия первого и второго игроков, выбираемые из выпуклых компактов P и Q. Терминальное множество Mc задается соотношением Mc = (x, y) : |x y| c. Первый игрок стремится привести движение системы на терминальное множество Mc в момент T, второй препятствует этому. Именно эту игру чаще всего называют обобщенным контрольным примером Л.С.Понтрягина.

Заметим, что пример, изучавшийся в предыдущих трех параграфах, имеет динамику (1.10) вида (1.18), (1.19).

Сделаем замену переменных Несложно проверить, что в новых переменных динамика игры запишется в стандартной форме (1.1). Ограничения на управления имеют прежний вид u P, v Q. Терминальное множество записывается теперь через новые координаты в виде Mc = z : z1 + z2 c.

Следует отметить, что замена (1.20) имеет несколько другую структуру, чем замена (1.11), использованная при изучении примера (1.10). Однако в силу того, что целевыми компонентами фазового вектора (определяющими значение функции платы) в обоих случаях будут разностные геометрические координаты, то после замены (1.2) и в рассматриваемом примере эквивалентная игра будет также иметь матрицы D(t) и E(t) вида (1.13), (1.14), т.е. D(t) = (t) · I2, E(t) = (t) · I2. Пояснить это явление можно тем, что в системе (1.3) матрица D(t) (и функция (t)) целиком определяется коэффициентами уравнения (1.18), матрица E(t) (и функция (t)) коэффициентами уравнения (1.19). Стало быть, динамика первой и второй компонент эквивалентного фазового вектора будет идентична, что и приводит к появлению матриц D(t) и E(t) указанного вида.

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

1.4.1 Пример Динамика игры описывается соотношениями Первый игрок управляет материальной точкой, движущейся в плоскости.

Второй управляемый объект двумерный математический маятник. В обоих случаях присутствует трение, пропорциональное скорости. Ограничения на управления игроков выбраны в виде эллипсов Терминальное множество M после перехода к эквивалентным координатам является кругом радиуса c с центром в нуле.

На рис. 1.20а показаны развернутые в обратном времени вектограммы P(t) и Q(t) первого и второго игроков. Поскольку динамика второго игрока описывает осциллирующую систему, то характер преимущества одного игрока над другим меняется во времени. В начале обратного времени второй игрок имеет полное преимущество над первым, но для достаточно больших моментов обратного времени преимущество получает первый игрок. Увеличенный фрагмент трубок вектограмм приведен на рис. 1.20б.

На рис. 1.21 показан стабильный мост Wc для c = 2.45098. Этот мост обрывается (конечен во времени). Перед обрывом ориентация вытянутости меняется. А именно, до последней шейки сечения моста вытянуты по вертикали, а после нее по горизонтали. Изменение характера вытянутости происходит вследствие взаимодействия вектограмм P(t) и Q(t) в районе этой шейки.

С увеличением значения c протяженность стабильного моста во времени резко возрастает. Стабильный мост для c = 2.45100 показан на рис. 1.22.

На рис. 1.23 приведен его увеличенный фрагмент в районе узкой шейки, возникающей при = 11.95. Указанное значение параметра c можно считать критическим: при c < 2.45100 мост обрывается, при c 2. обрыва не происходит.

Для достаточно больших значений c структура мостов упрощается.

Рис. 1.24 содержит вид моста для c = 3.87300.

Рис. 1.20: Пример 1. Эллиптические вектограммы первого (1) и второго (2) игроков:

а) общий вид; б) увеличенный фрагмент, вид сбоку Рис. 1.21: Пример 1. Конечный во времени максимальный стабильный мост, c = 2. Рис. 1.22: Пример 1. Максимальный стабильный мост с узкой шейкой, c = 2. Рис. 1.23: Пример 1. Увеличенный фрагмент шейки, c = 2. Рис. 1.24: Пример 1. Максимальный стабильный мост для значения параметра c, большего критического: c = 3. Счет примера производился на промежутке обратного времени [0, 20]. Шаг по времени = 0.05. Круги терминальные множества M подменялись правильными 100-угольниками, эллипсы P и Q ограничений на управления игроков многоугольниками с 100 вершинами.

1.4.2 Пример Динамика игры имеет вид Ограничения на управления игроков выбраны в виде одинаковых эллипсов Терминальное множество M (в эквивалентных координатах) выбрано в виде круга радиуса c = 1.2.

Поскольку множества P и Q совпадают, то в каждый момент времени эллипсы P(t) и Q(t) подобны: P(t) = |(t)|·P, Q(t) = |(t)|·P. (О подобии имеет смысл говорить, когда ни одно из множеств P(t) или Q(t) не обращается в точку.) Если есть преимущество первого игрока, т.е. |(t)| |(t)|, то процедура овыпукления при построении мостов не прорабатывает в такие моменты времени функция (·, t) получается выпуклой. Если же преимущество имеет второй игрок, т.е. |(t)| < |(t)|, то овыпукление происходит.

На рис. 1.25 и 1.26 показаны трубки вектограмм. Рис. 1.26 отличается от рис. 1.25 тем, что трубка вектограмм второго игрока сделана прозрачной.

На рис. 1.27 приведен общий вид просчитанного стабильного моста. На рис. 1.28 показан более крупно фрагмент первой шейки. Моменты наиболее узких частей шеек 1 = 8.50 и 2 = 11.30.

Счет примера производился на промежутке обратного времени [0, 16]. Шаг по времени = 0.05. В районе шеек шаг измельчался в раз: = 0.005. Количество вершин аппроксимирующих многоугольников было таким же, что и для первого примера.

Рис. 1.25: Пример 2. Вектограммы игроков: 1 первого, 2 второго Рис. 1.26: Пример 2. Вектограммы игроков: 1 первого, 2 второго. Трубка вектограмм второго игрока сделана прозрачной Рис. 1.27: Пример 2. Общий вид максимального стабильного моста с двумя узкими шейками Рис. 1.28: Пример 2. Вид первой узкой шейки максимального стабильного моста Отметим еще раз, что несмотря на подобие вектограмм игроков (множеств P(t) и Q(t)) отсутствует подобие вектограмм и сечений Wc (t). Это приводит к нарушению однотипности задачи в целом и, следовательно, к появлению узких шеек со сложной структурой.

1.4.3 Пример Динамика игры описывается соотношениями Ограничения на управления игроков взяты в виде эллипсов Терминальное множество M после перехода к эквивалентным координатам является кругом с центром в нуле радиуса c = 0.3970.

Вектограммы, возникающие в этом примере, приведены на рис. 1.29.

Множество уровня Wc функции цены игры, соответствующее c = 0.397, показано на рис. 1.30а. Видны три узкие шейки, возникающие при значениях обратного времени 1 = 6.05, 2 = 9.35 и 3 = 12.70. Крупный план Рис. 1.29: Пример 3. Общий вид трубок вектограмм: 1 вектограмма первого игрока (множество P), 2 вектограмма второго игрока (множество Q) Рис. 1.30: Пример 3. а) Общий вид максимального стабильного моста с тремя узкими шейками, c = 0.397; б) Крупный план наиболее узкой из трех имеющихся шеек (средней) при = 2 = 9. наиболее узкой из них (средней) приведен на рис. 1.30б. Мост обрывается в момент = 19.35.

Счет данного примера производился на промежутке обратного времени [0, 20]. Шаг по времени = 0.05. Количество вершин аппроксимирующих многоугольников такое же, что и в первых двух примерах.

Рис. 1.31 показывает множество уровня с наложенными на него трубками вектограмм. Трубки вектограмм сделаны прозрачными. Синим цветом показана трубка P вектограмм первого игрока, зеленым трубка Q вектограмм второго игрока. На увеличенном фрагменте в районе первой шейки видно, как со сменой преимущества в пользу того или другого игрока сечения Wc (t) начинают увеличиваться или уменьшаться.

Рис. 1.31: Пример 3. Общий вид максимального стабильного моста с наложенными на него трубками вектограмм игроков: зеленая трубка стабильный мост, синяя прозрачная трубка вектограмма первого игрока (множество P), желтая прозрачная трубка вектограмма второго игрока (множество Q) Глава Уровневое выметание функции цены Одной из основных теоретико-множественных операций, используемых при построении максимальных стабильных мостов в линейных дифференциальных играх, является геометрическая разность (разность Минковского) [40, 29]. Геометрической разностью множеств A и B называют совокупность элементов, вдвигающих множество B в множество A при помощи алгебраической суммы:

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

Для геометрической разности выполняется следующее соотношение Рис. 2.1: Примеры вычисления геометрической разности: а) геометрическая разность квадрата и круга; б) геометрическая разность двух кругов. Геометрическая разность показана пунктирной линией. Тонкой линией показаны крайние положения множествавычитаемого Рис. 2.2: Сумма геометрической разности и множества-вычитаемого для примеров на рис. 2. между уменьшаемым, вычитаемым и разностью:

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

Если же множества A и B таковы, что в соотношении (2.2) имеет место равенство то говорят, что множество A полностью выметается множеством B (множество B полностью выметает множество A). Понятие полного выметания введено в работе [8].

Эквивалентно полное выметание множества A множеством B можно определить как В данной главе устанавливается следующий факт. Оказывается, что если непрерывная квазивыпуклая функция платы (·) игры (1.3) такова, что для любой пары констант c1 < c2 множество уровня Mc1 полностью выметает множество уровня Mc2, то таким же свойством обладают сечения множеств уровня функции цены:

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

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

Среди утверждений, рассматриваемых в этой главе, основными являются леммы 2.4.2, 2.5.2, 2.5.3 и итоговая теорема. Поскольку многие свойства положительно-однородных функций в R2 аналогичны свойствам функций в R, то из соображений наглядности утверждения сначала формулируются и доказываются для функций, заданных в R, и только потом для положительно-однородных функций в R2. Для функций в R аналогом леммы 2.4.2 является лемма 2.4.1.

При рассмотрении функций, заданных в R, часто будут использоваться бесконечные промежутки. Традиционная запись [a, b] может при этом обозначать бесконечные лучи или даже всю прямую, если один из объектов a, b или оба совпадают с ±.

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

2.1 Альтернированные суммы Пусть игра (1.3) имеет частный вид где терминальная функция платы непрерывна и квазивыпукла. Тогда, зафиксировав значение платы c и множество уровня Mc функции платы, можно построить соответствующее множество уровня функции цены. Его сечение в момент t [t0, T ] будет выражаться формулой Эта формула верна для игр с простыми движениями и с фазовым вектором любой размерности.

Рассмотрим теперь общий случай игры (1.3). Как описывалось в разделе 1.2, для приближенного построения множества уровня функции цены можно использовать рекуррентную процедуру, основанную на формуле (1.5). Пусть t некоторый момент из промежутка [t0, T ]. Если записать эту формулу через операции над множествами, подобно формуле (2.6), получим выражение 2.2. Связь операций над множествами и опорными функциями моменты временнго разбиения отрезка [t, T ]. Так можно сделать, поскольку после дискретизации на каждом промежутке времени [ti, ti+1 ] имеем игру с простыми движениями.

Если рекуррентно развернуть последнее выражение в явном виде, получим соотношение которое называется альтернированной суммой последовательностей {P(ti )} и {Q(ti )} с начальным значением Mc [30].

Таким образом, для того, чтобы проверить наличие уровневого выметания для сечений Wc1 (t ) и Wc2 (t ) множеств уровня в некоторый момент t, в предположении о полном выметании множества Mc2 множеством Mc1, следует проверить сохранение этого свойства при операциях алгебраической суммы, геометрической разности и при предельном переходе в альтернированной сумме.

2.2 Связь операций над множествами и опорными функциями Пусть A выпуклое замкнутое множество в пространстве Rn и A (·) его опорная функция:

Уравнение A (l) = l, x с переменной x задает опорную гиперплоскость к множеству A, перпендикулярную вектору l (рис. 2.3а). Соответственно, неравенство A (l) l, x с переменной x задает опорное полупространство множества A, перпендикулярное вектору l (рис. 2.3б).

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

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

Рис. 2.3: Иллюстрация к определению опорной фун- Рис. 2.4: Конус линейнокции: а) опорная гиперплоскость; б) опорное полу- сти опорной функции пространство Пусть имеются два выпуклых ограниченных множества A и B. Их алгебраическая сумма определяется как Опорная функция алгебраической суммы равна Рассмотрим геометрическую разность A B. Ее опорная функция записывается [42, 62] в виде Здесь conv f операция взятия выпуклой оболочки функции f. При этом, если A B =, то AB (·) собственная функция. Если же A B =, то AB (l).

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

Как было отмечено ранее, для двух произвольных множеств A и B и их геометрической разности выполняется соотношение (2.2). Соотношение (2.2) можно переформулировать на языке опорных функций как Соотношение (2.3) будет иметь вид Иначе говоря, множество A полностью выметается множеством B тогда и только тогда, когда 2.3 Локальная выпуклость В этом разделе сформулируем несколько простых свойств, связанных с выпуклыми функциями.

Предложение 2.3.1. Пусть функция f : R R определена на некотором промежутке [a, b] (возможно, бесконечном). Пусть задан отрезок I = [, ], вложенный в [a, b]. Тогда выпуклая оболочка функции f, взятая на всей области определения и суженная на отрезок I, не превосходит выпуклой оболочки сужения функции f на отрезок I:

(conv f ) [,] conv [,] f.

Определение 2.3.1. Назовем функцию f локально выпуклой в точке x Dom f, если найдется число > 0 такое, что f выпукла на множестве O (x0 ) Dom f, где Dom f область определения функции f, а O (x0 ) -окрестность точки x0.

Определение 2.3.2. Функцию f назовем локально выпуклой, если она локально выпукла в любой точке x Dom f.

Лемма 2.3.1 (критерий выпуклости). Пусть функция f определена на промежутке [a, b] ( a < b +). Функция f является выпуклой тогда и только тогда, когда она локально выпукла.

Для доказательства сформулированного критерия понадобится вспомогательная Лемма 2.3.2 (о выпуклости на объединении). Пусть функция f : R R выпукла на промежутках [a, b] и [c, d] (конечных или бесконечных). Предположим, что промежутки пересекаются, причем внутренность пересечения непуста. Тогда функция f является выпуклой на объединении [a, b] [c, d] этих промежутков.

Доказательство. Если [a, b] [c, d] или [c, d] [a, b], то утверждение очевидно. Пусть, без ограничения общности, a < c < b < d (рис. 2.5).

Рис. 2.5: Иллюстрация к доказательству леммы 2.3. Докажем выпуклость функции f на промежутке [a, d]. Предположим противное: существуют точки A и B в надграфике f такие, что отрезок [AB], их соединяющий, не принадлежит целиком надграфику. Такое возможно разве лишь, если абсцисса точки A находится слева от c, а абсцисса точки B справа от b. Возьмем произвольную точку K на [AB], которая не принадлежит надграфику. Двигаясь от нее по [AB] влево и вправо, найдем ближайшие к ней точки L и M, лежащие на графике f.

Очевидно, что абсцисса точки L расположена слева от c, а абсцисса точки M справа от b.

Обозначим через P и Q точки на графике f, имеющие абсциссы c и b соответственно.

В силу выпуклости функции f на интервале [c, d] отрезок [P M ] лежит в надграфике f. Точка Q лежит на графике, т.е. не выше отрезка [P M ].

При этом точка Q лежит выше отрезка [LM ] по построению этого отрезка.

Проведем отрезок [LQ]. Точка P лежит выше этого отрезка, так как она лежит не ниже луча [M Q), а отрезок [LQ] ниже этого луча.

Однако в силу выпуклости функции f на промежутке [a, b] точка P должна лежать не ниже отрезка [LQ]. Получили противоречие.

Теперь докажем эквивалентность локальной и глобальной выпуклостей.

Доказательство (критерия выпуклости). Очевидно, что локальная выпуклость следует из глобальной в силу определения выпуклости. Докажем обратное следование.

Пусть функция f локально выпукла. Зафиксируем точку x0 (a, b) и выберем > 0 такое, что [x0, x0 + ] [a, b] и f выпукла на промежутке [x0, x0 + ].

Выберем максимальное число x1 (x0, b] такое, что функция f выпукла на интервале [x0, x1 ]. Если b = +, то и x1 может быть равно +.

Покажем, что x1 = b. Пусть, от противного, x1 (x0, b) [a, b]. Тогда в силу локальной выпуклости f найдется число 1 > 0 такое, что и f выпукла на [x1 1, x1 + 1 ]. Применяя предыдущую лемму 2.3.2 к промежуткам (x0, x1 ) и (x1 1, x1 + 1 ), получаем, что f выпукла на их объединении, т.е. на промежутке (x0, x1 + 1 ), что противоречит построению промежутка [x0, x1 ].

Аналогично показывается, что f выпукла на промежутке [a, x0 + ).

Доказательство глобальной выпуклости функции f на [a, b] завершается через сращивание промежутков [a, x0 + ] и [x0, b] также с использованием леммы 2.3.2.

Лемма 2.3.1 верна и многомерном случае, когда f : Rn R.

Предложение 2.3.2. Пусть функция f : Rn R определена на выпуклом множестве D (ограниченном или неограниченном). Функция f выпукла тогда и только тогда, когда она локально выпукла на D.

Действительно, если где-то нарушается выпуклость функции f, то найдется отрезок [x1, x2 ] Rn, на котором f невыпукла. Переходя к сужению функции на этот отрезок, получим одномерный случай, рассмотренный в лемме.

Лемма 2.3.3 (о сопряжении). Пусть функция f : R R выпукла на промежутке [a, b] (конечном или бесконечном). Зададим промежуток [, ] [a, b] и функцию f подменим новой функцией f так, что f непрерывна, f (x) = f (x) при x [a, b]\[, ], f f на [, ], f выпукла на [, ]. Тогда функция f выпукла на всем промежутке [a, b].

Доказательство. Воспользуемся доказанным выше критерием. Локальная выпуклость функции f очевидна на промежутках [a, ] и [, b] (там она совпадает с выпуклой функцией f ) и на промежутке [, ] (там она выпукла по построению). Таким образом, для доказательства леммы нужно показать локальную выпуклость функции f в точке, если она принадлежит интервалу (a, b), и, аналогично, локальную выпуклость в точке.

Докажем локальную выпуклость в точке (для точки доказательство аналогично).

Предположим противное. Пусть f не является локально выпуклой в точке. Иначе говоря, для любой окрестности точки функция f невыпукла в этой окрестности: > 0 функция f невыпукла на [, + ] [a, ]. Зафиксируем > 0 такое, что [, +] (a, ). При этом найдутся две точки (x1, y1 ) и (x2, y2 ) из надграфика f на интервале (, +) (т.е. y1 f (x1 ) и y2 f (x2 )) такие, что отрезок I = (x1, y1 ), (x2, y2 ) не лежит целиком в надграфике epi f. Обозначим линейную функцию, график которой содержит этот отрезок, через L(x) (см. рис. 2.6).

Имеем L() < f (). Действительно, если бы L() f (), то отрезок I целиком содержался бы в epi f. Часть (x1, y1 ), (, L()) лежала бы в epi f в силу выпуклости f на [a, ] там f совпадает с f, которая выпукла; а часть (, L()), (x2, y2 ) лежала бы в epi f в силу выпуклости f на [, ].

Итак, получаем конфигурацию, изображенную на рис. 2.6. Поскольку y1 f (x1 ) = f (x1 ), а y2 f (x2 ) > f (x2 ), находим, что точки (x1, y1 ) и (x2, y2 ) лежат в надграфике f. Стало быть, весь отрезок I лежит в надграфике f. Поэтому f () L() < f () = f (). Противоречие. Стало быть, исходное предположение о локальной невыпуклости f в точке неверно.

Лемма 2.3.4 (о локализации овыпукления). Пусть f : R R и [a, b] Dom f. Если величина a конечное число, предположим, что f (a) = (conv f )(a); аналогично предположим, что f (b) = (conv f )(b). Тогда conv [a,b] f = (conv f ) [a,b].

В силу предложения 2.3.1 на [a, b] справедливо неравенство f1 f2.

Определим функцию f совпадающей с f1 на [a, b] и с f2 на Dom f \[a, b].

Эта функция будет выпуклой по предыдущей лемме. Кроме того, она подпирает f и не меньше conv f. Поэтому f = conv f.

Лемма 2.3.5 (о локализации области овыпукления положительно-однородной функции). Пусть f : R2 R положительно-однородная функция такая, что conv f собственная функция. Пусть C выпуклый конус с вершиной в нуле и f = conv f на C. Тогда conv C f = (conv f ) C.

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

Лемму 2.3.4 можно расширить на пространство любой размерности для любой функции (не обязательно положительно-однородной) и для любой выпуклой области (не обязательно конуса с вершиной в нуле).

Предложение 2.3.3. Пусть f : Rn R, Dom f выпуклое множество, D Dom f выпуклое замкнутое подмножество, f = conv f на D.

Тогда conv D f = (conv f ) D.

2.4 Разность выпуклых функций Лемма 2.4.1. Пусть функции f, g : R R непрерывны и определены на промежутках If = Dom f Ig = Dom g (конечных или бесконечных). Предположим, что conv f и conv g собственные функции и функция h = f g выпукла на If. Тогда разность conv If f conv Ig g выпукла на If.

Доказательство.

A. Обозначим g = conv рывности функций g и g множество S замкнуто, стало быть, S = Ig \S открыто и представляется в виде не более чем счетного дизъюнктного объединения интервалов (среди них может быть не более двух бесконечных): S = (i, i ) : i = 1, N, где N, i i < i +, Видно, что для любого i Рассмотрим процесс построения выпуклой оболочки функции g как пошаговый: g = g0 g1 g2... Очередная функция gi получается из gi1 заменой последней на отрезке [i, i ] линейной функцией:

3) li (i ) = gi1 (i ), li (i ) = gi1 (i ).

Параллельно будем осуществлять процесс подправки функции f :

2) если (i, i ) If =, то функция fi1 подправляется на промежутdef ке [ i, i ] = [i, i ] If следующим образом:

Т.е. функция fi получается из функции fi1 овыпуклением последней на общей части промежутков [i, i ] и If (если таковая существует).

B. Обозначим hi = fi gi. Для любого числа i функция hi выпукла.

Докажем это по индукции.

База индукции: Имеем h0 = f0 g0 = f g, а функция f g выпукла.

Шаг индукции: Пусть hi1 выпукла. Докажем, что hi тоже будет выпуклой. Возможны три случая.

Случай б: If [i, i ]. Тогда fi = conv If fi1 выпукла, gi li на If и поэтому линейна. Следовательно, hi = fi gi выпукла. Более того, в быть, с этого номера i последовательность {fj } стабилизируется. Также стабилизируется {gj } : j > i gj If = li If. Следовательно, существует поточечный предел lim hj = h = f = lim fj lim gj = fi li, являющийся выпуклой функцией.

Случай в: (i, i ) If =, If [i, i ]. Обозначим, как было указано выше, [ i, i ] = [i, i ] If. Заметим, что хотя бы одна из точек i, i лежит внутри If.

Выполняется неравенство gi [i,i ] gi1 [i,i ]. При этом gi линейна на i ]. Стало быть, на отрезке [ i, i ] имеем Поэтому Здесь gi линейна, hi1 выпукла. Следовательно, сумма gi + hi1 выпукла на [ i, i ]. Поскольку отмеченная сумма, являясь выпуклой функцией, подпирает функцию fi1, то эта же сумма подпирает и выпуклую оболочку fi1, т.е. подпирает и функцию fi : fi = conv [i,i ] fi1 gi + hi на [ i, i ]. Преобразуя последнее неравенство, получаем fi gi hi1, т.е. hi hi1 на [ i, i ].

Функция fi [i,i ] = conv [i,i ] fi1 выпукла на [ i, i ]. Следовательно, hi = fi gi выпукла на [ i, i ] как разность выпуклой и линейной функций.

Итак, о непрерывной функции hi мы имеем следующие сведения:

1) hi hi1 на If, а на If \[ i, i ] функции hi и hi1 совпадают;

2) hi является локально выпуклой на [ i, i ] и на If \[ i, i ].

Выпуклость функции hi следует из леммы 2.3.3.

Таким образом, доказан шаг индукции.

C. Воспользуемся выпуклостью функций hi на If. Верны следующие поточечные пределы:

(Здесь f некоторая функция, про которую будет ниже доказано, что она совпадает с выпуклой оболочкой f.) Имеем x If i N hi (x) h(x), hi (x) h(x). Отсюда получается, что h(x) = sup hi (x), т.е. h = sup hi. Следовательно, h выпукла как верхняя огибающая семейства выпуклых функций.

Кроме того, из определения функций f и g как поточечных пределов функций f и g, соответственно, вытекает, что h = f g. Поэтому функция f = g + h выпукла как сумма выпуклых функций.

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

Докажем, что f = conv f (это нужно сделать, если в процессе подIf правки функций f и g не встретился случай б индукции).

Имеем f = f conv f на S If. Здесь S, как вводилось в начале доказательства множество, на котором функция g совпадает со своей выпуклой оболочкой. (Равенство верно в силу построения функций fi : они отличаются от f только там, где gi отличаются от g).

Поскольку для любого x If \S найдется номер i N такой, что x (i, i ), то для этого i При этом очевидно, что fi (x) f (x).

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

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

Лемма 2.4.2. Пусть функции f, g : R2 R являются непрерывными и положительно-однородными. Пусть conv f, conv g собственные функции и функция h = f g выпукла. Тогда разность conv f conv g выпукла.

Доказательство.

A. Обозначим g = conv g, S = x R2 : g (x) = g(x). В силу непрерывности функций g и g множество S замкнуто. С учетом положительной однородности этих функций множество S = (R2 \S) {0} представляется в виде не более чем счетного объединения открытых конусов (т.е., без граничных образующих), пересекающихся лишь в точке {0}:

При этом раствор каждого из конусов не превышает (см. рис. 2.7). Обозначим через Ci замыкание конуса Ci.

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

g = g0 g1 g2... Очередная функция gi получается из gi1 заменой последней на конусе Ci линейной функцией:

1) li = (conv g) Ci ;

2) li gi1 на Ci ;

3) li = gi1 на Ci.

Параллельно будем осуществлять процесс подправки функции f :

Т.е. функция fi получается из функции fi1 овыпуклением последней на конусе Ci.

C. Обозначим hi = fi gi. Для любого числа i функция hi выпукла.

Докажем это по индукции.

База индукции: Имеем h0 = f0 g0 = f g, а функция f g выпукла.

Шаг индукции: Выполняется неравенство gi Ci gi1. Из него вытекает, что на конусе C Поэтому Здесь функция gi линейна, функция hi1 выпукла. Следовательно, сумма gi + hi1 выпукла на Ci. Поскольку отмеченная сумма, являясь выпуклой функцией, подпирает функцию fi1, то эта же сумма подпирает и выпуклую оболочку fi1, т.е. подпирает и функцию fi : fi = conv Ci fi i. Преобразуя последнее неравенство, получаем fi gi hi1, gi + hi1 на C т.е., hi hi1 на Ci.

Функция fi Ci = conv Ci fi1 Ci выпукла на Ci. Тогда hi = fi gi выпукла на Ci как разность выпуклой и линейной функций.

Итак, о непрерывной положительно-однородной функции hi мы имеем следующие сведения:

1) hi hi1 на R2, а на R2 \Ci функции hi и hi1 совпадают;

2) hi является локально выпуклой на множествах Ci и R2 \Ci.

Выпуклость функции hi следует из леммы 2.3.3. Действительно, выберем какой-нибудь отрезок I = [AD], пересекающий границу конуса Ci в точке B, не совпадающей с нулем плоскости (см. рис. 2.8). Его можно взять достаточно малым, поскольку нужно будет доказать локальную выпуклость функции hi на отрезке лишь в точке B. Функция hi1 выпукла на [AD], hi = hi1 на [AB], функция hi выпукла на [BD] и hi hi1.

Поэтому в силу леммы 2.3.3 функция hi выпукла на [AD].

Таким образом, доказан шаг индукции.

C. Окончание доказательства (обоснование выпуклости предельной функции h и совпадение предельной функции f с выпуклой оболочкой conv f ) повторяет окончание доказательства леммы 2.4.1.

Рис. 2.8: К доказательству выпуклости функции hi в лемме 2.4. 2.4.1 Контрпример к обобщению лемм 2.4.1 и 2.4. Отметим, что для произвольных функций, имеющих область определения в пространстве размерности 2 или выше, утверждение, аналогичное леммам 2.4.1 и 2.4.2, вообще говоря, неверно. Это демонстрируется следующим контрпримером.

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

При этом нуль пространства полагаем на середине выступа долота и на середине вмятины крыши. Тогда график функции f g = f + (g) будет напоминать график f. Наклон нижнего выступа будет более крутым, а боковых граней, наоборот более пологим в сравнении с графиком функции f. Подбором наклонов плоскостей исходных графиков (достаточно крутые боковые грани функции f и достаточно пологие наклоны скатов функции g и выступа долота ) можно достичь того, что график f g будет выпуклым.

Рассмотрим график функции conv f conv g = f + ( conv g). Выпуклая оболочка conv f совпадает с f, поскольку функция f исходно выпукла.

График функции conv g (или, что то же самое, вогнутая оболочка g) будет представлять собой крышу без всяких вмятин (рис. 2.9в). Рассмотрим сечения графиков conv f, conv g и их суммы, проведенные в вертиб) 2.5.2. Сохранение полного выметания при геометрической разности Рис. 2.10: Сечения графиков conv f = f (а), conv g (б) и conv f conv g (в) кальной плоскости, проходящей по прямой выступа долота f (рис. 2.10).

Поскольку сечение графика функции conv f conv g невыпукло, то и вся функция conv f conv g невыпукла.

2.5 Доказательство факта о сохранении уровневого выметания 2.5.1 Сохранение полного выметания при алгебраической сумме Лемма 2.5.1. Пусть множества A и B таковы, что множество A полностью выметается множеством B, т.е. A = B + (A B). Тогда для любого множества P имеем Доказательство. Будем использовать эквивалентное определение полного выметания, т.е. докажем, что Выберем a A+P. Тогда найдутся такие a A и p P, что a = a+p.

В силу полной выметаемости A при помощи B находим, что x : a B + x Раскрывая первое включение, имеем Расписывая второе вложение, получаем Нужные свойства показаны.

2.5.2 Сохранение полного выметания при геометрической разности Лемма 2.5.2. Пусть выпуклые компакты A, B R2 таковы, что множество A полностью выметается множеством B: A = B + (A B).

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

Обозначим AQ = A Q, BQ = B Q. В этих обозначениях имеем Требуется показать, что Рассмотрим функции f = A Q и g = B Q. По условию леммы выражение есть выпуклая функция. Тогда по лемме 2.4.2 функция также будет выпуклой. Стало быть, она совпадает со своей выпуклой оболочкой.

2.5.3 Контрпример к обобщению леммы 2.5. Отметим, что только что доказанный факт неверен для множеств высокой размерности. Это демонстрируется следующим контрпримером.

Выберем множество A в трехмерном пространстве в виде полушара, срезанного двумя плоскостями (см. рис. 2.11). Множество B возьмем подобным множеству A с коэффициентом подобия 0.5. Известно, что меньшее из двух выпуклых подобных множеств выметает большее. Меридиональные сечения (вертикальные плоские грани) множеств A и B приведены справа от них. Выберем множество Q в виде отрезка, перпендикулярного меридиональным плоскостям множеств A и B. При этом длина 2.5.4. Сохранение полного выметания при предельном переходе отрезка Q больше срезанной части B, но меньше срезанной части A (эти части условно обозначены на рис. 2.11 тонкими вертикальными линиями).

Легко показать, что геометрическая разность выпуклого множества и отрезка есть пересечение двух экземпляров этого множества, смещенных друг относительно друга на этот отрезок. Геометрические разности A Q и B Q изображены в правой части рисунка. Тонкими линиями отмечены исходные множества A и B. В силу выбора длины отрезка Q крыша на множестве A Q сохранилась. Вертикальная плоская грань разности приведена справа: она имеет угловую точку. В то же время исходная крыша множества B пропала, и вертикальная плоская грань множества B Q есть просто круг. Очевидно, что множество A Q не выметается полностью множеством B Q: угол сечения A Q не может быть накрыт множеством B Q так, чтобы последнее полностью находилось в A Q.

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

Рис. 2.11: Контрпример к сохранению полной выметаемости после геометрической разности в случае множеств размерности три или выше 2.5.4 Сохранение полного выметания при предельном переходе Лемма 2.5.3. Пусть задана игра с фиксированным моментом окончания T. Предположим, что многозначные функции P (t), Q(t) : [t0, T ] 2R непрерывны и имеют значениями выпуклые компактные множества. Зафиксируем момент t [t0, T ] и рассмотрим два максимальных стабильных моста W1 и W2, построенных на промежутке времени [t, T ] от двух множеств M1 и M2 соответственно. Считаем, что int W1 (t) = для всех моментов t [t, T ].

Пусть множество M1 полностью выметает множество M2.

Тогда множество W1 (t ) полностью выметает множество W2 (t ).

Доказательство. Выберем последовательность разбиений промежутка [t, T ] с диаметром k 0. Обозначим через W1 (t ) и W2 (t ) альтернированные суммы (2.7) последовательностей {P (ti )} и {Q(ti )} с начальными значениями W1 (T ) = M1 и W2 (T ) = M2.

Поскольку множество W1 (T ) полностью выметает W2 (T ), то в силу тает множество W2 (ti ). Следовательно, для любого k множество W1 (t ) полностью выметает множество W2 (t ).

В силу предположения о том, что для любого момента t [t, T ] непуста внутренность сечения W1 (t) множества уровня W1 функции цены, имеются сходимости множеств W1 (t ) W1 (t ) и W2 (t ) W2 (t ) в метрике Хаусдорфа при k.

Стало быть, чтобы доказать полное выметание множества W2 (t ) множеством W1 (t ), требуется обосновать следующий факт. Пусть две последовательности {Ak } и {Bk } выпуклых компактных множеств сходятся в метрике Хаусдорфа к компактным множествам A и B соответственно.

Предположим, что для любого k множество Bk полностью выметает множество Ak. Тогда предельные множества обладают тем же свойством: множество B полностью выметает множество A.

Используем альтернативное определение полного выметания, т.е. докажем, что a A x : 1) a B + x и 2) B + x A.

2.5.4. Сохранение полного выметания при предельном переходе Возьмем произвольный элемент a A. В силу сходимости Ak A, можно выбрать последовательность {ak }, ak Ak, такую, что ak a.

Поскольку множество Ak полностью выметается множеством Bk, то Рассмотрим последовательность {xk }. Она ограничена. Стало быть, из нее можно выделить сходящуюся подпоследовательность. Без ограничения общности, будем считать, что сама последовательность {xk } сходится к некоторому элементу x пространства R2. Покажем, что этот элемент совпадает с тем, который фигурирует в определении полного выметания.

Первое свойство: a B + x. Имеем k ak Bk + xk. Выберем такие bk Bk, что ak = bk +xk. Поскольку ak a и xk x, то bk b = ax.

Принимая во внимание сходимость Bk B, получаем b B. Следовательно, существует элемент b B такой, что a = b + x. Поэтому a B + x.

Второе свойство: B + x A. Выберем произвольный элемент b B.

В силу сходимости Bk B можно выбрать последовательность {bk }, bk Bk, такую, что bk b. Поскольку Bk + xk Ak, то bk + xk Ak. Следовательно, k ak Ak : bk + xk = ak. В силу того, что bk b и xk x, имеем ak a = b + x. Принимая во внимание сходимость Ak A, получаем a A. Отсюда для любого b B вытекает b + x A. Стало быть, Таким образом, множество B полностью выметает множество A.

2.5.4. Сохранение полного выметания при предельном переходе Теорема. Пусть функция платы (·) дифференциальной игры (1.3) такова, что для любых двух констант c1 < c2 ее множество уровня Mc (если оно непусто) полностью выметает множество уровня Mc2.

Тогда соответствующие множества уровня Wc1 и Wc2 функции цены V (·) игры (1.3) обладают следующим свойством: для каждого момента t [t0, T ] такого, что сечение меньшего множества уровня Wc1 (t ) непусто, сечение Wc1 (t ) полностью выметает сечение Wc2 (t ) большего множества уровня.

Доказательство. Если int Wc1 (t) = для всех t [t, T ], то утверждение теоремы следует непосредственно из леммы 2.5.3.

Пусть теперь Wc1 (t ) =, но int Wc1 (t ) = в некоторый момент t [t, T ]. Из непрерывности функции цены следует, что int Wc (t ) =, если c > c1. Тогда int Wc (t) = при c > c1 для всех моментов времени t [t, T ]. В силу факта, отмеченного в предыдущем абзаце, множество Wc (t ) полностью выметает множество Wc2 (t ), если c (c1, c2 ).

Поскольку Wc (t ) Wc1 (t ) в метрике Хаусдорфа при c c1 + 0, то множество Wc1 (t ) полностью выметает множество Wc2 (t ).

Таким образом, теорема утверждает, что если функция платы обладает свойством уровневого выметания, то это свойство наследуется функцией цены для любого момента времени из промежутка [t0, T ].

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

Глава Численное построение сингулярных поверхностей Понятие сингулярных поверхностей дифференциальной игры введено американским математиком Р.Айзексом в книге [1]. Соответствующие определения базировались на анализе поведения оптимальных движений на рассматриваемой поверхности и вблизи нее. Позже определения такого типа были использованы J.V.Breakwell, J.Lewin, A.W.Merz, J.G.Olsder, J.Shinar [50, 64, 68, 65, 69] при исследовании конкретных задач игрового быстродействия. Необходимые условия, характеризующие сингулярные поверхности, исследовались P.Bernhard в статье [47]. Определения сингулярных поверхностей, основанные на рассмотрении точек недифференцируемости функции цены игры и классификации геометрии предельных значений векторов ее градиентов в точках поверхности, были предложены в работах А.А.Меликяна [66] и Л.В.Камневой [11]. А.А.Меликяном доказаны утверждения о необходимых условиях сингулярных поверхностей с использованием понятия обобщенного (минимаксного, вязкостного) решения уравнения Гамильтона–Якоби–Беллмана–Айзекса.

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

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

Таким образом, первичными являются сингулярные линии на границе множеств уровня.

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

Среди примеров построения сингулярных поверхностей, включенных в текст главы, имеются задачи [22, 23, 70, 71], исследованные ранее аналитическими методами. Результаты, полученные при помощи разработанных программ, достаточно хорошо совпадают с результатами этих статей.

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

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

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

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

Итак, для промежутка времени [ti, ti+1 ] рассмотрим игру с простыми движениями. В прямом времени первый игрок пытается перевести систему с многоугольника Wc (ti ) на многоугольник Wc (ti+1 ), второй препятствует этому. Вводя дискриминацию второго игрока, определим оптимальные движения.

Зафиксируем некоторую точку y0 на границе многоугольника Wc (ti ).

Управление второго игрока (постоянное на промежутке [ti, ti+1 )) назовем оптимальным, если первый игрок не может направить результирующее движение из точки y0 во внутренность многоугольника Wc (ti+1 ). При выбранном оптимальном управлении второго игрока, управление первого игрока (также постоянное на этом интервале) назовем оптимальным парирующим, если соответствующее движение остается на границе моста.

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

Управление v, удовлетворяющее условию максимума назовем экстремальным управлением второго игрока на векторе l. Аналогично, экстремальное управление первого игрока на векторе l это такое управление u, которое удовлетворяет условию минимума Легко видеть, что если y0 является внутренней точкой какого-либо ребра многоугольника Wc (ti ), то постоянное управление второго игрока оптимально тогда и только тогда, когда оно экстремально на внешней нормали многоугольника Wc (ti ) в этой точке. Оптимальное парирующее управление первого игрока экстремально на том же векторе.

Если y0 вершина многоугольника Wc (ti ), то ей соответствуют две внешние нормали инцидентных ей ребер. Структура оптимальных управлений в этом случае описывается следующим образом [10].

Для любой вершины многоугольника Wc (ti ) управление второго игрока, экстремальное хотя бы на одном из векторов внешних нормалей, соответствующих этой вершине, является оптимальным. При этом оптимальное парирующее управление первого игрока экстремально на том же векторе.