Главная страница
qrcode

Модифицированное уравнение Беллмана. Модифицированное уравнение беллмана для эргодических марковских цепей с доходами


Скачать 360.5 Kb.
НазваниеМодифицированное уравнение беллмана для эргодических марковских цепей с доходами
Дата01.01.2020
Размер360.5 Kb.
Формат файлаdoc
Имя файлаМодифицированное уравнение Беллмана.doc
ТипДокументы
#67333
Каталог

УДК 519.2

© 2011 г. А. А. ИБРАГИМОВ, канд. техн. наук

(филиал РГУ нефти и газа им. И. М. Губкина в г. Ташкенте)
МОДИФИЦИРОВАННОЕ УРАВНЕНИЕ БЕЛЛМАНА ДЛЯ ЭРГОДИЧЕСКИХ МАРКОВСКИХ ЦЕПЕЙ С ДОХОДАМИ
Управляемые марковские цепи с одним эргодическим классом и, возможно, с невозвратными состояниями изучаются с помощью операторов сжатия. Строится модифицированное уравнение Беллмана, позволяющее найти оптимальные стратегии не только на конечном, но и бесконечном горизонте. Представляется IBm
1. Введение

Пусть задана управляемая марковская цепь с критерием средних доходов за единицу времени, удовлетворяющая условиям: 1) любая стационарная стратегия задает марковскую цепь с одним эргодическим классом и, возможно, с невозвратными состояниями; 2) каждый эргоди-ческий класс не имеет циклических подклассов. Такую управляемую марковскую цепь назовем регулярной марковской моделью и обозначим RMM. Этот случай, по существу, является основным, заслуживающим внимания с точки зрения задач, встречающихся на практике.

В [1], [2] RMM рассматривается как частный случай общего марковского процесса принятия решений (структура цепи может меняться в зависимости от стратегии).

В настоящей работе, опираясь на одно замечательное свойство неотрицательно регулярной цепи Маркова (теорема 1), строятся операторы сжатия, неподвижная точка которых определяют оптимальное значение критерия качества стратегий RMM. С помощью их: 1) строится модифицированное уравнение Беллмана, позволяющее найти оптимальные стратегии RMM не только на конечном, но и бесконечном горизонте управления, 2) изучается вопрос существования стационарной оптимальной стратегии RMM, 3) определятся оптимизационная схема последовательных приближений, которая порождает целый класс итерационных алгоритмов, позволяющих решать задачи оптимизации достаточно больших размерностей.

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

Из результатов данной работы получается утвердительный ответ на поставленный Д. Бертсекасом и С. Шривом вопрос [7, c. 25]: можно ли схему оптимизации, основанной на принцип сжатых отображений, эффективно распространить на модель динамического программирования со средним доходом за единицу времени.

2. Постановка задачи

Пусть имеется управляемая марковская цепь с конечным множеством состояний S= {1, 2, …, N} и конечными множествами управлений (решений) Ui
k
iiS).

Элемент f = [uiiS) из пространства F = UUUNui
U
ifffnfnn-м шаге, а uin) (i-й элемент вектора fni. Стратегия вида f = (f, f, …, f, …) называется стационарной. Каждой решающей функции fF заданы матрица вероятностей переходов N× N) и (N× 1)-мерный вектор доходов kuiUiF — множество стационарных стратегий.

Для управляемых марковских цепей с конечным горизонтом n цель управления состоит в максимизации (N× 1)-мерного вектора суммарных средних доходов за n шагов

(1)

