Задачи на правило остановки в минимаксной постановке тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

12?.

1 О Я 2

Санкт-Петербургский Государственный университет

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

ВИННИЧЕНКО Сергей Викторович

ЗАДАЧА НА ПРАВИЛО ОСТАНОВКИ В МИНИМАКСНОМ ПОСТАНОВКЕ

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата <1>иэико—математических наук

САНКТ-ПЕТЕРБУРГ - 1992

Работа вьполнена в Ч1Тинском институте природных ресурсов СО РАН

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

В.В.Мазалов (г.Чита)

Об1Дие оппоненты — доктор физико-математических на;

В.В.Захаров (г.Санкт-Петербург) кандидат Физико-математических » А.Н.Кириллов (г-Санкт-Петербург:

Ведущая организация - Иркутский Вычислительна Центр

СО РАН

Защита состоится 1ЭЭ2 г. в часов

на заседании специализированного совета КВБЗ. 57.1.6 по присуждению ученой степени кандидата наук при Санкт-Петербургскс государственном университете (1ЭО000, Санкт-Петербург, Васильевский Острое, 1®—линия, д. 33, ауд. В8) .

С диссертацией намно ознакомиться в библиотеке им А.М.Горьког Санкт-Петербургского государственного университета.

Автореферат разослан ^ченьл секретарь Совета доцент

1ЭЭ2 г.

Горьковой В.Ф.

..- • • :-. '..-ц.:-:;! ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

3. Разработаны численные метопы решения многошаговых задач оптимальной остановки, которые вошли в пакет прикладных программ ОСТАНОВКА, разработанный в Читинском институте природных ресурсов СО РАН.

Апробация работы. Результаты диссертации докладывались на II областной конференции молодых ученых Читинской области "Природные ресурсы Забайкалья" (Чита, 1987),

I—III Школе "Математические проблемы экологии" (Чита,19В6,198В, 1990), конференции "Методы математического программирования и программное обеспечение"(Свердловск,19В7),

Всесоюзной конференции "Вероятностные методы в дискретной математике" (Петрозаводск,1988).

Публикации. Основные результаты опубликованы в печатных работах /1-6/.

Структура и объем работы. Диссертационная работа содержит введение, 4 главы, приложение, список литературы, включающий ТВ наименований. Объем работы составляет 85 страниц машинописного текста.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Задачи оптимальной остановки берут начало с работы А.Вальда "Последовательный анализ", 1947 г., в которой был предложен новый метод различения двух просты.- гипотез, который называется последовательным критерием отношение вероятностей. Особенностью этого метода было то, что окончательное решение выносилось не при Фиксированном объеме выборки, а определялось в процессе получения наблюдений. Второй проблемой, которая вызвала большой интерес к задачам оптимальной остановки, была задача о скорейшем обнаружении момента изменения свойств случайного процесса. Метод решения этой задачи и его обоснование были получены в работах Е.Пейцжа "Continuous inspection schemes", (1954) и А.Н.Ширяева Об оптимальных методах в задачах скорейшего обнаружения, 1963 г. Интерес к этой проблеме обусловливается ее практической значимостью в оёлас

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

В 1966 г. Д.Гильберт и Ф.Мостеллер предложили исследовать задачи оптимальной остановки в минимаксном варианте. Минимаксным задачам оптимальной остановки быпи посвящены работы В.К.Доманского, М.Сакагучи, Р.Я.Читашвили, 3.Л.Пресмана, И.М.Сонина, Е.3.Ференштейн, Д.Еннса, В.В.Мазалова и др.

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

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

Рассмотрим оптимизационную постановку такой задачи. Пусть задана случайная величина 1 с плотностью распределения вероятностей на СО, 13 и натуральное число п . Наблюдатель последовательно производит п+1 наблюдение случайной величины 1 . На любом шаге наблюдатель может взять полученное на этом шаге значение случайной величины и прекратить наблюдения или продолжить наблюдения. Если наблюдатель выполнил все наблюдения, то он обязан взять последнее наблюденное значение.

Пусть Т(1) - некоторая невозрастающая функция на СО,13, не являющаяся тождественно постоянной на (0,1). Рассмотрим задачу оптимальной остановки, цель которой минимизировать математическое ожидание ~Т~ (■Х'Х.) , ~ТГ - момент остановки. Будем считать,

что (р (-£) не равно нулю почти всюду. Правило остановки является набором измеримых подмножеств

{ОО , П

(1.1)

Если Оь > то следиет останавливаться на шаге а , если

£ , то следует продолжать наблюдения. Пасть Х^ оеозначае характеристически» фуыкцим 0 С СО. -¿-7 ■ Тогда плотность распределения вероятностей ^(Ь) результата наблюдений для

правила остановки 'С 0{ У описывается формулой

П-Ы t-1

fltJ^Zt (¡7 /< ^j^oi <Р(±} u-2'

где ^/У - мера с плотность» СрЦ) . 0-1 ~ дополнение

множества 0\, в С 0,1-7 <

О считается равным СО, 13.

Математическое ожидание ~Г{~Ьх 1 равно

/Л (TUj)) ^ I if(i)TU)d(

(1.3)

Введем величины , Ащ) в соответствии со следьюшш

условиями:

1

¡pitJ Ti-tjfk

С 1 . 4)

X* - есо,а | T(V~-A^Jr (l.s)

Aw ^ J ерш Tit)<U +Am+i f (pivcbt

(i.6)

Тогда выполняется следующая теорема: Теорема 1

Задача на правило остановки V имеет решение в виде правила

М■="■ ■ •„ /1 определяйте

остановки „ П где ■ П

<13 асловий С1. 4) , (1.5) , < 1.6) .

Задача на максимизацию Т~ (^Ст) решается аналогично с той разницей, что полагается равным (Д, ОСт ]

Рассмотрим следующий пример.

Пусть Т(0=-Ъ и Ср(~Ь) 5 -/ .В этом случае

Оптимальные пороги определяются из реккирентного соотношения

-J-m-i " 2

-г = L .г ~ S _ SJL

-Л-И -г J - <g ~ dsi' '" (1-S)

Максимальное значение математического ожидания / равно

Теорема 2

Пасть T(t) адовлетворяет условиям теоремы 3 и< кроме того,

о<с< 1, т(t) =а для te-iC^JJ, ¿¿m

■t -~C-'

Тогда для того, чтоёы выполнялось ¿С)у\ — С для m=l.....п

необходимо и достаточно выполнения неравенства

i

f срЮ т ^ в (1.9)

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

СО,13x1:0,13 неасываишап по первому аргументу и невозрастамщая по второму, причем для любого X. &СО, Л +(у)=А(х^> и а(ч)=й(у,х) являются Функциями не постоянными на (0,1). Имеются рве независимые одинаково распределенные случайные величины и X «

•ЗаЦаимЫй плетыеет&ю распределения вероятностей ср (О на ГО, 13.

б

Задано число наблюдений п+1. Игроки I и II получают значения I: и * из отрезка СО,13 описанным выше спосоеом. Выигрыш первого игрока составляет А(Ь,и), второго - —

Стратегиями игроков I и II считаем пороговые стратегии. Верна следующая теорема:

Теорема 3. Игра Г* имеет решение в чистых стратегиях. Пасть ; £ (о, 4> , Ро - (О-х,..Цо" (аа> ■ V .

Введем обозначения

1

HjliJ^/ A (is W) <Рп Що < у

Н3M=f A (t, w) <Фп (p0j±)cU (i.u,

С1. 10)

Су - ¿ил Н, Ю , dt •= &т Н, Ш

С2 = ¿от <LZ- Cwi hAifJ ;i

ъг—il; -hi-ЦТ

Попустим, что

ад

имеет постоянное значение при С>-с

(/(}> С^ г а имеет постоянное значении ¿/^ при >■ (Л-у ,

С2 •

Пусть выполняются условия

J

0

Hi И) cp{t)dA

- / у

Ну i'iv/ Cp(.W)ilW ^ с?

Тогда верна следующая Теорема 4.

Пара стратегий Срр; ^.р) является решением игры /"*

Б главе 2 рассмотрена следующая постановка вацачи.

N-4

- две совок^пно1.1и

Пысть

независимых одинаково распределенных случайных величин с непрерывной функцией распределения . Игроки I и II помечают

?

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

времени Ту и , 1 < А/ч- 4 , Т* ^ /[/■+!

которые еудем предполагать моментами остановки - стратегии в антагонистической игре / 'д/ с функцией выигрыша

Н( -с 1 = Н< х^р И . 14)

Ищется ситуация равновесия в игре Доказана следующая теорь-ма:

Теорема. Оптимальными стратегиями в игре Г// являются стратегии Т, ■ ^ ) и ^ • определенные с

помощью порогов СС* . . , где ^ • •■у

решение системы уравнении (1. 13> — (1. 17):

А/

Ч- г,- • . . . ( + ... ^ п .: 5)

4-У

+ - В с 1.16)

Х^РмУ > 8-------

В главе 3 рассмотрена задана о^ олтииальиое управлении процессом босстанавлени)! как в общей постановке, которая применяет^ к случаю, когда на каждом шаге процесса восстановления решается задача на правило остановки, описанная в главе 1.

Рассмотрим следующий управляемый случайный процесс восстановления. Пусть Р - некоторое множество, Т(х) — непрерывная Функция, определенная на Г0,1]. Пусть для каждого 5 £г ^ задана плотность вероятностного распределения на ГО, 13.

Пусть частица находится а точке и<0 . Управление заключается с

выборе 5е 5 ■ Затем производится наблюдение случайной величины й заданной распределением на ГС, 13, получается значение

±0 ее0,43 , и частица перемещается б точкч ЭС -1- ТГр , Так

происходит, пока частица не пересечет нуль. Функция [— о) ~~$

называется управлением в процессе восстановления. Уравнение восстановления для данного управления ц записывается как

I

Т(х) - ±-г У T(x+tJ cU (;.3S>

Если Т(>;)=0 при >:50, то Т(х) имеет смысл среднего времени

движения частицы до пересечения нуля.

Рассмотрим управления, которые дают- минимальное и максимальное значение Т(>;). В этич случаях уравнение босс тановпения записывается в виде

_ _ /

' .X) - / -г- Utfr f //is, a Tix-^xJdd и.39)

its- °

■I

ТЫ) мр f (f(Ssi)T(x+Vdi (1.20)

seS

Будем предполагать, что ТЫ) является суммируемой функцией на каждом ограниченном интервале. Пусть Функция (^(¿^■Ъ) удовлетворяв следующим условиям: Пля всех $€5 и ^ -

некоторое положительное число. Существует Функция (£} такая, что ¿ипс1ц)~0 и для каждого <ге-5 £ | с1Ц) , здесь и

далее ^ — мера Лебега.^ Пысть Т<х) удовлетворяет уравнении (1.1В) и пусть 1/~ ■ Положим Р(х)=х/у. Аналогично

для (ОС) 4 удовлетворяюшего уравнению (1.19) и

1/> - положим ^ IX)- • При этих условия»

верна следующая

Теорема 1. Существуют пределы IX) ^

Шп F, (х)

' п

Теперь рассмотрим процесс выбора наблюдении I , описанный

в главе 2 с заданным распределением вероятностей ¿pit) на СО,13 и числом наблюдений п, удовлетворяющим описанным условиям. Пусть наблюдатель находится в точке х<0 , выбирает ~ta с помощью процесса Г' и перемещается в точку DC + "td . Если JC+t0<- О , то этот процесс повторяется до тех пор, пока наблюдатель не пересечет нуль. Рассмотрим вопрос о стратегии минимизирующей или максимизирующей математическое ожидание числа u/агов.Задача сводится к решению уравнения восстановления

4

TUJ Л0 J Ifl^-tJ ТШМ (1 ,п

seS V

для случая максимизации или к решению уравнения восстановления (1.20) где

а = iT* (/7 и/) ls. (i) ери)

i-i

Ь = lo,12

n

Ui =

f(~t) di

•r i.:

При этих условиях решение задачи на минимизацию ~~[х) имеет

асимптотику

V L

(1.23)

при JC'

\J-JUp Si \J(SA>M

Sé'¿ 0 '

(1.24)

С - некоторая постоянная, а решение задачи на максимизацию —

асимптотика

,1.25)

при ¿С ~~ > где

^ - /Ь </^¿¿61 (1.26)

С/ - некоторая постоянная. Кроме того, данные управляемые

процессы восстановления имеют непрерывные стратегии

А .' ^ О)£ : (—-5" соответственно,

причем К^О-Ф}

