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

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

ТАРАСЬЕВ Александр Михайлович

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

01.01.02 - дифференциальные уравнения

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

Екатеринбург

1996

Работа выполнена в Институте математики и механики Уральского отделения Российской Академии наук.

Официальные оппоненты: доктор физико-математических наук,

на заседании специализированного совета Д 002.07.01 по защите диссертаций на соискание ученой степени доктора наук при Институте натематики и механики Уральского отделения РАН по адресу: 620066, г. Екатеринбург, ул. С.Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики Уральского отделения РАН.

профессор Э.Г. АЛЬБРЕХТ; академик РАН H.H. КРАСОВСКИИ; доктор физико-математических наук, профессор М.С. НИКОЛЬСКИЙ.

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

Зашита состоится

Автореферат

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

М.И. Гусев

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

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

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

А.Б. Куржанский, Дж. Лейтман, П.-Л. Лионе, A.A. Меликян, Е.Ф.

3

Мищенко, М.С. Никольский, Ж.-П. Обэн, Г. Ольсдер, Ю.С. Осипов,

A. Г. Пашков, B.C. Пацко, H.H. Петров, J1.A. Петросян, Г. К. Пожарицкий, Б.Н. Пшеничный, А.И. Субботин, H.H. Субботина,

B.Е. Третьяков, В.Н. Ушаков, А. Фридман, Хо Ю-ши, А. Г. Ченцов, Ф.Л. Черноусько, A.A. Чикрий, Р. Эллиотт и многие другие.

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

1

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

игр ' , которая разрабатывается в научной школе H.H. Красов-ского по оптимальному управлению.

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

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

4

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

3

принцип экстремального прицеливания на стабильные носты. Для

широкого круга дифференциальных игр доказана теорема об аль-р

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

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

5

мального гарантированного управления .

Красовский Н.Н. Игровые задачи о встрече движений. М. : Наука, 1970. 420 с.

Субботин А. И. Обобщение основного уравнения теории дифференциальных игр // Докл. АН СССР. 1980. Т. 254. № 2. С. 293-297.

Guseinov H. G. , Subboti n A. I. , Ushakov V.N. Derivatives for multivalued mappings with applications to game-theoretical problems of control SS Probl. Control and Information Theory. 1983. Vol.14. No. 3. P. 155-167.

4

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

С

производных первого порядка - уравнений Ганильтона-Якоби . Эти обобщенные решения были названы минимаксными, т.к. операции нинимума и максимума являются характерными в определении решений и представлены, например, в функциях программного ма-ксимина, формулах Хопфа, конструкциях идемпотентного анализа.

В главе 1 диссертации представлены результаты, полученные

4 s

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

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

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

6

Развивались конструкции первого и второго методов Л. С.

7

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

В главе 2 диссертации предлагаются вычислительные нетоды построения функции цены и оптимальных стратегия, которые представляют собой сеточные аппроксинэционные схемы для соответствующих уравнений Гамильтона-Якоби. Эти схемы являются продолжением совместных исследований автора с В.Н. Ушаковым и ого сотрудникани по разработке алгоритмов построения стабильных мостов 15,7,э,юз, в аппроксимационных схемах используются конечно-разностные операторы, основанные на конструкциях негладкого и выпуклого анализа - обобщенных градиентах различных типов.

Теория уравнений Гамильтона-Якоби в 50-70-е годы привлекала внимание многих авторов в связи с интенсивными исследованиями в области математической физики. Проблене определения неклассических (недифференцируемых) решений и вопросу численного их построения для некоторых классов уравнений Гзнильтона-Якоби посвящены работы С.К. Годунова, С.Н. Кружкова, O.A. Ладыженской, O.A. Олейник, A.A. Самарского, А.Н. Тихонова. П. Лакса, Е. Хопфа, У. Флеминга и других.

Методами идемпотентного анализа уравнения в частных производных первого порядка исследовались в работах В. П. Мас-лова и его сотрудников.