в множестве стратегий П = {π}, где Pt
P(fP(fP(ftPI(I — единичная матрица размера N× N); i-й элемент Vn() отвечает начальному состоянию процесса iS.

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

(2) Г(π) = lim inf Vn(π) / nпри n ∞.

Здесь начальному состоянию iSотвечает i-й элемент gi
Стратегия π**П оптимальна, если Г(π*) ≥ Г(π) для всех πП.

Наша цель — решить задачу оптимального управления регулярных марковских моделей с вектором средних доходов за единицу времени Г(π) с помощью принципа сжатых отображений и функционального уравнения Беллмана, и разработать эффективные методы нахождения оптимальных решений (π*, Г(π*)) таких моделей.

3. Вспомогательные результаты

Обозначим VN множество N-мерных вектор столбцов. Вектор из VN, все элементы которого равны единице, обозначим 1 (векторная единица).

При фиксированной стационарной стратегии fF RMM характе-ризуется положительно или неотрицательно регулярной цепью Маркова с матрицей вероятностей перехода P( f). Согласно теории цепей Маркова [8] в этом случае существует предельная матрица f) = [αif)](iS)VN. Иначе говоря, P*( f) = 1α( f). Вектор α( f) есть финальное распределение вероятностей, удовлетворяющее уравнению α( f) = α( f)P( f) при условии α( f)1 = 1. Отсюда и из (2) следует, что

(3) Г( f) = P*( f)r( f) = 1α( f)r( f) = g( f)1,

где g( f) — скалярная величина (называется прибыль).

Таким образом, для RMM в множестве стационарных стратегий F предельный средний доход не зависит от начального состояния iS, т. е. gif) = g( f) для всех iS.

Лемма 1. Для RMM справедливо равенство

V n(f ) = ng( f )1 + v( f ) + εnf ), n ≥ 1,

где εnf) → 0 при n→ ∞ и

v( f) =
Доказательство (см. [2], c. 42).

Элементы vif), iSвектора v( f) называются весами, а величины vif) – vsf), iS\{s}, где sпроизвольный элемент S— относительными весами.

В [1], [2] RMM рассматривается как частный случай общего марковского процесса принятия решений (при фиксированной стратегии f множество состояний разбивается на несколько эргодические множества и невозвратное множество, которые могут меняться в зависимости от стратегии f). Согласно замечанию в [2, c. 82] итерацион-ный алгоритм Ховарда для RMM может быть представлен в следующем виде:

1. Для выбранной решающей функции f= [ui
(iS) Fрешить систему уравнений

(4)
i
S

относительно весов vivif), iS и прибыли g = g( f) полагая vssS, где k= ui
2. Используя найденные значения g и viiS, найти при каждом iSрешение


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

Решающую роль в изучении RMM играет следующая

Теорема 1 [6, 9]. Пусть марковская цепь, задаваемая матрицей P= || piji, jN), положительно или неотрицательно регулярна. Пусть Qsматрица размера (N– 1)×(N– 1), полученная из матрицы P вычитанием произвольной s-ой строки из оставшихся N– 1 строк и вычеркиванием s-ой строки s-го столбца. Тогда спектральный радиус ρ(Qsматрицы Qs меньше единицы.

4. RMM в стационарном режиме

Приведем некоторые свойства RMM в множестве стационарных стратегий F. Поскольку в данном разделе рассматривается конкретная стационарная стратегия fF, для краткости, соответствующие ей вектор доходов r(f) и матрицу вероятностей переходов P( f) будем обозначать через rи P соответственно, а их элементов k.

Пусть величина n при стационарной стратегии fF. Тогда в силу (1) имеет место рекуррентное соотношение

(5) iS

Лемма 2. Для RMM при любом sS справедливо равенство

(6)

для всех iSs и n≥ 1 при произвольном jSs где SsS\ {s}.

Положим

iSs
(7)
Теперь равенство (5) может быть записано в виде

(8)
Величины
Введем величину σiji, jS) такую, что σiji jи σiiijijij
Лемма 3. Для RMM при любом sS существуют конечные пределы При этом имеет место равенство wsg( f) и разло-жение

(9)
Предложение 1. Для RMM величины представляют собой относительные весы.

Предложение 2. Для RMM система уравнений (9) имеет единствен-ное решение, такое, что

(10) wsg( f ), wivif ) – vsf ), iSs.

Предложение 3. Для RMM, прежде чем решать соответствующую систему уравнений Ховарда (4), можно приравнивать к нулю любое из весов viiS.

Таким образом, в случае неотрицательной регулярной цепи, вопреки утверждению в [2], нет необходимости отыскивать (при большом Nэто достаточно сложно) некоторое существенное состояние s, чтобы положить vsvN
5. Построение операторов сжатия для RMM

