Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 69
Текст из файла (страница 69)
К. Дж. Эрроу, Л. Гурвиц, УС Улзава, Исследования по линейному и нелинейному программированию, ИЛ, !962. Линейные неравенства н смежные вопросы, М» ИЛ, 1959. йж. Л с и и и с, Математическое программирование и элентрические цепи, М., ИЛ, 1960. 1!оскольку разложения для У и о имеют впд у (Ь+аА"')=.Г(Ь) 1-а ~~ дЬ агт+ г= — ! »» л« + 2" ~,,~ дь,дд„аыаау+.", (44) !=!а=! ,(а+ ~),(ха) ! от ! ! «дз ( (45) дх ' 2" дх-а ПРИЛОЖЕНИЕ И! ВЫЧИСЛИТЕЛЬНЫЙ МЕТОД, ОСНОВАННЫЙ НА ПОСЛЕДОВАТЕЛЬНЫХ ПРИБЛИЖЕНИЯХ В ПРОСТРАНСТВЕ ПОЛИТИК С.
Драйфус Е ВВЕДЕНИЕ В настоящем приложении мы хогим дать элементы теории численного решения задач оптимизации, весьма перспективнон в огношении преодоления трудностей, снязанных с размерностью. Этот метод, по существу, яиляется градиентным мегодом, в котором приближение к оптимальной политике осуществляегся последовательными шагами.
При построении метода мы пользуемся известными понятиями и аппаратом динамического программирования. Эти результаты были также получены Брайсоном и Келли ~1~, (2] более сложным путем. Брансон получил этим методом численные решения вариацнонных задач, содержащих до восьми параметров состояния; представляется, что общность метода практически ничем не ограничена. Недостатки этого метода уничтожения оков размерности двояки.
Во-первых, процесс приближений может сходиться к экстремали, которая не дает абсолюпшго минимума или максимума. А потому для задач с небольшой размерностью большое преимуптество на стороне обычного метода, изложенного на предшествующих страницах этой книги. Однако в случае задач с высокой размерностью простота и [п. ш 446 вычислитвльный мвтод практичность метода компенсируют опасность локальноя сптимальпости. Во-вторых, ограничения в виде неравенств на параметры состояния и решения порождают серьезные трудности.
указанные недостатки можно до некоторой степени принять во внимание при последовательных приближениях, но этого нельзя сделагь каким-либо из известных способов. Напомним, что в обычных алгоритмах динамического программирования ограничения просто выделяют некоторую область в пространстве решений, в которой должно быгь найдено решение, и потому они скорее желзтельны, чем неудобны.
2, ЗАДАЧА В настоящем приложении иы ограничимся днскретныч аналогом вариационной задачи, известной под названием «задачи Мадера» (см. 2 22 главы г). Это не умаляег общности, так как, во-первых, любая вариационная задача можег быть сведена к задаче Майера и, во-вторых, для численного решения на счетной машине непрерывной вариационной задачи необходима дискретизация. Кроме того, читатель, вероятно, представляет себе теперь, чз о почти все задачи динамического программирования можно рассматривать как вариационные задачи и наоборот. Нашу задачу можно постави~ь следующим образом. Мы хотим минимизировать функцию р от параметров состояния у,, у„и времени ( в некоторый неопределенный момент Т в будущем, где Т вЂ” первый момент, когда выполняется некоторое «правило остановки» ф(уь, у„, 1)=О, (1) Величины 22 определяются своими начальными значениями -у'о'' '' ' у"о (2) и разностными уравнениями у,(г+цг)=у,(~)+д,(у,((),, у„(г), «(г), г)цг, (3) где «(() — решение, которое должно быть выбрано оптимальным образом.
Иначе говоря, мы хотим выбрать такую последовательность чисел («ь), где «ь — — «(Ацг), что, когда параметры состояния у; меняются во времени, условие остановки )=0 выполняется при минимальном у. 447 Рш<уРРеитныт уРАВнения Задачи на нахождение минимального времени можно рассматривать как частные случаи этой общей задачи, когда !рь Е Обратно, если требуется, чтобы конечным моментом был в точности момент 7'„, то условием остановки будет (4) Чтобы избежать рассмотрения ! как особой переменной, положим уп„,=! и ощ! =1. 3. РЕКУРРЕНТНЫЕ УРАВНЕНИЯ Начнем с выбора наугзд заведомо неоптимальной последовательности Решений (г„, го.,., «ю,), где г„=а(7тб!), и рассчитаем криву!о, порожденную этими решеииямн вместе с уравнениями (3) п условиями (2). Определим неоптимальную функцию дохода как функцию у(уп..., у„,,), равную значению т при условии остановки ф=б, при начальноч состоянии, харак!еризтющемся ун.,., (5) У„ы и использовании 1таданной политики (г„).
Очевидно, что функция 7 удовлетворяет рекуррентному соот- ношению 7 !.у! ° Ую.!) =7,(У!, йд! °, У„ы — ! — Ачтд!), (6) а+1 дг~! 1г~.. 1ду! т+а() т,дг Д (7) Как видно, чтобы вычислить это выражение, нужно знать — Рекуррентное соотношение для этой величины ду дУ! т-1-щ' где д! вычислены с помощью угзданных (га) и соответствующей им трзектории. Для того чтобы рассчитать эффект первого порядка от изменения в решении в момен~ Е мы пытаемся найти ду дг т' т. е. вычислить производную дт 'дг как функцию параметров состояния и решений в момент Е Взяв частную производную от (6) по г, получим: 448 [п. щ вычнслитяльныИ мгтод получается взятием частной производной от (6) по уг (8) Уравнения (7) и (8) имею~ очевидное словесное толкование.
Уравнение (7) выражает тот факт, что скорость изменения функции ? ом<осительно г в момент 1 равна произведению скоростеИ изменения в момент с+ цг' состояния системы, вызванного изменением т, и изменения функции ?, обусловленного изменением сосзояния системы в момент 1+ Ы. Уравнение (8) гласит, что полное изменение функции ? есть сумма двух слагаемых, которые выражают соответственно изменение г, обУсловленное изменением Ул входащих в 8п и изменение ?, вызванное прю!ым изменением ут(?) относительно у?(! + Ы). Как видно, уравнение (8) является дискретным аналогом правила множителеИ *) а-!-! ~,у,у+ '?' ут к! = О, (9) г=! полученного в 9 22 главы У (уравнение (8.97)). Если — = — О, дт" дг то никакого улучшения быль не может и имеющаяся кривая является оптимальной.
Это замечание приводит к уравнению (5.93) 9 22 главы Н. Теперь мы имеем два обычных рекуррентных соотношения (7) и (8), которые дают возможность в любой момент оценить эффект от изменения з в конечной целевоИ функции у. Граничные условия для рекуррентных соотношений мы определяем из того обстоятельства, что изменение в параметре состояния в конечный момент ?'вызывает два эффекта: непосредственное изменение !у и изменение э, обусловленное изменением в конечном моменте, определяемом уравнением ф = О. Учитывая это, имеем: *! Но терминологии Л. С.
Понтрягина эти уравнения являются дискретным аналогом уравнений дая импульсов. (Прая. ред) 41 спосовы ултчшвния Ф. СПОСОБЫ УЛУЧШЕНИЯ , Постулируем для корректировки г правило г„„„(1)=злы „(г)+6г(1) (11) и будем искать выражение для йг. Начинаем с принятия рааучной политики, заключающейся в изменении г в каждый момент г пропорционально величине вычисляемой для момен~а б Это означает, что там, где потенциальный уровень дохода дг7дг больше, мы действуем более решительно. Обознзчив л+! ~и ду! дг ' ! ! (! 2) мы заключаем из (7), что т Т п+! Ьр=~ ~~йг=й'~ (~~~ УФ)'М, (13) О помощью двух элемегыарных оперзций взятия производной мы получили выражения для вычисления в любой люмент эффекта первого порядка в конечном значении функции 4!, вызванного изменением в решении. Эти результаты можно осмысливать как «функции влияния» или сопряжен.ные урзвнения, которые обычно получзются из теорем о предсгзвлении решениИ линейных дифференцизльных урзвнений.
Выбор метода, с помощью которого их можно использовать наиболее эффективным образом для последовательного улучшения неоптимального решения, является в значительной мере вопросом эксперимента в области численного анализа. В следующем параграфе будет дан один, по-видимому, весьма эффектизныИ способ использования этих результатов, принадлежащий Брайсону. 450 1п. ьп вычислитвльпый мигов (1 4) я+! ~(2.д дг)" г=о г-! и используем при следуюцгей итерации новую функцию решения, задаваемую формулой ~~ дУд,1,— г=\ змовое (1) аггавое ( ) + г и+! г=а г=! (15) Разумно при каждой последовательной итерации искзть лишь небольшие улучшения Ьр, поскольку нами проводится знализ эффекта первого порядка, а он точен только для малых изменений. Прежде чем приступи~ь к изложению аппарата последовательного улучшения лля более сложных задач, введем некоторые обозначения и перечислим основные результааы.
Вместо ду,'ду! будем писагь Лу (ср), помня, что Л, (и) можно интерпретировать как влияние изменения в у; на значение р ь+! ъ! дУ дд! в конечный момент, Сумму гг — — ' будем обознзчзгь Л,(а). ,7 ду! дг г=! В этих обозначениях метод последовательного улучшения состоит в следующем: (1) Угадывается «(1). (2) Интегрируются уравнения движения (3). (3) Вычисляются Л (га) в конечный люмент Т по формуле (10). где !Лр есть изменение в конечном значении а, обусловленное изменениями з(1) через да(т) во все моменты О ~1=.: 7'. Слагаемые в выражении для Ьр легко вычисляются вдоль заданной траектории с помощью рекурренгных соо!ношений (7) и (8).
Если мы хотим внести поправку Ьр в значение р, то мы выбираем 45! 41 СПОСОВЫ УЛУЧШЕНИЯ (4) Определяются Л,,(з) вдоль исходной траектории посредством (8), и одновременно вычисляются Л,(са) и г ~Х ', (Л, (ср))а сЛС ПО фариуЛЕ (7). (о) По формуле (15) определяется аа„аа для фиксированного сЛе. (6) Возвращаются к шагу (2). Предположим теперь, что в молсенг остановки должно выполняться дополнительное сооююшение О(ун ..., у„, 1)=0. Такие же рассуждения, как в предыдущих параграфах, дают возможность рассчитать влияние изменения в а на конечное знзченне О с помощью формул а+! ЛУ,(О) =7 С (Л! (О)! ('~'~~) бс-с-Лс, (О)(,, (17) с=! а+! Л, (О) / =,~ (Лу (О) 1с ! дс) ~ Ог!с) ' с ! (19) Пусть теперь Ог имеет вид Ог = 7ссЛ, (са) + 7ссЛ, (О), тогда (20) Ьса= ~ ! Л,(О) Ьсйа, с-а г ОО = ~ Л, (О) Дг О . (21) (22) Если исходная траектория из-за ошибок округления, нелинейности или же трудностей нахождения начальной допустимой траектории не удовлетворяет вспомогательному условию (16), то мы выбираем сЛО как взятое со знаком минус отклонение от желаемого условия на конце.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