. ^ Г С-»- '

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

Т (ЭС) - Л I £ !1.27)

при - ( Л J ^ X <" - /1

Рассмотрим задачу минимизации Т(х) для п^О. Доказана следующ; теорема.

Теорема. Существует 2, -1< 2 < О такое, что для г< х < О (—к,...,-х> является оптимальной стратегией поведения и

Тех» - {-+ {-х)п е

у?"

п

ТГ+Г

является решением уравнения (1.18).

В оеГщем случае уравнения (1.18) и (1.19) могут еыть решены сеточными методами. Этот метод нахождения оптимальных стратегий поведения и Функции Т(х) Ёыл реализован на языке фортран-77, программа входит в состав пакета ОСТАНОВКА.

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

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

Пусть игроки I и II находятся в точках x,Y<0. Пусть заданы независимые случайные величины ХщY с плотностью распределения ip(t) на Задано число наблюдений п+1. Игроки проводят

независимо друг от друга наблюдение этих случайных величин как аписанно в главе 1. Они получают значения t и v. после чего игроки перемещаются в точки x-t-t и y+v соответс гвенно. Процесс лроаолжает-ся до тех пор, пока хотя бы один из игроков не пересечет нуль. Рыиг — равшим считается игрок, который пересечет нуль первым. При одновременном пересечении нуля обоими игроками игра считается закончившейся вничью.

Игра rj,j может йыть сформулирована следующим образом. Игроки I и II пользуются множеством порагааы,, стратегий • Т'х,»;

будет йёьзначать Функции», равную йж^-даимиг-и ьыпгрыиу игйОг-а I пр■ оптимально..:: стратегия-, обоих игроков. Тогд^

т<х,у) = 1 т<х,у)=-1 Т(л,у;=0 , ^-û У>(?

При >:,у<0 функция ТО,,у) удовлетворяет следующему уравнению восстановления :

J I

TtK у) = ЯФ utl / ^ ./ // <р ПА) фп issu'h

рЛ fis с о, а» о о " ' 7 'UJ

* Т(х + i; у+гО dv cU dpfvctcf, is) ■

где S - множество смешаных стратегий игроков I и II.

функция Т<х,у) антисимметрична и обладает следующими свойствами;