Перейдем теперь к изучению RMM с помощью операторов сжатия.

Рассмотрим оператор L( f), отображающий пространство VN–1 в себя, определяемый равенством

L( f ) (w)sLiuiw)sLsusw)siSs
где (w)swwswswNT V N –1,


Теорема 2. Для RMM при любой fF оператор L( f) является на VN–1 сжатием. При этом L( f) имеет в VN–1 единственную неподвижную точку (w(f))s и последовательные приближения

(11)
сходится к (w( f))svif) – vsf)] (iSsначиная с любого (w0)sN–1, причем при n→ ∞.

Данная теорема показывает, что задача нахождения предельного среднего дохода gи относительных весов wiiSsNвелико и применение метода Гаусса для решения системы уравнений Ховарда (4) невозможно.

Следует заметить ещё одно достоинство рекуррентной процедуры (7)-(8), состоящее в том, что при ее реализации можно прекратить вычисление на любом шаге итерации и использовать приближенные значения wnдля улучшения решения и принять wnв качестве начального приближения для нового решения. Далее будет обсужден вопрос о возможности такого подхода в нахождении стационарной оптимальной стратегии RMM.

Рассмотрим теперь оператор Λ, отображающий пространство VN–1 в себя, определяемый равенством

(12) Λ(w)siw)siSsw)sN –1,

где
Поскольку w)sN–1, где ( f)suususuN( f).

Теорема 3. Для RMM оператор Λ является на VN–1 сжатием. При этом Λ имеет в VN–1 единственную неподвижную точку (w)s и последо-вательные приближения

(13)
сходится к (w)sначиная с любого (w0)sN–1.

6. Модифицированное уравнение Беллмана

Рассмотрим RMM с конечным горизонтом n. Критерий оптималь-ности в этом случае характеризуется величиной Vn(π) — (N× 1)-мерным вектором суммарных средних доходов (1). Здесь стратегия π определяется как последовательность (…, fnfn–fF, где fnnшагов до окончания процесса принятия решений. Множество таких «восточных» стратегий обозначим
Vn(π) = r( fnP( fnVn1(π), n≥ 1,

где V0(π) = 0 (нулевой вектор столбец).

Определение 1. Стратегия π*равномерно оптимальна, если для любой стратегии πn≥ 1 выполняется неравенство Vn*) ≥ Vn(π).

Заметим, что если стратегия π*
Равномерно оптимальная стратегия π* =
(14)
при начальном условии
Определение 2. Стратегия πквазистационарна, если, начиная с некоторого n′< ∞, имеет место равенство fnf для всех nn′.

Напишем рекуррентное соотношение (13) в развернутом виде

(15)
где
Рекуррентные соотношения (15) назовем модифицированным урав-нением Беллмана.

Поскольку для RMM в (15) wnwпри n→ ∞, то справедливо

Следствие 1. Для RMM стратегия πпорожденная модифици-рованным уравнением Беллмана (15) с соблюдением правила выбора решения, квазистационарна.

Теорема 4. Пусть для RMM в функциональном уравнении Беллмана (14) начатом и в модифицированном уравнении Беллмана (15) начатом соблюдено правило выбора решения. Тогда, решаю-щие функции {fnи порожденные рекуррентными соотношениями (14) и (15) соответственно, являются идентичными, т. е.

(16) для всех n= 1, 2, … .

Следствие 2. Для RMM стратегия πпорожденная модифици-рованным уравнением Беллмана (15), равномерно оптимальна.

Следствие 3. Для RMM стратегия πпорожденная функ-циональным уравнением Беллмана (14) с соблюдением правила выбора решения, квазистационарна.

Например, в задаче водителя такси [1], [2] решающая функция fT, полученная методом динамического программирования, начи-нает повторяться уже с третьего шага итерации; fff
Теорема 5. Для RMM стратегия π*порожденная модифи-цированным уравнением Беллмана (15) начатом доставит критерию оптимальности Г(π) максимальное значение, причем все компоненты вектора Г(π*) равны между собой.

Следствие 4. Для RMM существует стационарная оптимальная стратегия, максимизирующая средний доход за единицу времени.

Следствие 5. Для RMM последовательность решающих функций {fnn= 1, 2, …}, порожденная модифицированным уравнением Беллмана (15) с соблюдением правила выбора решения при любом начальном приближении сходится к пределу f *F такому, что f * — оптимальная стратегия, причем и n→ ∞.

Следствие 6. Для RMM система функциональных уравнений


имеет единственное решение (w)s
w( f *))s такое, что wivif *) – vsf *), jSsпричем wsg( f * ), а f * — стационарная оптимальная стратегия.