7

Понтрягин Л.С. О линейных дифференциальных играх. 1; 2 // Докл. АН СССР. 1967. Т. 174. № 6. С. 1278-1280; Т. 175. № 4. С. 764-766.

В начале 80-х годов были опубликованы работы М.Дж. Крэн-

о о

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

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

Crandall M. G. , Lions P.-L. Viscosity solutions of Hamil-ton-Jacobi equations // Trans. Amer. Math. Soc. 1983. Vol. 277. No. 1'. P. 1-42.

Crandall M. G. , Lions P.-L. Two approximations of solutions of Hamilton-Jacobi equations /V Math. Comput. 1984. Vol. 43. No. 167. P. 1-19.

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

Построение теории вязкостных решений стимулировало развитие вычислительных нетодов. В работах М.Дж. Крэндалла,

Ч 1 Г)

П.-Л. Лионса и П.Е. Соуганидиса были рассмотрены явные и

неявные эппроксинационные схемы с конечно-разностными операторами Лэкса-Фридрихса, предложен общий метод обоснования сходимости и указаны оценки сходимости. Аппроксимации высоких порядков в "по существу неосциллируших" схемах рассматривались11 С. Ошером и Ц.-У. Шу.

В диссертационной работе предлагаются конечно-разностные операторы специального типа для аппроксимации "несуществующих" градиентов в уравнении Гамильтона-Якоби. Лля этого применяются конструкции негладкого анализа: суб и супердифференциалы различных типов, обобщенные градиенты локальных линейных оболочек. Проводится сравнение предлагаемых конструкций с классическими операторами Годунова и Лакса-Фридрихса, известными в

Souganidis P.E. Approximation schemes for viscosity solutions of Hami1ton-Jacobi equations// J. Different. Equat. 1985. Vol. 59. Ho. 1. P. 1-43.

Osher S. , Shu C.-W. High-order essentially nonosci 11 atory

schemes for Hami 1 ton-Jacobi equations // SI AM J. Numer.

Anal. 1991. Vol. 28. No. 4. P. 907-922.

9

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

Ч 1 о

мощью достаточных условий сходимости из работ

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

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

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

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

1. Предложены дифференциальные неравенства в терминах

10

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

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

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

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

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

на 6-7-ом съездах по механике (Ташкент, 1986), (Москва, 1991),

5-7-ой Всесоюзных конференциях по управлению в механических

системах (Казань, 1987), (Львов, 1988), (Свердловск, 1990),

Гагэринских научных чтениях по космонавтике и авиации (Москва,

1986, 1988, 1991), Международных конференциях и семинарах по

11

дифференциальным уравнениям (Руссе, Болгария, 1985), математическим нетодам оптимального управления (Минск, 1989), методу функций Ляпунова (imacs, Иркутск, 1990), негладким и разрывным задачам управления и оптимизации (1-2-ой семинары ifac -Владивосток, 1991, Челябинск, 1993), оптимальнону управлению в механических системах (Москва, 1992), нелинейному теоретико-игровому и управляемому синтезу (Санкт-Петербург, 1995), динамике и управлению (Шопрон, Венгрия, 1995). Основные результаты докладывались на семинарах отдела динамических систем ИММ УрО РАН, кафедры прикладной математики УрГУ, кафедры оптимального управления ВМК МГУ, в Университете Вюрцбурга (ФРГ, 1992), в Институте прикладного и системного анализа (iiasa. Лаксенбург, Австрия, 1994, 1995).

