Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 20
Текст из файла (страница 20)
Чтобы получить лучшее приближение, определяем и, = д, (Р) как функцию, максимизируюшую выражение А'(Р ц) + 7ь(7 (Р 7)) (2. ! 28) а затем определяем 7,(Р) с помощью соотношения 1~(Р)=й(Р, 7~)+7~(7(Р, ~У~)). (2.129) Продолжая таким обрззом, получим две последовательности: !'7л(Р)! " (7л(Р)). Во многих случаях легко доказазь монотонную сходимость Л ( ) ==А (Р) -" В общем, приближение в пространстве политик тем или иныч способом будет монотонным приближением.
Интересным в этом понятии приближения является то, что оно может быть применено ко многим уравнениям, совсем не связанным с процессами решения. В таком виде он составляет основу метода, называемого квазплпнеарпзацней. 45] послвдовлтвлы!Ыв пгислижвния — и 1!Я Иа следу!ощих страницзх мы рассмотрим некоторые примеры приближенна в пространстве политик и приведем численные результаты. 4б, ПООЛЕДОВАТЕЛЬНЫЕ ПРИБЛИЖЕНИЯ вЂ” П Вернемся к процессу распределения, описанному в 2 2. Мы хотим максимизирова!ь функцию л ул(х, у)= ~ ег(хь у;) (2.131) при условиях (2.132) (2.133) Этот процесс дает для каждого значения у множество значений Уи У" = 1У!).
ИспользУЯ эти значениЯ Уе котоРые мы называем уг, рассматриваем задачу максимизации функции л! ~ д,(х„у!) г= — ! по всем значениям хь удовлетворяющим условию (2.132, а). Эта задача решается с помощью рекуррентного сооююшения, аналогичного (2.! 34). (а) х! = х, х! ) О, г=.
! (Ь) '5; у,=у, у, О. г=- ! Пусгь ха=(хЦ вЂ” начальное приближение для множества значений хе Это есгь приближение в «пространстве политик». Эзтем определяем мзксимум функции и йл (х, у) = д', д! (хг, у;) (2.! ЗЗ) !.=! по всем уг, удовлетворяю!цим услови!о (2.132,Ь), используя обьг!ное одномерное рекуррептное соотношение гл (у) = п!ах (ггл (хл, ул) -',-да — ! (у — ул)! (2 134) в х,у у где А!=2, 3, ...
и 120 многоияяныв пяоцвссы Рлспявдвлвння [гл. и Таким ну~ем мы получаем иножество значений хь х' = [х[[. Повторяя теперь этот процесс, получим пару последовательностей [х"[, [у"[, п = 1, 2, , Ясно, что последовательное!ь значений [гтх(х", у")[ — монотонно возрастаю!цая. Однако эта последовательность вовсе не обязана сходиться к абсолютному максимуму.
Чтобы убедиться в этом, рассмотрим, например, функпию двух переменных е = д(х, у). изображаемую поверхностью вида, показанного на рис. 28. Рис. 28. Хотя абсолютный максимум находится в точке (х„, у,), если мы примем зз начальное приближение х=О, то в описанном выше процессе максимизации сначала по х, затем по у, затем снова по х и т.
д, мы застрянем в точке (О, О)— точке оп!осителшюго максимума (си. й 5!). С лругой стороны, если начальное приближение взято достаточно близким к точке (х,, у„), то приведенный выше метод будет сходиться к требуемой точке (хм у,). В любом случае этот метод может быль использован для проверки того, дает ли конкретный выбор значений х; и у,. относительный максимум, и если нет, то имев~ ли место сходимость к ближайшему относительному максимуму. Если исходить из начальных векторов [х', у'[, достаточно удаленных друг от друга, то мы можем ожидать, что таким путем определится целый ряд относительных максимумов и, как можно нздеяться, среди них абсолютный максимум. Задача выделения абсолюпюго максимума из относительных максимумов является бичом в области оптимизации.
Нельзя ожидать, что она будет когда-либо разрешена одним ударом, Можно надеяться лишь присоединять класс задач за классом к нашей коллекции «укрощенных зверей». 121 послвдовлтвльныв пгивлижвния — ш 46. ПОСЛЕДОВАТЕЛЬНЫЕ ПРИБЛИ1ИЕНИЯ вЂ” Ей Рассмотрим теперь дру~ое применение последовательных приближений, при котором мы используем непрерывность изменения значения, доставляюшего максимум. Рассмотрим задачу, описанную в 9 2, и отмегим зависимость положения максимизирующей точки от х и у. Как можно показать на простом примере, эта зависимость не обязана быть равномерно непрерывной. Чтобы проиллюстрировать это, рассмотрим одномерный случай.
Предположим, что мы имеем ~т Ум функцию д(хь х,) от х, и хм максимум которой мы Рис. 29. хотим найти в области х,--', +х,=х, хь хя)0. Обозначим ((х,) =д(хь х — х,) и рассмотрим график этой функции (рис. 29) при 0 =х,(х. В этой области функция имеет два относительных максимума, один из когорых является абсолютным максимумом. Если и ((х-у=((у, ) Жи ум х Рис. 30. непрерывна по х, и х,, то при изменении х положение точки х, доставляю~цен абсолютный мзксимум, будет изменяться вместе с х непрерывным образом до тех пор, пока мы не достигнем значения х, при котором грзфик имеет вид, изображенный на рис. 30. Для этого значения х относительные максимумы равны. Предположим теперь, что для близко~о значения х значение ((у ) больше, чем ((х„).
В резульгате положение 122 многсмггпыз пвщшссы и. гпгвдзлвння !гл. и абсолютного максимума резко перемещается из окрестносги хы в окрестность у . Следовааельно, х„, рассматриваемая как функция от х, может иметь точки разрыва. Интересный пример такого рода появляегся в связи с уравнением г (х) = щах (д(у) + !г (х — у) — ') (ау —,'- ь (х — у))1. (2.137) Если р'(у) — е- !ог (2.138) !! (у) = е — !ас', то функция л (х) является гладкоп (рис. 31), в то время как функция политики у(х) имеет вид, изображенный на рис.
32, Гд Ы .ггт ад Рис. 31. При некоторых значениях х пропсходгп резкое изменение в хзрщстере огпимальной политики. Мы копались в этих деталях для того, чтобы должным образом подготовить читателя к трудностям, содержзщимся в методе, который буде~ тепер» излагаться. Наша цель сочетать описанный выше метод последова!ельпык приближений с лсетодом неггрерыанослгп, еще одним осногнпям инструментом аналитика. Лля х=О единс~вег!ным возможпыи выбором знзченин х! является х; = О, ! = 1, 2, , )т'*).
Следовательно, зздача максимизации по у; есть задача определения максимума функции л' П, (О, у) = ~ д,. (О, у,), !:-1 ') Лвгор зоззращастск к рассчогрешпо задачи (2.13)), (2.132). (Пряли ред.) 123 послгдоялтельпыя пРиближения — !и задача, которук! мы решаем с помощью последовзтельностеп функпии от одноИ переменноИ. Предположим на минуту, что ср Рис.
32. онз имеет единственное решение у'= 1у!). Для того чтобы решить вадачу с ограничениями вида М х!=Ь, (=! л Х У;=У хгтв О, 12.140) ! =! х;=21, ! =-! х ! У'=У (2.141) != ! где в качестве нзчального приближения по у берется тг решение задачи 12.140). где Ь вЂ” «малое», мы исходим из начального приближения уч = !!у!) и приступаем к максимизации по хл как описано в предшествуюших параграфах. Получив таким путем решение, мы повторяем рассуждения для задачи с ограничениями 124 и~Огомвгныв пгоцвссь! Рлспгвдвления 1гл. и Если мы чувствуем, что этот метод может потребовать слишком много времени, то мы можем использовзть прямой метод для решения задачи (ч х»=хо (=! 12.142) Х у(=у для некоторого большего значения х, и области значений у, 0 -у ч-у», и начать процесс от этой точки.
47. НОЭФФИЦИЕНТЫ СВЯЗИ Иногдз можно применять метод последовательных приближений другим способом. (1опустим, что мы хотим максимизировать функцию вида (ч л (ч ~ д(х()+ ~, 6((х()+1 5; А((х(, у() (2.143) (=- ! при ограничениях ~ х;=х, ~ у( — — у, хв у()0. (2.144) != ! (= ! Здесь 1 — параметр, который предполагается принимаюшим все неотрицательные значения. Если 1=0, задача легко решается на языке двух последовательностей функций от одной переменной. Поэтому, чтобы решить задачу для малого 1, скажем 1= Ь, мы используем в качестяе начального приближения решение 1х»о уД, полученное при 1=0.
Приняв х»=1х(1, мы можем упростить задачу поиска, ограничив свое внимание окрестностью точки у = 1у!). Получив решение, соответствующее (=Ь, мы используем его в качестве начального приближения для случая (=21, и т. д. Эту идею »развязывания» посредством подходяшего приближения можно использовать многими способами; она предоставляет массу возможностей для изобретательности и применения специальных методов. 125 48] ГРУБАЯ СЕТКА 48.
ГРУБАЯ СЕТКА другой путь приближения к решению задачи максимизации состоит в первоначальном использовании грубой сетки. Допустим, что мы хотим максимизировать функцию д, (х,) + 1~я (х,) +... + Дм(хл) (2.145) при ограничении х,+х,+...+х, =х. (2.146) Пусть для начала х принимает только значения О, 3, 2Ь, где 3 велико по сравнению с нашим обычным ша~ом сетки. Аналогично, переменным х; мы позволяем принимать то же множество значений, котя можно было бы считать х; при- надлежащими также некоторому другому множеству. В результате нахождение решения ускоряется ч в двух направлениях. Здесь подлежит табулированию меньше значений ум(х), и процесс поиска ст д ьз максимнзирующего хм Рис.
ЗЗ. на каждом шаге короче. Таким образом, мы получаем множество максимизирующик значений ]х;(х)), !=1, 2, ..., Аг, затабулированпых в точках х=О, 3, 28, Риск при использовании грубой сетки состоит в том, что можно пропустить очень острый абсолютный максимум и принять за него плоский относительный максимум. Рассмотрим, например, функцию, изображенную на рис. ЗЗ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
