Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 58
Текст из файла (страница 58)
КОММЕНТАРИИ И бИБЛИОГРАФИЯ Материал, содержащийся в этой главе, взят из диссертации Масанао Аоки (Маг ли а о А ой й РЛ. 19. Тнеэы 1уерагсаепт о1 БпЕ1пеег1п8, 11л1гегэ1гу о1 СаИогп1а, Еоэ Апйе1еэ, 1960). ГЛАВА Х ЛИНЕЙНЫЕ УРАВНЕНИЯ И КВАДРАТИЧНЫЕ КРИТЕРИИ й ВВЕДЕНИЕ В предшествующих главах внимание было сосредоточено в основном на получении достаточно целенаправленных вычислительных алгоритмов. Нашей целью была выработка методов, которые приводили бы к численным решениям независимо от конкрегных структурных свойств индивидуальных задач. Однако, как постоянно подчеркивалось ранее, в большинстве случаев трудности, связанные с размерностью, ограничивают возможность прямых подходов. Следова гельно, здесь требуется определенная изобретательность.
Для получения подходящего аппарата или более быстрых и более эффективных методов мы должны сочетать специфические аналитические свойства рассматриваемого процесса и подход с помощью функционального уравнения. Как мы видели, во многих случаях, когда описывающие процесс уравнения линейны и критерии квадратичны, можно получить вычислительные процедуры, которые гораздо лучше процедур, даваемых обычными классическими методами.
Это имеет место, несмотря на тот факт, что классические вариационные уравнения линейны, в то время как уравнения, получаемые при использовании метода динамического программирования, нелинейны. Эти результаты, конечно, важны сами по себе. К тому же они служат в качестве важных этапов в цепи последовательных приближений к решению более сложных задач. Наконец, такие же методы применимы к стохастическим и Збб линвйпыг. тилянзния и квлдвлтичпыв кииткпии [гл. я адзптивным процессам управления, где обычные методы оказываются вообще бесполезными.
В основном в этой главе мы будем просто перечислять результаты, отсылая читателя для более подробных сведений к первоисточникам. 2. ЗАДАЧА СГЛАЖИВАНИЯ Для того чтобы проиллюстрировать в элементарных терминах аналитический аппарат, который будет неоднократно испольаоваться в различных контекстах, вернемся к процессу дсглаживания», рассмотренному в главе 1П. Предположим, что мы хотим определить значения хп обрашающне в минимум функцию () (х„х,,....
хл)=а, (х, — г)" +а,(х„— х )я+... ... +ал(хл — хл 1)'+Ь,х1-";Ьяхад — , '... +Ьххл (10,1) 1(ействуя обычным образом, полагаем: уд (с) = ппп [ад(хд — с)'+... + ал (хл — хлг,)д+ + Ьдхд + ° ° .+ Ьлхч] (10.2) для /г=1, 2,, Аг — 1. Тогда, как ранее, (х(г) = ш1п[а,,(х, — с)'+ Ь, хл], (10.3) и для Ь=1, 2, ..., Аг — 1 мы имеем рекуррентное соотношение У'„(с) = ш1п [ад(хд — г)' + Ь хдд -[- У „, (х )]. (10.4) Таким образом, пока мы не добавили ничего нового к нашим предшествуюшим рассуждениям. Используем теперь то важное обстоятельство, что каждая из функций т", (с), г,(г), ..., ул,(с) является квадратичной функцией от с.
Именно Гд(с)=пдс», . Ь=1, 2, ..., Аг, (10.0) где ид не зависит от с. По-видимому, проше всего это показать методом индукции. Результат, очевидно, верен для Ь = Аг, а соотношение (10.4) показывает, что эта структура сохраняется. овстждвнив После того, как установлена формула (10.5), нетрудно получить рекуррентное соотношение, связываюшее иа и лаве Подставляя (10.5) в (10.4), получим уравнение гга с' = ш! и !аа (ха — с)'+ Ьа ха+ сга „г хЦ. (10 6) 'а Легко видеть, что значение х„, доставляюшее минимум, равно пас хь — (и, + Ь„+ и„,) (10.7) при атом ™ а Ь ам+ Ь (10.9) Определив таким образом последовательность 1иа), мы получим из (10.7) миннмизируюшие значения хгс 3.
ОБСУЖДЕНИЕ Обычные методы классического анализа, примененные к задаче минимизации, рассмотренной в предшествующем параграфе, приводят к системе линейных уравнений а, (х, — с) — ая (х, — х,) + Ь, х, = О, ал(ха — х» а) — а,ь, (ха+, — х„)+ Ьаха — О, (10.10) а (х — х,)+Ь х =О. Хотя обычно время, требуемое для решения системы йГ линейных уравнений пропорционально гчя, особый вид матриц, связанных с записанной выше линейной системой, позволяет Подставляя это значение в (!0.6), получим простое рекурренгное соотношение аа+ да+ иь,,, ЗГ!В ЛИНЕЛНЫР УРАВНЕНИЯ И КВЛДРЛТИЧНЫЕ КРИТЕРИИ [ГЛ. Х примени гь спеииальиые методы, солращающие это время. Оно становится пропорииональным АГ.
В этом случае, если требуется только найти численное решение, использование метода фуикииональных уравнений не дает никаких особых преииуществ. 4. БОЛЕЕ СЛОЖНАЯ ЗАДАЧА СГЛАЖИВАНИЯ Предположим, ч!о мы хотим миииииэировать фуикиию (с(хг„х„..., х )=а,(х, — с,)' — , 'а,(х„— 2х, +с„)'=,' +аа(ха — 2ха+х,)'+ ... [-Ьгх',-,'- — ',— Ья х", + ... + Ь, хм . (10.1 1) Вводя последовательность фуикиий г"„(с„ся) = шш [аа (ха — с,)'+ да э, (х„„, — 2ха -1- с!)' + ... ...-"[-Ь„;.+Ь„„;„-[- ... Ь„~- [, (10.Г2) мы получии рекуррентное соотношение [а(с,, сэ) =пил [аа(ха — с,)Я+ Ь„х-"„+ к +Уач! (2ха — с„х„)[, (10.13) Ь= 1, 2, ..., Аг — 2, причем ,(с,, ся)= пии [а ., (х,, — с!)'-[- лЮ вЂ” !' "Л' + а (х — 2х .
+ ст)Я+ Ь,, х)г !+ Ь хт]. (10.14) Теперь методом индукиии легко покззать, что !а (с„ся) = ггь с", + 2оа с, ся+ ш„с'„ Ь = 1, 2, ..., Аг — 1. (10.1б) После получения этого результата нетрудно вывести, как и выше, рекуррентное соотношение, связывающее тройку [ „, „, иг„[ с [,+„с„+и +,[. СЛЛЗО СВЯЗЛННЫЕ СИСТЕМЫ б, СЛАБО СВЯЗАННЫЕ СИСТЕМЫ Рассмотрим теперь обобщение линейной систем ац х, + а,г х, + а,з х, = с„ ам х! + а„г х, — 1- ага хз = сг, ам х, + а „х, + азз ха + Ь, хт = с„ Ь,х,+а,зхз+амхз — , 'а!Зхз=сг, ам хз+ а„х„+ а,з хз = с„ а„! х! + ааз х, + аз, х, + Ьг х! = с,„ ы (10.10) (10.16) Ь, х +а,, х л -! зм — з+ зм-г, зл-2 зл — 2+ ЗМ -2, ЗМ вЂ” ! ЗМ вЂ” ! + ЭЛ' — 2, ЗМ ЗМ Згг — 2 322 — 1, ЗХ вЂ” 2 ЗМ-2 ' ЗЛ'- 1, ЗЛ' — 1, ЗМ вЂ” ! + + ЗМ-1. ЗУ ЗМ ЗЛГ - 1, зл', зл' — 2 зм — 2 азл', зм — ! хзл'— з,ч, зл зл зл, ! Сис!емы этого типа возникают при рассмотрении экономических и механических систем, в которых имеется лишь небольшое число связей между различными подсистемами.
Используем теперь кое-что из теории магриц — по сушес!ву только обозначения. Введем мзтрипы А„=(а;ьгз-з. 2.22-2) ! /=-1 2 3, (10.17) и векторы х'= х,„, хаз УСЗЗ 22, с =1сгл 2~ . (10.18) сза Предположим, чго матрипа линейной системы (10.16) положительно определенна. Тогда решение линейной системы сводится к решению задачи определения минимума неоднородной квздратичной формы (х', А, х') + (х', Аг х') + ... + (хлг, А хл)— — 2 (с', х') — 2 (с', хг) — ...
— 2 (с м, хл) + +2Ь,х,х,+ 2Ь,хзх,+ .. + 2ЬЛ-! хзл-зхзл! — г' (10.10) ЗТО линвйныв гвлвнвния и квядвлтичныв квитввии 1гл. х Введем последовательность функций (С,(г)), — оо( (г(оо, АС=1, 2, ..., определяемых соотношением А, ') — 2 ~(,', '] м-с ч. 2 т. Ь *, .и *м ч- 1, „ ~ с=с (10.20) Тогда мы получим рессуррентссое соотношение ~м (г) = ш 1п ((ж, А их ) + 2гха т — '2 (с~, х") + лл +Х~, (Ссч,х . )], (10,21) где Я вЂ” трехмерная область — со (х „хам,, х, ( о;, Легко ус~ввозить индукцией, что каждая функция тт( ) является квадратичной функцией от г; У (г)= +' а+ш, '. 6, ХАРАКТЕРИСТИЧЕСНИЕ ЧИСЛА Задачу нахождения нетривиальных решений уравнения и" +1~(С)п=О, и(0)= — и(1)=О, (1023) можно рассматривать, при разумных предположениях относительно в(С), как задачу определения опюсительных лсиссиясумов функционала с ! (сс) = ) сс' ~й (1О.Ы) при ограничениях с ~ а(С) иМ=1, и (0] = и (1) = О.
(а) (Ь) (10.26) Используя (10.21), нетрудно вывести рекурренсные соотношения для пы о„и шы аналогичные полученным выше. Использование этого метода при рассмотрении обшего случая, когда матрицы А; имеют различные разиеры, не вызывает затруднениИ 37! ххРАктеРистичвскив числя Рассмотрим только задачу определения абсолютного минимума, наименьшего характеристического числа упомянутоИ выше задачи Штурма — Лиувилля. Дискретным аналогом поставленной выше вариационноИ задачи является задача минимизации квадратичной формы О(хи хя, ..., хх)=(хг — с)2+ (ха — х)2+ ... + +(х, — х,)2+х)г (10.26) при ограничении ~~7; х'2=1, (1 0.27) где ха подчинены условию М ~ чьх„=1.
2=2 (10. 29) Легко видеть, что У,, (с) = пип 1(хл,, — с)'+х ), (10. 30) где 2 2 рА,, хА,, +~Р х =1, (10.31) и ! уа(с)=пил (ха — с)2+(1 — о,ха)2 )( кь ХЛ22 2 2, (10.32) где йах„(1. Значение Л(0) есть приближение к наименьшему характеристическому числу уравнения Штурма — Лиувилля. Предположим, что 0 ( а — у; ~ Ь ( со при всех О и введем последовательность функций (га(с)), л=1, 2,..., м — 1, определяемых соотношением 7а (с) = ш 1п ((ха — с)'+ (ха, — ха)2 +... ...
+ (х — х,,)2+ хх), (1О. 28) 372 линвйныв гглвнвния и квлдглтичныв кгитиеии [гл. х 7. СТОХАСТИЧЕСНОЕ СГЛАЖИВАНИЕ Рассмотрим теперь вкратце стохастическим варизнт задачи сглаживания, о которой речь шла в 9 2. Предположим, что мы хотим минимизировать математическое ожидание функции д (х у) — '~~ (а у»+ Ь»х»), (1о.зз) »=1 где х!,=»1»х;+у»+гп !=О, 1, 2,...,М вЂ” 1,(10.34) Здесь г! — независимые случайные величины с заданными распределениями. Положив для А = 1, 2, ..., Аà — 1 г»(с) = ш1п Е ~~~ (а;у»»+ Ь»х";)~ (10Лб) !=й где х„, = с, имеем; г а (с) = ш 1п [ а»уа»+ Ь„с'+ х» + )У»~ (г(»с+У + га) ЫО„(г~)~ (10.36) для Ь=1,2,...,А! — 1 и г,(с)=Ь с'.
(10.37) Легко показа~ь с помо!цью индукции, что каждая функция у»(с) — квадратичная функция от с, 7»(с) = и»+ 2'в„с+ таас», (1о.зз) 8. ЛИНЕЙНЫЕ ПРОЦЕССЫ УПРАВЛЕНИЯ С НВАДРАТИЧНЫМИ НРИТЕРИЯМИ— ДЕТЕРМИНИРОВАННЫЙ СЛУЧАЙ Рассмотрим задачу определения вектора управлении в(1), минимизиру!ошего квздратичный функционал т ! (о) =) 'те»»11+ и (Т)», а (10.39) а затем получить рекуррентные соотношения, аналогичные полученным в $ 2.
373 стохагтичвскиЙ случАЙ где и и э связаны соотношением аи — = а и+ о, и (О) = с. (10.40) Рассллотрим дискретныи случай. Мы хотим минимизировать квадратичную форму и — ! 1,1 (п)=и)о+Л уЧ',о1 (10.41) л=о по всем о», когда и„н о» связаны соотношением и»„,=аи»Ч и», 7г=0,1,..., А! — 1, и„=с. (1042) Полагая ум ( ) = пц я„(о), (10.43) имеем ~! (с) = ш!и !(ас+ и,)'+ Л и,'), (10.44) и для Аг=2,3, ... Угг (с) = пцп (Л э,'+Уч ! (ас+ по)] (! 0.45) ъ» 9. СТОХАСТИЧЕСКИЙ СЛУЧАЙ Аналогично для величин и», о„, связанных соотношением и»ы —— аи„+ и»+ г», и»= с, (10.46) где (г ) — последовательность случайных величин с заданными распределениями, рассмотрим задачу минимизации математического ожидания квадратичной формы Л вЂ” ! Ял(о) = и»и+Л ~Ч~~'о~. (10:47) г=о Обозначив ум(с) =шшЕйл(п)1, (10.48) Используя тот факт, что каждая функция в последовательности (7» (с)) является квадратичнои функцией от с,г» (с) = =и»+2э»с+те»са, можно быстро получить рекуррентные соотношения для и„, о» и ти».
ЗТ4 линвйныв тяавпвния и квадялтичныг. квятвяии [гл. х где минимизация производится по всем политикам управления с обратной связью, получим, как и выше, Уч(с) = ш!и ~Ло,'-)- $уч ! (ос+ по+ го) ИО(го)~, (1049) где 0(г) — функция распределения для г,. Нетрудно убедиться, используя метод индукции, что каждый элемент последовательности )Та(с)) является квадратичной функцией от с, Тр,(с) = и„-1- 2о с+ твоея, и снова получить рекуррентные соотношения для коэффициентов. Аналогичные результаты можно получить для адаптивного случая. Ссылки помещены в конце главы. !О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