Публикации. По теме диссертации опубликовано более 20 работ. Список основных публикаций приводится в конце автореферата. Результаты, вошедшие в диссертацию, получены автором. В работах ч.гз А.И. Субботину принадлежит постановка задач. Результаты работ c5.io,i3,i8j получены совместно с В.Н. Ушаковым и A.A. Успенскин. В совместной с P.A. Адиатулиной статье с 8] автору принадлежит постановка задачи и методы решения. Работы гз,7,9.1ез не вошли в диссертацию, но имеют к ней непосредственное отношение. Особенно близкими являются результаты совместных с В.Н. Ушаковым и А.П. Хрипуновым исследований по численнын методам построения стабильных мостов. Работы £19,го: инициированы исследованиями A.B. Кряжимского, проводимыми в Международном Институте прикладного и системного анализа (iiasa, Лаксенбург, Австрия).

Решения примеров, включенных во вторую и пятую главы, получены с понощыо програнм, разработанных A.A. Успенским и Н.В.

12

Мельниковой.

Структура и обьеи. Диссертация состоит из пяти глав и семнадцати параграфов, которые разделяются на пункты. Объен диссертации составляет 350 страниц. Библиография состоит из 195 наименований.

СОДЕРЖАНИЕ РАБОТЫ В первой главе рассматриваются уравнения Ганильтона-Якоби и связанные с ними задачи гарантированного управления - позиционные дифференциальные игры. В теории позиционных диффе-1 2

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

Функция цены в точках дифференцируемости удовлетворяет уравнению в частных производных первого порядка типа Гэмиль-тона-Якоби. Известно, что функция цены является, как правило, недифференцируемой функцией. Задача определения обобщенных (недифференцируемых) решений уравнений Гэмильтона-Яиоби рассматривалась в работах А.И. Субботина4'®. Было введено понятие минимаксного решения, доказаны теоремы существования и единственности. В рамках теории уравнений с частныни производными

аналогичные вопросы рассматривались в работах М.Д*. Крэндалла 8 Э

и П.-Л. Лионса ' , где обобщенные решения названы вязкостныни.

Обобщенное решение определяется с помощью пары дифференциаль-

13

ных неравенств, заменяющих уравнение Гамильтона-Якоби в точках недифференцируемости решения.

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

Лля непрерывных по Липшицу функций (t.xHoCt.x) верхняя и нижняя сопряженные производные определяются формулами

D*uXt.x)|(s) = sup (<s,h> - 0_U(t.x)|(l.h)) heRn

DMUXt.x)|(s) = in/ (<s.h> - 0+U(t.x)|(l.h)) heRn

Здесь вектор s e r" - сопряженная переменная, символами д_ и обозначены нижняя и верхняя производные функции ш по направлению (l.h). h е r" в точке (t.x) е х е rn

0 UXt.x)l(l.h) = liminf ДшСЪ.х.Ь.б)^-1 Ojo

a^aXt.x)l(i.h) = nmsup AaXt,x.h.S)>5-1 ejo

AuXt.x.h.S) = aXt+6.x+6h) - (0(t.x)

Изучаются свойства сопряженных производных. В частности,

исследуются вопросы непрерывности сопряженных производных и

14

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

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

х = f(t,x,u,v) = h(t,x) + B(t.x)u + C(t.x)v (1 )

x(t ) = x , t 6 tt = T, x e r". u e P с rp. v e Q с rq

о о о

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

7(х( • )) = a(x(fl)) (2)

В задаче (i). (г) требуется выбором позиционного способа управления и = u(t.x) e iР гарантировать минимальное значение функционала (г) при любой реализации помехи v.

В точках ди^еренцируемости функция цены (t.x>4o(t,x) удовлетворяет уравнению в частных производных первого порядка типа Гамильтона-Якоби (Айзекса-Беллмана) Зш dw

— + h(t, x. — ) = о (3 )

dt дх

Здесь символом н обозначен гамильтониан управляемой системы (i )

H(t.x.s) = <s,h(t.x)> + min <s,B(t.x)u> + max <s,C(t,x)v> (4)

ueP veQ

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

Теорема 1.2.1. Пусть функция о из тернинального функционала (г) удовлетворяет условию Липшица. Для того чтобы функция ш: t*rn->r была функцией цены дифференциальной игры (i ), (2), рассматриваемой в классе позиционных стратегий if*vp, необходимо и достаточно, чтобы выполнялись следующие условия.

15

1. Функция (с.хН^их) удовлетворяет условию Липшица.

2. Выполняется краевое условие шСв.х) = о(х).

3. Имеют несто дифференциальные неравенства, связывающие сопряженные производные о*, о^ функции ш с гамильтонианом н (4.) управляемой системы (1 )

) £ ни.х.а ) (5)