Таким образом, модифицированное уравнение Беллмана (15) позволяет решать задачу оптимизации RMM как на конечном, так и бесконечном горизонтах. При этом, в случае бесконечного управления, итерационный алгоритм (15) выгодно отличается от итерационного алгоритма Ховарда отсутствием необходимости решения систем линейных алгебраических уравнений в каждой итерации, а в случае конечного управления, выгодно отличается от функционального уравнения Беллмана (14) отсутствием проблемы переполнения памяти ЭВМ за счет значения суммарных средних доходов n могут превышать возможности запоминающего устройства ЭВМ.

7. IBm-метод динамического программирования

Положив L1( f) ≡ L( f), Λ1 ≡ Λ введем на VN–1 операторы вида

(17) Lm( f )(w)sL( f )Lm–1( f )(w)sm = 2, 3, …, (w)s N –1;

(18) Λm(w)sLm( f *)(w)sm = 2, 3, …, (w)s N –1,

где элементы f* определяются равенством
Теорема 6. Для RMM оператор Λm при любом m≥ 1 на VN–1 являет-ся сжатием. При этом Λm при любом m≥ 1 имеет в VN–1 единственную неподвижную точку (w)sw( f * ))s такую, что wivif * ) – vsf *), iSsпричем wsg( f* ), а f * — оптимальная стратегия.

В соответствии с (17) и (18) и принципа сжимающих отображений для заданного m≥ 1 образуем, так называемое, m-уравнение преобразова-ние относительных оценок


Эти соотношения могут быть записаны в развернутом виде

(19)
где
Метод последовательных приближений, определенный рекуррентными соотношениями (19) назовем IBm-методом динамического программирования. Заметим, что IB-метод представляет собой модифицированное уравнение Беллмана (15), а IB-метод — итерационный алгоритм Ховарда, изложенного в разделе 3.

Введем отношение> на множестве VNследующим образом: a> b, если aibii≤ Nи ab( a, b VN).

Лемма 4. Для RMM если при некотором

(20)
то где
v( f) — вектор весов.

Следствие 7. Для RMM если при некотором

(21)
и хотя бы для одного iS неравенство (21) строго больше, то где
(w( f))sv(f) – vsf)1)sвектор относительных весов.

Теорема 7. Для RMM при любом конечном или бесконечном m последовательность решающих функций {fnn= 1, 2, …}, порожденная IBm-методом (19) с соблюдением правила выбора решения при любых сходится к пределу f*F такому, что f* — оптимальная стратегия, причем и iSs при n→ ∞.

Следствие 8. Для RMM для любого конечного или бесконечного m существует конечное число kmтакое, что стратегия πпорож-денная IBm-методом (19) с соблюдением правила выбора решения, квази-стационарна такая, что fnf* для всех nkm, где f* — оптимальная стратегия.

Теорема 8. Для RMM найдется конечное число mIB≥ 1 такое, что стратегия f* , полученная из соотношения IBm-метода (19)


будет оптимальна при любых mmIB.

Следствие 9. Для RMM скорость сходимости IBm-метода (19) возрастает с возрастанием m и максимальна при mmIB.

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

Итерационный алгоритм 1:

1. Задать ε > 0, sS и m≥ 1. Выбрать произвольное (w0(m))sN–1.

