Главная > Разное > Марковские процессы принятия решений
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.2. Условия сжатия и монотонности

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

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

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

Условие сжатия. Существует такое число что неравенство

выполняется при всех

Обозначим решение, принимаемое в точке при политике 8. Определим по формуле

где элемент из пространства V, являющийся образом элемента при отображении т. е. действительная функция, определенная на 2, а значение этой функции в точке Условие сжатия эквивалентно следующему утверждению: Существует такая постоянная что

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

выполняется при всех

Функция называется функцией доходов при политике Оптимальная функция доходов определяется соотношением

Оказывается полезной следующая

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

функции имеет место неравенство

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

Так как

Рассмотрим теперь отображение пространства V в себя, определяемое равенством

при любых и Следующая теорема устанавливает, что отображение А сжатое.

Теорема 7.4. Пусть выполняется условие сжатия. Тогда неравенство

справедливо при любых

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

Ясно, что

Последнее неравенство следует из определения отображения Комбинируя оба неравенства, получаем

Так как неравенство (7.12) верно при любом то Случай рассматривается аналогично. При неравенство тривиально.

В силу теоремы 7.1 у сжатого отображения А существует единственная неподвижная точка, т. е. единственный элемент такой, что

при любом

Уравнение (7.13) представляет собой записанное в довольно общем виде уравнение оптимальности (см. [7]).

Следствие 1. Для любого существует политика такая, что

и выполняется неравенство Если

Доказательство. Из (7.13) следует, что для любого существует политика 8 такая, что

Заменяя в на получаем при любом

Следствие 2. Предположим, что при каждом фиксированном функция является непрерывной по в топологии, в которой множество компакт. Тогда существует политика 8 такая, что

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

Для оператора В, отображающего пространство V в себя, определим его модуль как наименьшее из чисел с таких, что при всех

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

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

Условие монотонности. Если то при любой политике

Это условие эквивалентно тому, что если

Теорема 7.5. Пусть выполняются условия монотонности и сжатия. Тогда

Доказательство. Из следствия 1 теоремы 7.4 вытекает, что Так как при любой политике 8, то, многократно применяя монотонный оператор получаем при всех 8. А поскольку то из последнего неравенства следует, что

Таким образом, решение уравнения (7.13) — единственное и совпадает с функцией оптимальных доходов.

Политику 8 назовем -оптимальной, если и оптимальной, если Следствие 1 теоремы 7.4 и теорема 7.5 устанавливают существование -оптимальной политики, а следствие 2 теоремы 7.4 дает достаточные условия существования оптимальной политики.

Если последовательность удовлетворяет условию при каждом , то будем писать

Лемма 7.1. Пусть выполняется условие монотонности. Тогда если то Если то Если то

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

Рассмотрим условие сжатия порядка, являющееся ослаблением условия сжатия.

Условие -сжатия. Существуют натуральное число и действительное число с такие, что при любой политике 8 модуль оператора меньше или равен с и при всех 8 модуль оператора меньше или равен 1.

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

Определим теперь функцию равенством Чтобы показать, что введем отображение, определенное на V, с помощью равенства . Так как (последнее неравенство следует из условия монотонности и определений операторов то множество значений отображения содержится в Тогда из предыдущего утверждения и условия -сжатия следует, что сжатое отображение. Пусть единственная неподвижная точка отображения Так как то при любой Политике 8. Следовательно, таким образом, Итак, мы доказали утверждения а) — в) следующей теоремы.

Теорема 7.6. Пусть выполняются условия монотонности и -сжатия. Тогда

а) единственная неподвижная точка отображения

в) сжатое отображение, модуль которого меньше или равен с;

единственная неподвижная точка отображений и

Доказательство пп. г) и д) опирается на следующую лемму 7.2.

Лемма 7.2. Пусть выполняются условия монотонности и -сжатия. Тогда

б) для любой политики

в) если , то

Доказательство. Мы докажем только поскольку б) и в) очевидны. Пусть 1 — функция, определенная на 2 и принимающая единственное значение, равное 1, т. е. при всех Предположим сначала, что Тогда при любой политике 8, откуда следует, что при каждом Поэтому для любой политики 8. Следовательно,

Далее, так как при любой политике 8, то

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

т. е. утверждение верно и для что завершает доказательство. Так как то из условия -сжатия вытекает, что Отсюда получаем . Предположим теперь, что число Тогда

Таким образом, мы пришли к противоречию. Следовательно,

Доказательство теоремы 7.6. Пункты доказаны. Как уже отмечалось, Тогда и в силу леммы 7.2 получаем Следовательно, Если то из леммы 7.2 вытекает, что Таким образом, единственная неподвижная точка отображения

Ранее было установлено, что Для доказательства равенства определим функцию и следующим образом:

Тогда для Так как то Следовательно, в силу леммы 7.2 выполняется неравенство откуда вытекает, что Значит, Для доказательства заметим, что Если то откуда следует цепочка неравенств

<< Предыдущий параграф Следующий параграф >>
Оглавление