^ (Б)

(их,Б ) е .•0)х!?П*1гП о

Дифференциальные неравенства выражают свойства стабильности функции ш. В точках дифференцируемости функции ш они обращаются в уравнение Гамильтона-Якоби (з).

Сопряженные производные являются достаточно удобными конструкциями для исследования решений: аналитических вычислений, построения аппроксинационных схем, различных приложений, т.к. являются носителями концепции двойственности. В первой главе демонстрируется эффективность предлагаемых конструкций сопряженных производных: выводятся аналитические формулы для сопряженных производных кусочно-гладких решений (§1), обсуждается вопрос эквивалентности дифференциальных неравенств в определении мининаксных и вязкостных решений (§ 3), обосновываются условия регулярности функции программного максимина в терминах сопряженных переменных (§ 4), исследуются свойства кусочно-гладких решений на сингулярных поверхностях (§5).

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

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

Пусть заданы шаг дискретизации Л интервала т и моненты времени t е т. t+Д е т. Полагаем, что в нонент вренени t+Д задана непрерывная по Липшицу функция х-и(х), приближающая обобщенное решение х-иХt+Д,х). Определим оператор u-F(t.A,u), который аппроксимирует уравнение Гамильтона-Якоби (з) и задает значения функции x->v(x), приближающие решение x-*oXt,x), формулой

v(x) = F(t.A.uXx) = (7)

= f(x) + max max < ДН( t. x, s )+f ( у )-f ( x )-< s , y-x> >

уеО(х.КД) seDf(y)

Здесь функция y-*f(y).- о(х,гД) - r - локальная выпуклая оболочка функции u(y) в замкнутой окрестности о(х.гД) точки х радиуса гД

п+1 _

f(y) = in/ < ECtj.uCyj,): УкеО(х,гД). О. 2 О. к =1.....п+1

к =1

п+1 п+1 _

Е CLy = у. Е CL = 1>. у 6 О(х.гД) к=1 к =1

Множество Df(y) - субдифференциал выпуклой функции г в точке у из замкнутой окрестности о(х,кД) точки х радиуса кд,

г > К

Df(у) = <seRn: f(z)-f(y) > <s.z-y>. z e 0(х,гД)>, у e 0(х,КД)

Здесь к - максинальная скорость системы (1). Оператор f (7) на элементарном ромбе

S(x,A) = со < yi: yi = х + A'Ti'®!' 1 =1.....n>

фазового пространства Rn имеет простую структуру

f = F(t,A,S,uXx) = f(x) + A «max H(t.x.s) (8)

seDf(x)

Здесь значение f(x) локальной выпуклой оболочки y-»f(y) в точке х и субдифференциал Df(x) определяются формулами

Г (х) = min <u(x), min (u(x + Д.7 -e ) + u(x - Д.7 ))»

12

Df(x) = со <а : k=X.....2n>

°k = (ak.....ak)