Т(>:,у) возрастает по х на , строго возрастает по :: нл

0) г убывает по у на , строго убывает по у на

(- <4, 0>

Поведение Функции выигрыша Т(>:,у) при малых значениях к, у описывается следующей теоремой:

Теорема. Существует последовательность чисел таг,ая, что

О ¿'Îfri* 4 для каждого n, êcfH и для любых х , у таких, чго naps

Л—

стратегий (-х,.--,-х), <-у,-.-,-у) является решением игры

Рассмотрим случай., когда срС-Ов! и О^-Х,. -¿л . В этом

случае для функции выигрыша Т<х,у) мо»ет быть получено явное выражение:

(---

В общем случае уравнение (1.29) мотет быть решено сеточньки методами. Этот метод был реализован в виде подпрограммы QGONKA на языке ЧЬртран—77 на компьютере 1114-PC. Подпрограмма входит в состав пакета ОСТАНОВКА.

Работы, опубликованные по теме диссертации:

1. Винниченко C.B. Некоторые игры на случайны:« процессах , В сб.Природные ресурсы Забайкалья (Тезисы докладов II обл. конц>. мол. ученых Читинской обл.), >-^1та: ЧИПР СО АН СССР, 19872. Винниченко C.B., Мазалов В.В. l/fr-ры на правило остановки последовательности наблюдений фиксированной длины, Кибернетика, 1983, N 1, с. 122-124.

3. Винниченко C.B., Мазалое В.В. Оптимальная остановка наблюдений в задачах управления случайньми блужданиями. Теория вероятн. и ее примен., т.35(1990), вып. 4-, и-SSB—676.

4. Винниченко C.B., Мазалов В.В. Игровая задача на правило остановки последовательностей независимых случайных наблюдений, В сб. Математические проблемы экологии (Тезисы докл. I школы), Ч-1та : "-ИГР СО АН СССР, 198S.

5. Винниченко C.B., Мазалов В.В. Минимаксные задачи на правило остановки наблюдаемых процессов, В сб. Методы математического программировании и программное обеспечение (Тезисы кожр.) Свердловск: МММ УрО АН СССР, 1987.

6. Винниченко C.B., Мазалов В.В. Об оптимальном управлении процессом восстановления, В сб. Вероятностные методы в дискретной математике, (Тезисы докл. Всесоюзной конч>.) Петрозаводск, КФ АН СССР, 1988.