2. C помощью (19), соблюдая правило выбора решения, вычислить wn(m) до тех пор, пока не будет выполнено условие fnfn
3. Если || (wn(m))swn–1(m))s4. Положив (w0)swn(m))sw( fnswn(m))sw( fns
При значении параметра m=mIBmIBmIBm= 1. Если при этом, субоптимальная стратегия окажется неоптимальной, то на следующем шаге итерации mувеличивается на одну единицу. Эти соображения приводят к следующему варианту оптимизационной процедуры с переменным параметром m.

Итерационный алгоритм 2:

Этот алгоритм отличается от итерационного алгоритма 1 тем, что в пункте 1 полагается m= 1, а в пункте 4 — m= m+ 1.

8. Заключение

Отправной точкой анализа RMM послужило утверждение теоремы 1. Опираясь на него, построен оператор сжатия (13), определяющий алгоритм итерации решающих функций — модифицированное уравнение Беллмана (15), которое при конечном горизонте порождает оптимальную марковскую стратегию, а при бесконечном горизонте сходится к решению RMM в стационарном режиме. Модифицированное уравнение Беллмана (15) позволило установить существование стационарной оптимальной стратегии (следствие 4) и выявить одно замечательное свойство функционального уравнения Беллмана (14) (следствие 3).

Для RMM построен IBm-метод динамического программирования (19), который при m= 1 представляет собой модифицированное уравнение Беллмана, а при m= ∞ — итерационный алгоритм Ховарда для управляемой марковской цепи с одним эргодическим классом и, возможно, с невозвратными состояниями. Тем самым он является одновременно их обобщением и развитием. Следует отметить, что IBm-метод динамического программирования при любом m(1 ≤ m< ∞) выгодно отличается от итерационного алгоритма Ховарда отсутствием необходимости решения системы линейных алгебраических уравнений в каждой итерации. Такое положение позволяет решать задачи оптимизации управляемых марковских цепей достаточно больших размерностей при критерии средних доходов за единицу времени.

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

ПРИЛОЖЕНИЕ

Леммы 2-3, предложение 2, теоремы 2-4, теорема 5 и ее следствия 4-6 представлены и доказаны в рамках регулярных марковских игр (см. [6]). Заметим, что когда один из двух игроков пассивен (не имеет возможности выбора стратегии), регулярная марковская игра представ-ляет собой RMM.

Доказательство теоремы 6. Как показано в [6] для матрицы Qsf) из теоремы 1 существует матричная норма L(f), что следует из соотношения L(f)(w)sd(f) + Qsf)(w)sd(f) = N–1, k= uiUil= usUsLm(f) вытекает из равенства w)sw′′)sN–1 || Lm(f)(w)sLm(f)(w′′)s)sw′′)sm|| (w)sw′′)sLm(f) есть оператор сжатия. Рассуж-дения, аналогичные использованным при доказательстве теоремы 3 (см. [6], теорема 3), приводят к тому, что || Λm(w)sm(w′′)sm||(w)sw′′)sm есть сжатия.

Пусть (w)sm. Тогда справедливы равенства (w)sm(w)sLm(f * )(w)sL(f * )(w)sf* определяются равенством mL(f * )(w)sL(f * m(w)sL(f* )(w)sL(f * )(w)sm. Но Λmимеет на VN–1 единственную неподвижную точку и, следовательно, L(f *)(w)sw)s
Доказательство леммы 4. Пусть γ — (N× 1)-мерный вектор такой, что γ = fи f из Fсогласно (4) имеем

(П.1) g( f)1 + v( f) = r( f) + P( f)v( f),

(П.2) g( f )1 + v( f ) = r( f ) + P( f )v( f ).