= ±(u(x ± •ei ) - f(x)).(A'Ti )_1. 1=1.....n

Оператор g, двойственный оператору f, задается соотношениями для супердифференциалов 5g(x) локальных вогнутых оболочек у-»д(у)

g = g(t-, A.S.uXx) « g(x) + Д »min H(t,x,s) (Э)

seDg(x)

g(x) = max <u(x), max <—— (u(x + Д'7, ) + «j(x - A»7{ )У» 12

Dg(x) = CO <bfc: k=l,...,2n> ■ b)c = (bi.....b">

b* = ±(u(x ± д.7..^) - g(x)).(A>Ti )_1 . i=1.....n

Выпуклая комбинация операторов f(8)hg(9)c коэффици-

18

ентами а.(х), i=i.a

g(x)-u(x) u(x)-f(x)

CL(x) =--СЦ(х) = --(10)

^ g(x)-f(x) ^ g(x)-f(x)

приводит к оператору e с конструкциями субдифференциалов d^iKx) и супердифференциалов d*u(x) В.Ф. Демьянова

Е = E(t,i,s,u)(x) = ai(x).F(t.A.S.u)(x) + Q2(x).G(t,i,S,uX*)=

= u(x) + д.(max H( t, x, s ) + min H(t-.x.s)) (11) sgD^uCx) seD*u(x)

DHu(x) = Ct1(x).Df(x). D*u(x) = Ct2(x).^(x)

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

L(y) = <А.у> + В

наиболее близкой в смысле квадратичного отклонения к множеству значений функции у->и(у)

и = <u(y ): m = 1.....М>

ш

Параметры AeRn, b^r определяются из условия нининунэ

квадратичного отклонения

м г

min £ (u(ym ) " (<А.у>+В )Г (12)

. — - ш ш

А,В ш=1

которое приводит к систене линейных уравнений м м

Е<А.?>'£ = Е u(y_)*£m (13)

ж ш ш . m

Ш=1 Ш = 1

В = —< А, х > + и о о

1 м 1 м

х = х = - £ у . и = - Г и(у )

М ш=1 т ° М т=1 т

£ = у -х . т=1.... , М

то

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

ьа(ъ,Д,и)(х) = и + А 'Н( 1, х, А ) + < а, х-х > (14.)

о о

Доказывается, что выпуклая у-г(у). вогнутая у-^д(у) и линейная у-Цу) оболочки функции у-»и(у), определяемые в окрестности о(х.зпКД) точки х радиуса ЗпКД, связаны неравенствами

г(у) ^ Цу) ^ д(у)

в окрестности о(х,кД) точки х радиуса кД. и, следовательно, операторы г, е являются нижней и верхней оценкой для оператора

ЬА

К( Ь, Д, и )( х ) ^ ЬА(С.Д.иХх) ^ С(Ъ,Д,и)(х)

Обсуждается связь конечно-разностных конструкций к, е, с классическими операторами Годунова и Лакса-Фридрихса.

1 л

Во втором параграфе приводится набор достаточных условий лля конечно-разностных операторов, обеспечивающих сходимость соответствующих аппроксимационных схем. Этот набор включает такие свойства как: условие "генератора" - аппроксимации уравнения Гамильтона-Якоби, свойство "нерасширяемости", свойство непрерывной зависимости от параметров. Доказывается, • что предлагаемые в диссертации операторы с обобщенными градиентами удовлетворяют этому набору. Тем самым устанавливается сходиность аппроксимационных схем в норме пространства непрерывных функций.

Теорема 2.2.2. Пусть функция со есть обобщенное решение задачи (з),(г) в сильно инвариантной области и для разбиения Г=<ь .интервала т с постоянным шагом А.

Л = 1=0.....определена аппроксимационная схема с

любым из указанных операторов р (7) (э (э). е (и), ца (14))

ир(-в.х) = С7(х), (-9.Х) е Ог

ир^.х) = 41 . • )Хх) (15)

Ъ е СЪ ,1 ). (Ъ.х) е , 1=0.....N-1

Тогда аппроксимационная схема (15) сходится к обобщенному решению ш задачи (з),(г). Кроме того, существует константа с такая, что при достаточно налых Д выполняется оценка

|ир - Ш|е < С.Д1/2 (16)

|и-р - Ш| = лох |и-р(их) - ОХ t, ж ) |

