Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 59
Текст из файла (страница 59)
ПОНИЖЕНИЕ РАЗМЕРНОСТИ можно рассматривать в терминах функций от !т переменных, независимо от размерности х. Покажем теперь, что задача существенно упрощается, если а — квадратичная функция своих аргументов. Решение уравнения (10.51) имеет вид х=е"'с-)- $е ""-'! у(а) ~. о (10.52) Следовательно, задача сводится к минимизации Е(с,+) [Хр«(а)у«(а)1 з,.", с„+ о '«-! г + (7Д,ро«(а) у«(а)1 с(а), о «=! где постоянные с) и функции р;«(а) известны. (10,53) В предыдущей главе мы указывали, что задачу минимизации функции 5(х!(Т), хо(Т), ..., х„(Т)) по всем функциям у(«), удовлетворяющим уравнению — = Ах +у, х (О) = с, 375 линвйн»я твовия пявдсклзхния Введя новые функции Т(сг, са, ..., с», Т)=пипа, 1г> (10.54) легко увидеть, что 1' — квадратичная функция от с,'.
Если допустить, что Т непрерывно, то функциональное уравнение (8,54) приводит к сисгеме дифференциальных уравнений для коэффициенгов хчг (Т) в выражении а; . ( Т) сг с,. с/=! 11, ЛИНЕЙНАЯ ТЕОРИЯ ПРЕДСНАЗАНИЯ Линейная теория предсказания Колмогорова и Винера приводит к задзче минимизации квадратичной формы »). м = Х (܄— Х гб ໠— г)г (10.56) »=о г=о по всем вещественным значениям п», где а» и Ь» — заданные вещественные числа. Предположим, что а,=О, г) 1 и что АГ) М. Поскольку прямой подход приводнг к решению системы линейных уравнений, мы хосни предложить метод, основанный на аппарате функциональных уравнений, позволяющий обойтись без это~о.
Итак, рассмотрим задачу минимизации квадратичной формы и Е ф (Ь»+ г„— ~ и,а»,) ~, »=о г=о (10.57) где 㻠— сначала независимые случайные величины, потом коррелированные случайные величины такие, что распределение г» зависит только от г„ „ а затем случайные величины с неизвестными распределениями, подлежащими определению из наблюденин. В случае дискрегного Т получится система нелинейных рекуррентных соотношения, 876 линейные гилвнвния и квлдвлтичныв квитввии (гл. х 12, ДЕТЕРМИНИРОВАННЫЙ СЛУЧАЙ Минимум величины О м по всем и есть квадратичная форма относительно Ь„, ш!и В =(Ь, Я Ь), и (10.58) где с,см „ — симметричная неотрицательно определенная матрица порядка (Ас + 1) )С (АС + 1), заданная для Ас) М ) О, а Ь вЂ” (Ас+ 1)-мерный вектор-столбец с компонентами Ь,,Ь„..., Ь . Запишем (10.58) в виде пнп0,и — — шсп ((Ьо иоао) +(Ьс — иоа,— и,а„) + и ' !ио.
ис., ил1 +...+(Ь вЂ” и,а — и, ал., †...— имая)о]. (10.69) Следовательно, в терминах функции, определяемой равенством (10.68), имеем: (Ь ЪмЬ)= = сп1п 1(Ьо — ссоао) + (Ь' — и,а', Яи с „, (Ь' — ссоа'))) (10.61) ио где Ь' и а' — теперь Ас-мерные векторы с компонентами соответственно ан а,, ..., а, и Ь,, Ьо, ..., Ьм. Положим Р,м 0 (1062) сил — с, м — с Тогда (10.61) принимает вид (Ь ссл, мЬ)= ш1п(Ь вЂ” и,а, Ри „(Ь вЂ” и,а)), (10,63) ио и легко видеть, что (Ь,!Сл мЬ) — ' ' ' (10.64) (Ь, ! л' м") (и ! л, м ') — (и У и мЬ) Если и, выбрано, мы видим, что получается аналогичная задача определения сс„ио,...,и, где (а) Ь; заменено на Ь; — сс,аи с=1,2,..., Ас, (Ь) М заменено на М вЂ” 1, (10.60) (с) АС+1 заменено на АС. 377 коггяляция при минимизирующем выборе им задаваемом равенством ( ° Рл,мЬ) с'о=( Р (10.65) сома Таким образом, мы получаем рекуррентное соотношение, связывающее сс' и с 1„сч с м и Итерируя это соотношение сИ рзз, приходим к задаче минимизации формы со м ;~; (Ь,-ссоа,)о о-о по и,, имеюсцей весьма простое решение.
Исходя из этого решения, с помощью рекурренгного соотношения (10.63) получаем решение исходной задачи. 13. СТОХАСТИЧЕСНИЙ СЛУЧАЙ Рассмотрим теперь задачу определения минимума (10.57), когда го — независимые случайные величины с одинаковой функциеи распределения 0(г). Тогда, обозначив (Ь ЯлмЬ)+2(Ь с) м)+р м=ш1пЕ(...), (10.67) и г мы получим рекуррентное соотношение (»()л лсЬ)+2(Ь с)л м)+Ртом = = пс 1п $ $ ((Ьо — поа„+ г )' асО (г ) + (Ь вЂ” сс а, 1;С~,, Х оо )((Ь вЂ” ссоа))+2(Ь вЂ” ссоа,а, с м с)+рл.— м )/. (10.68) Из этого соотношения можно легко получить рекурресыные соотношения, как это сделано выше.
И. НОРРЕЛЯЦИЯ Положим теперь г, = а и запишем: (Ь, (), (г)Ь)=ппп[Е~~(Ьо+го — ~сосал с)оЦ. (10.69) и Г с с;с 878 линвйныв твлвнвния и квлдвлтичныв квитввии !гл. г( Тогда аналогом (10.68) будет: (Ь, ьу (а) Ь) + 2 (Ь, гуж (а))+ р (а) = =шгп ( ~ ((Ьо — и,а„+ г,)'+ ио +(Ь вЂ” п„а, О~ г аг г (г,)(Ь вЂ”,а)) +2(Ь вЂ” н„а, у,, м,(г,)) — 'р,, „, (гоЦ гУСг(го,д)(, (!070) откуда снова можно получить рекуррентные соотношения. гб. ТЕОРИЯ ПРЕДСКАЗАНИЯ С АДАПТАЦИЕЙ Рассмотрим теперь случай, когда пронесс протекает следующим образом. Сначала выбирается и,, затем наблюдается Ь,+г,. Далее выбирается и, и наблгодается Ь,+г, и т.
д. Предположим, что последовательности (а„) и (Ьа) известны. На основе нзблюдений над г,,ги ... мы выводим распределение гы Это есть адаптивнйй пропесс, описзнный в ф 29 главы Н1!!. Чтобы проиллюстрировать аппарат, которым мы будем пользоваться при решении задач такого рода, рассмотрим простой слу ый, ко~да предполагаегся, что каждое га принимает ~олька значения г- 1 соответственно с вероятностями р и (1 — р), причем р неизвестно. Пусть О (р) — заданное априорное распределение р. Предполагаем, что после наблюдения лг значений + 1 и и значений — 1 мы принимаем в качестве нового априорного распределения р" 1! — р) . а (р) ггсу „=, р" (! — р) ло(р) (10.71) Обозначим у (Аг, гИ; т, и; Ь) = (Ь, гч' ч м (гл, и') Ь) + 2 (Ь, гул „(лг, и)) + + Рл, (т, и) = ш!п [Е ( ~ [Ьа — ', га — ~~ ', ггга„г) й ( ! 0 72) а-о' г-о !51 КОММВНТАРИИ И БИБЛИОГРАФИЯ ~(Аг, М; и, л; Ь) = = пни (р„,л У(Аг — 1,М вЂ” 1; гп+1,п; Ь вЂ” па а)+ ла +(1 — р „)У(Аà — 1,М вЂ” 1; т,п+ 1; Ь вЂ” пааИ (10.73) позволяет нам получить рекуррентные соогношения, как и выше, для матриц (С, „, векторов !у,, и скаляров р ки Вероятность р „вычисляегся по формуле ! р „=) рат'.0 „.
о (10.74) КОММЕНТАРИИ И БИБЛИОГРАФИЯ 4 1. Ряд результатов этой главы вместе с другими резулыатами аналогичного характера и дополнительными ссылками можно найти в книге: К. В е ! ! ш а п, !п!гобосцоп то Ма!Пх Апа1ча!»3 аттсбга«ч-Н!1! Воо1« Со., 1пс., Ые«л Уог1«, 1960, Свар!ег 9. Кроме того, они включены в упражнения книги «Динамическое программирование». 9 5. Аналогичный аппарат можно применять нри изученнв задач линейного програламирования, в которых матрица коэффициентов имеет почти блочно-диагональную форму.
См. статью: К. В с!!ш а и, Оп где сошрн!а!!опа! зо1нпоп о1 Впеаг рго8гашш1п8 ргоЫеша !пчо!ч1п8 а1шоэ! Ыосй Шадопа! шаг!!сев, Мапа8ешепт Вс!енсе, чо!. 3, 1957, рр. 403 — 406. 4 9. Подробное рассмотрение задач такого рода можно найти в книге: К. Вес й «и ! ! Ь, Апа1у1!с апд Сошрн!а1!опаВ Аареста о1 Пупашш Рго8гашш!п8 Ргосехаеа о! Н!ЕЬ 1т!Ф4!Ьз1оп, Зе! Ргорн1аюп 1.аЬогагогч, 1959. 4 1О. Дальнейшие результаты имеются в статье: К. В е11ш а и апй К, К а1аЬ а, Кейнс!!оп о! Шгпепяопа1!ту, бупашк ргойгашш!п8 апб соп!го1 ргосезаеа, Л Ваяс.
Еп8г., чоЬ 83, 1961, рр. 82 — 84. нредполэгзя, что мы уже наблюдали т рзз + 1 и л раз — 1. Тогда рекуррентное соотношение 389 линвйныя тианийния И КВАЛРатиЧНЫИ Кинтвнин !ГЛ. Х 9 11. Вопросы обоснования задачи н подхода к ней яр!гиле лгетодами освещены в работе: Х. 1.ечгпзоп, Аррепгйх !о Х. Туг епег, Ехтгаро!а!!оп, !п!егро!а1!оп апй Вшоогй!пд о! Бта!!опагу Типе Вег!еэ, ТесЬпо1очу Ргезз апй лойп 1ч!1еу апй Вопя, Ыетч Уогй, 1949. Описанный здесь аппарат заимствован из статей: К. В е11шап, Туупаш!с Ргойгашш!пй апй Меап Впцаге Ттеч!а!!оп, ТЬе КАЫ17 Согрогабоп, Рарег Р-1147, Вер!ешЬег !3, 1957. К.
В е1!ш а п, 17упаш!с Ргойгашт!ггй апй Ь!пеаг Ргесйс!гоп ТЬеогу, Тйе КАЫТт Согрогаг!оп, Рарег Р-2308, Мау 16, 1961. Систематическое развитие этих идей и дальнейшие результаты даны в работе: К. Е. Ка1шап, Хетт Ме!Ьойз апй Кези1ы !п 1.!пеаг Ргей!с!!оп апй Ррнеппй Тйеогу, К1АБ, Тесйпгса1 Керог! 61-1, 1960. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА А. А. Ф е л ь д б а у м, О синтезе оптимальных систем с помощью фазового пространства, Автоматика и телемеханнка, т. 16, № 2,1955. Р.
В. Га ми реп идзе, Теория оптимальных по быстродействию процессов в линейных системах, Изв. АН СССР, серия матем., 22, № 4, 1958. ГЛАВА Х! МАРКОВСКИЕ ПРОЦЕССЫ РЕШЕНИЯ 1. ВВЕДЕНИЕ Как показано на предыдущих страницах, процессы динамического программирования могут принимать различные формы. йгы изучали процессы, в которых переменные, описывающие политику, могут принимать дискретное множество значений, и процессы, где они могут принимать континуум значений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