Вычитая (П.2) из (П.1) и полагая Δg = g( f) – g( f), Δv = v( f) – v( f ), получим Δg1 + Δv = γ + P( fv. Умножая обе части этого равенства слева на предельный вектор α( f), получим Δg = α( fg1 = α( f)γ ≥ 0, поскольку αjf) ≥ 0 при всех jSв силу предположения неотрицательно регулярности цепи Маркова. Далее достаточно доказать, что Δg 0. Предположим противное, т. е., что Δg= 0. Тогда g( f) = g( f) и условие (21) эквивалентно неравенстве r( f) + P( f)v(f)> g(f)1 + v(f). Умножая обе части этого неравенства слева на предельную матрицу P*(f), получим P( f)v( f)> P( f)v( f). Это противоречие доказывает лемму. Лемма доказана.

Доказательство теоремы 7. Согласно теореме 6 последователь-ность {(wn(m))sn≥ 1} при любом конечном mсходится к (w)sm. Значит, если будет соблюдено правило выбора решения, стратегия π = fm= ( f, f, …, f) — последовательность, состоящая из mоднотипных элементов вида f, порожденная IBm-методом является квазистационарной, т. е. найдется конечное число kmfnf *для всех nkmf * оптимальная стратегия.

В случае m= ∞ на каждом шаге итерации nимеем решающую функцию fnS), либо имеет стационарное улучшение fnS); тогда согласно следствию 7 g( fn) > g( fnkfnf *, которая не имеет стационарных улучшений. Следовательно, она должно быть искомой, об-разующая оптимальную стационарную стратегию f * . Теорема доказана.

Доказательство теоремы 8. Поскольку для
|| (w( f * ))swn(m))sm(w( f * ))sm(wn - 1(m))s
≤ ρm|| (w( f * ))swn - 1(m))sw( f * ))sv( f * ) – vsf * )1)s
скорость сходимости IBm-метода возрастает с возрастанием m. Следовательно, для целых чисел kmm ≥ 1 определенных выше, имеет место неравенство kmkmkmm ≥ 1} ограничена снизу числом kmIBkmk* для всех mmIBk* = k
Пусть IB-методом (итерационным алгоритмом Ховарда начатым со второго шага, изложенным в разделе 3). Покажем, что эти же решающие функции могут быть определены IBm-методом, если положить mmIB
Из (19) следует, что при любом m≥ 1 IBm-метод вначале итерации-онного процесса определяет решающую функцию fm) = fS, которые согласно теореме 2 при m→ ∞ стремятся к величинам iSтаким, что wifvifvsfiSsSпред-ставляют собой решение системы уравнений Ховарда (4) для fF. Следующей решающей функцией, определяемая IBm-методом будет fm)F. Из сходимости iSследует сходимость fm) → fm→ ∞. Это значит, что найдется такое конечное число mfmfIBm-методе положить m= mff
Аналогичным образом можно установить существования конечных чисел fkmkfkk= 3, 4, …, kIBm-метод за k* = k
СПИСОК ЛИТЕРАТУРЫ

1. Ховард Р. Динамическое программирование и марковские процессы. М.: Сов. Радио, 1964.

2. Майн Х., Осаки С. Марковские процессы принятия решений. М.: Наука, 1977.

3. Ибрагимов А. А. Об управляемых марковских процессах с поглощением // РАН. Автоматика и телемеханика. 1999. №12. С.80-89.

4. Ибрагимов А. А. О существовании и единственности ситуации равновесия в марковских играх с переоценкой // НАН Украины. Кибернетика и системный анализ. 2000. №6. С. 152-165.

5. Ибрагимов А. А. Существование и нахождение значения и оптимальных стратегий в рекурсивных играх // Известия РАН. Теория и системы управления. 2001. №4. С.102-109.

6. Ибрагимов А. А. Существование и нахождение значения и оптимальных стратегий в регулярных марковских играх // Известия РАН. Теория системы управления. 2002. №3. С. 29-40.

7. Бертсекас Д., Шрив С. Стохастическое оптимальное управление: случай дискретного времени. M.: Наука, 1985.

8. Саримсаков Т. А. Основы теории процессов Маркова. Ташкент: Фан, 1988.

9. Ибрагимов А. А. Об одном свойстве регулярной цепи Маркова // Украинский математический журнал. 2002. Т 54. №4. С. 466-471.

10. Крылов В. И., Бобков В. В., Монастырный П. И. Вычислитель-ные методы. Т. 1. М.: Наука, 1976. 304 с.

8.07.11



перейти в каталог файлов


связь с админом