Х Г (Ъ.х)е<3 1

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

ь = 7'Д. 7 = сопг(

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

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

U° = U°(t.x) - argmin <s°, B(t,x)u> (17)

ueP

s° = s°(t,x.y°) = argmin < ДН( t ,x. s )+g( y° )-<s, y°-x>> (18) 5еБз(у°)

y°=y°(t,x) = argmin min < ДН( t ,x, s )+g(y )-<s, y-x>> (19) yeO(x.КД) se5g(y)

Здесь y-»g(y): о(х,гД) r - локальная вогнутая оболочка функции y-*u(y) в окрестности ckx.rA). Множество Dg(y) -супердифференциал вогнутой функции g в точке у из окрестности

0(х,КД), г > К.

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

Теорема 2.3.1. Для любых разбиений Г, начальных позиций (t^.x^) и измеримых по Лебегу функций t-»q(t): ct^.fli-Q траектория х( •), порожденная стратегией и° (17)-(19), удовлетворяет оценке

o(x(-ö)) + L.CÖ-t,,)^ (20)

и, следовательно,

а(х('в)) ^ ■* с.д1/г + ^(•е-ь^-А (£1 )

Здесь константа ь. определяется свойствами гамильтониана н.

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

ь = 7>Л. 7 = е(А). е(А) =» о Д-ю

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

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

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

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

оптимального гарантированного результата (ВМФОГР). В случае

23

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

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

В первом параграфе изучаются свойства ВМФОГР. Исследования проводятся в рамках теории позиционных дифференциальных 1 ?

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

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

3 —

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

функция программного максимина (ВМФПМ) в этой задаче. Форму-

24

лируются условия регулярности - условия, гарантирующие совпадение ВМФПМ с ВМФОГР.

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

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

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

процедуры - аппроксимационной схемы. При ее реализации можно

25

использовать конечно-разностные операторы, предложенные во

второй главе. Следует сказать, что в работах И.К. Дольцетты, 1 ?

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

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

1 -г

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

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

1 ?

позиционных дифференциальных игр-. Динамическое равновесие

14

по Нэшу образуется согласно работе А.Ф. Клейменова на основе

решений задач оптимального гарантированного управления. Эти

задачи решаются методами теории обобщенных (минимаксных, вязе р

костных) решений уравнений Гамильтона-Якоби • . 12

Dolcetta I. С. , I shi i H. Approximate solutions of the Bel-lman équation of deterministiс control theory // Appl.

Math. Optimiz. 1984. Vol. 11. No. 2. P. 161-181.

26

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

Во втором параграфе вводится понятие динамической ситуа-14

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

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

вычисляются параллельно со значениями функции цены на сетке. -

Kryazhimskii А. V. Behavioral equilibria for a 2«2 "seller -buyer" game-evolutionary model. Working Paper WP-94-131. 11 ASA. Laxenburg. 1994.

14

Клейменов А.Ф. Неантагонистические позиционные дифференциальные игры. Екатеринбург: Наука. Уральское отделение, 1993. 185 с.

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

Моделируются траектории динамического равновесия по Нэшу.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

4. В дифференциальных играх неограниченной продолжитель-

29

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

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

ПУБЛИКАЦИЙ ОСНОВНЫХ РЕЗУЛЬТАТОВ

1. Субботин А.И., Тарасьев A.M. Сопряженные производные функции цены дифференциальной игры // Докл. АН СССР. 1985. Т. 283. № 3. С. 559-564.

2. Subbotin A.I., Tarasyev A.M. Stability properties of the value function of a differential game and viscosity solutions of Hami 1 ton-Jacobi equations '// Problems of Control and Information Theory. 1986. Vol. 15. No. П. P. 451-463.

3. Tarasyev A.M. Two formalizations of positional strategies // Probiems of Control and Information Theory. 1983. Vol. 14. No. 1. P. 65-73.

4. Тарасьев A.M. Об одной нерегулярной дифференциальной игре

/V Прикл. матем. и мех. 1985. Т.49, Вып. 2. С. 682-684.

30

5. Тарасьев A.M., Ушаков В.Н. Алгоритм построения стабильного моста в линейной задаче сближения с выпуклой целью // В сб.: Исследования задач мининаксного управления. Сзерд-ловск. УНЦ АН СССР. 1985. С. 82-90.

6. Тарасьев A.M. Неравенства для сопряженных производных кусочно-гладкой функции цены // В сб.: Управление с гарантированным результатом. Свьрдловск. УНЦ АН СССР. 1987. С. 86-91.

7. Тарасьев A.M., Ушаков В.Н., Хрипунов А.П. Об одном вычислительном алгоритме решения игровых задач управления // Прикл. матем. и мех. 1987. Т. 51, Вып. 2. С. 219-222.

8. Адиатулина Р.А., Тарасьев A.M. Дифференциальная игра неограниченной продолжительности // Прикл. матем. и нех. 1387. Т. 51, Вып. 4. С. 531-537.

9. Вахрушеи В.А., Тарасьев A.M., Ушаков В.Н. Алгоритмы построения пересечения и объединения множеств на плоскости // В сб.: Управление с гарантированным результатом. Свердлозск. УНЦ АН СССР. 1987. С. 28-36.

10. Tarasyev A.M., Uspenskii А. А. . Ushakov V. Н. Cn construction of solving procedures in a linear control problem // The Lyapunov Functions Method and Appl. Basel.: J. C. Baltzer AG, Scient.-Publ. Co. IMACS. 1S90. P. 111-115.

11. Tarasye/ A.M. The function of an opti Rial guaranteed result of control problems with a vector criterion // Prcb-lems of Control and Information Theory. 1991. Vol. 20. No. 1. P. 25-36.

12. Тарасьев A.M. Программные конструкции в задачах управления с векторным критерием // Прикл. нэтем. и мех. 1991. Т. 55, Еып. 2. С. 212-221.

13. Тзрзсьев A.M., Успенский A.A., Ушаков В.H. Конечно-разностный метод построения функции оптимального гарантированного результата // Сборник избранных докладов. Гага-ринские научные чтения по космонавтике и авиации. Москва. 1991. С. 166-172.

14. Tarasyev A.M. Approximation schemes for construction of the généraiized solution of the Hami1 ton—Jacobi (Bellman-Isaacs) equation // Report No. 371. Institut fur Angewandte Mathematik und Statistic. Universität Wuerzburg. Wuerzburg. 1992. 24 P.

15. Субботин А.И., Тарасьев A.M., Ушаков В.Н. Обобщенные характеристики уравнений Гамильтона-Якоби // Изв. АН.

Техн. кибернетика. 1993. № 1. С. 190-197.

16. Иванов В.А., Тарасьев A.M., Ушаков В.Н., Хрипунов А.П.

Задача тореадора // Прикл. матем. и мех. 1993. Т. 57,

Вып. 3. С. 15-22.

17. Тарасьев A.M. Аппроксимационные схемы построения минимаксных решений уравнений Гамильтона-Якоби // Прикл.

матем. и мех. 1994. Т. 58, Вып. 2. С. 22-36.

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

19. Tarasyev A.M. A differential model for a 2x2-evolutionary game dynamics // Working Paper WP-94-63. IIASA. Laxen-burg. 1S94. 32 P.

20. Тарасьев A.M. Решение эволюционных игр в рамках теории -• уравнений Гамильтона-Якоби // Прикл. матем. и мех. 1995. Т. 59, Вып. 6. С. 965-978.

Подписано в печ. 01.04.1996 г. Формат 60*84 1/16

Офсетная Объем 2,0. Тир. 100. Зак. № 83.

Екатеринбург, К-ЭЗ, пр. Ленина, 51. Типолэборатория УрГУ.