И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 83
Текст из файла (страница 83)
ЧШ. Вычислить значение шагового множителя р„, удовлетворяющее условиям теоремы 1. 1Х. Вычислить приращение Л» козффициента штрафа, удовлетворяющее условиям теоремы 1. Х. Положить а,= а» ~ + Л». Х1. Вычислить стохастический градиент (Р, т!") функции д„гь (х, и, а,) в точке (х", и») $» = а»т»)ппп (О, ~р(х», у») — и») )" ~ Ч,~р(х», у»)+ + а„т,) ш!п (О, 1»,(х»)) )' 7„7»,(х»); т!» = 1 — а»т» ) ш(п (О, »р (х», у») — и») )" (6Л) Х11. Вычислить следующее приближение (х»+', и»+') по формулам х»+» = х» + р ~» и»+' = и» + р»т!».
ХШ. Положить я = й+ 1 и перейти к шагу Ч1. Теорема 1. Пусть выполняются предположения О и (111)— Ч» р (х, у) ограничен на Л" »с У' и удовлетворяет условию Липшица по х на 1»" равномерно относшпельно у ~ 'г'; (1о) — Ч»1, (х), ! = = 1, ..., т, ограничены и удовлетворяют условию Липшица на 11"; (о) — числовые последовательности (р»)» ь (Л»)» ~ в алгоритме 1 такие, что р )О, ~ р,= оо, 1ппа„= оо, !ппб»=О, Л»)О; »-1 »-~.. »-н» !1»п(Ь»1р») = О, !!ш(р»а»») = О (р, й ', Л» = и '). » ГО »М 1.
Тогда для аобого начального приближения (х', и') последовательность ((х", и"))»"=ь порождаемая алгоритмом 1, содержит подпоследовотельность такую, что все ее конечные предельные точки (х', и') с вероятностью 1 удовлетворяют следующим условиям: существуют числа з=1, ..., и+1, Ц~О, 1=1, ..., т, и точки у„з = 1, ..., ~ + 1, у, Е (ага ш)п <р (х', у)), »ЕУ для которых справедливы соотношения и' = ппп ~р (х', и); »И и+! и Х К+,Е),)0; и+! м ~, '(),Ч,!р (х', у,) + 1,')чЧ,'1! (х') = О.
2. Если, кроме того, со(Ч„1!(х), !ЕИ (х)) Я О, (в.в) (6.7) где И ( ) = (1)7~(~)~(0, (Ео), и+! то х' р Х, ~ р, ) 0 и справедливы условия дополняюи(ей нежести=! кости ХД (х') = О, ! = 1, ..., т, т. е. точка х' являеп!ся стационарной в задаче О. Замечание 1. Условие (6.7) выполнено для х р Н", если векторы Ч„1! (х), 1Р 'в! (х), линейно-независимы для любых х таких, что И (х) ~ Я. Данное условие выполняется также в том случае, когда функции 1! (х) вогнуты и удовлетворяют условию Слейтера на пространстве 1!1" 2. Слелли!ий алгоритм и перейти к шагу 1Х, если )) о" ( ~ е, то перейти к шагу 1Х. 1Х.
Найти независимую реализацию у' случайной величины у, распределенной на компакте Г в соответствии с мерой р. Х. Найти независимую реализацию !е случайной величины 1, которая принимает значения из множества о! = (1, ..., т) с вероятностями р„рт, ..., р„, соответственно. 455 Для практического нахождения стационарных точек в задаче 0 с помощью алгоритма 1 необходимо выделять специальную последовательность, все предельные точки которой являются стационарными. В приводимом ниже алгоритме нужная подпоследовательность выделяется при реализации итерационного процесса.
Алгоритм 2 Н а ч а л о. 1 — 1Н. Шаги 1 — 1Н такие, как и в алгоритме 1. Н. Выбрать произвольное значение е ) О. Н1. Выбрать произвольный вектор ото й +' (обычно в качестве о' выбирают приближенное значение градиента функции у..,.,(х, и, а1) по (х, и) в точке (х', и')). НП. Положить й = 1, 1 = 1. Основной ци кл.
Н1П. Если ))оа))(е, то положить й! — — й, е=е12, 1 1+1 Х1. Вычислить значения щаговых множителей р», р» и значение козффицнента штрафа а», удовлетворяющее условиям теоремы 2. Х11. Вычислить стохастический градиент 4„» = (Ч», Ч') функции д,,,п (х, и, а») в точке (х", и») по (6.4), (6,5). Х1П. Вычислить следующее приближение х"+' = х'+ рД', и»4-! = и'+ р»п». Х1Ч. Вычислить вектор о»+! о» 1 р (~» о») ХНт Положить я = й + 1 и перейти к шагу НН!. Теорема 2.
Пусть выполняются предположения О, условия (1(!), (1о) теоремы 1 и числовые последовательности ' (р»)»=» (р»)»» (й»)»=! такие, чпю Р» ) О, 1!ш р = О, Ьо оо »=! "' = ~' "»+! = с»» + б»' й» ) О, 1ип б» = О, ч„, (б„)» ~ Ьо оо » » ! о Вп4АРч =О, 11шр,'=О, ~', р о 11шй/р О, »+~ » » оо о 1(шр»(!х»)» = О, ~ (, )», » оо »=! оо / » оо /» 1» ло (р»я /р )( со, р»и4/р' ) »=1 Тогда для любых векторов (х», и'), о'! 1) последовательность ((х», и») )» 4, порождаемая алгорит- мом 2, содержит такую падпоследовательность ((х'ц и"))! „что почти наверное 1ип 74„,„!диан(х*4, и'4, и,,) = О. ! оо Любая предельная точка (х', и') втой подпаследовательности удовлетворяет условиям 1'б.б) и является стационарной в заааче О, если О Я со(7,/4(х'), Ебв' (х')(; 2) 1ип((о» вЂ” 74,44д,,кч(х», и», а»)((= О п.
н; Ьо 3) предельная точка (х, и) последовательности ((х» и !))! !, порожденной алгоритмом 2, является стационарной точкой в задаче О. Приведенные выше условия будут выполняться, если, например, положить р»=1/й; р»=й '*'*' й»=(й]пйГ илн / — чие. р» )п. 7))» — ) 6 3. Выпуклый случай 3 ада ч а 3. Найти агдшах ппп )р(х, у) для заданной функ«ах «ну ции <р: В" Х В"-~В', компактного множества Ус=.В" и множества Хс) (х]7,(х) «О, ) = 1, ..., т; х~Я], где 2 — выпуклый компакт в В"; 7,: В"-~- В', 1 = 1, ..., т — во- гнутые функции на Е. Алгоритм Я Н а ч а л о.
1 — Ч. Шаги 1 — Ч такие, как в алгоритме 1. Ос н о в н о й ци к л. Ч1. Найти независимую реализацию у» случайной величины у, распределенной на компакте У в соответ- ствии с мерой р,. ЧП. Найти независимую реализацию 1» случайной величины 1, которая принимает значения из множества У (1, ..., т) с вероят- ностями р„ р„ ..., р , соответственно. ЧП1. Найти значения шагового множителя р» и коэффициента штрафа а», удовлетворяющие условиям теоремы 3. 1Х. Вычислить стохастическнй градиент ($», ))») функции у«„«, (х, и, а») в точке (х», и») по формулам (6А), (6.5).
Х. Вычислить следующее приближение (х»+', и"+') х»+' = пх(х" ]- р»Я; и»+' по(и" + р»т)»), где по — оператор проектирования на Я; У вЂ” достаточно большой отрезок, содержащий (ппп )ь(х, у), шах ~р(х, у)]. («.»)егху («,е)яяху Х1. Положить й й+ 1 и перейти к шагу Н1. Теорема Ю. Пусть выполняются условия: (1) — Š— выпуклый компакт, У вЂ” компакт; (И) — функции )ь (х, у), Ч„р (х, у) непрерывны на Е х У; (]и) — ц) (х, у) вогнута по х на Х для любого у ~ У'; (1о) — функции 7) (х), 1 1, ..., т, имеют непрерывные частные производные и вогнуты на Е; (о) — числовые последователь- 457 ности (р»)Г и (а»!Г ! такие, что р»>0, Ишр„=О, р»+с(р», ~ р„оо; » » ! а» > О, 1[го ໠—— оо, а».с! ~ сс„, ~„'(р»а»)а ( сю »-> « » ! (условия (о) будут выполняться, если положить р„=[с !', сс,=я'н, й=-1, 2, ...).
тогда для любого начального приближения (х', и') последовательность ((х", и»)')»=с, порожденная алгоритмом 3, с вероятностью! сходится к множеству ба решений задачи 3: 6»йз(агдшахш[пср(х, у)) х (и'). «ех дет Замечание 3. Если в максиминной задаче 3 Л вЂ” В" и функции ср (х, у), !! (х), с = 1, ..., т, удовлетворяют условиям теоремы 1, то на шаге Х алгоритма 3 точку (х»+', и»+') можно вычислять по формулам х"+' = х" + рД»; и»+' = и»+ р»т[», где р», а„вычисляют в соответствии с требованиями теоремы 3. Замечание 3'.
Алгоритмы, приведенные в данном параграфе, сравнительно просты для реализации, устойчивы относительно ошибок вычислений; их эффективность по сравнению с другими методами решения задачи 0 увеличивается с ростом размерностей переменных х и у. Решение тестовых задач на ЭВМ свидетельствует о более быстрой сходимости алгоритмов по переменной х, чем по переменной и, поэтому в [372) рекомендуется один шаг по переменной х чередовать с несколькими шагами по переменной и. Библиографические укаванил. Пункт ! написан иа основании работ [372, !651, пункт 2 — на основании работ [372, !641. При написании пункта 3 использовались работы [372, !65, 2661.
6.7. Метод певнаак в задаче поиска макскмина 3 а да ч а 1. Найти х' ага шах ш[п ср (х, у) для заданной «ех еет функции ср: В" !с В -ь Вс, заданного параллелепипеда У с.-. В и множества Хсз(х(1,(х)~0, фс(х) О, с 1, ..., 1,, 1 1, ..., 1„хй(!), где Я вЂ” заданный компакт. Предположения 1. Функции !! (х), 1 = 1, ..., 1„»Р! (х), 1 = 1, ... ..„1, — непрерывны по х; ср (х, у) — непрерывна по (х, у).
В методе «невязок» вводится функция д(х, и) = ) [пип(0, ср(х, у) — и))»«[у+ У с, с, + ~, [Зс(«рс (х))'+ с~~ а, [сп|п [О, сс (х)Ц», где рс ) О, ас ) 0 — произвольные константы. Значение макснмина и'Ьшахш!пчс(х, у) «ЯХ «ЯУ вычисляется как максимальное и, для которого ш!пд(х, и) = О, .ее при этом х = агя пппб (х, и*) является решением задачи 1.
На ««е каждой итерации алгоритма требуется решать задачу минимиза- ции по хЕ Я функции д(х, и»), где (и»)Г=« сходится к и*, что представляет собой сложную задачу из-за трудностей, связанных с вычислением многомерных интегралов. В работе [721 для вычисления многомерных интегралов исполь- зован один из вариантов метода Монте-Карло. Метод «невязок» для решения максиминных задач следует использовать, когда х и у имеют небольшую размерность, нлн когда )к состоит нз конеч- ного числа точек (тогда вычисление интеграла заменяется вычисле- нием суммы).
Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное значение и«Р х!с (обыч- но и' выбирают из отрезка [пип ср (х, у), шах ср (х, у))) и произвольСк,юаЕССУ ' С '.МЕЕХУ ное начальное приближение х» Е Я. 11. Выбрать приращение с«) О. П1. Выбрать произвольные константы а, ) О, с' = 1, Рс)0, 1=!, ..., 1,. 1Ч. Определить функцию д(х, и) = ~ [ппп [О, ср(х, у) — и))»с[у+ с, + ~ рс (фс (х))» + ~; а, [сп|п (О, !с (х)))«.
(а з) с=с с Ч. Положить й = О. Ч1. Вычислить о» ш|пу(х, и') ае н вектор хо=агяш!пд(х, и'), (х«ЕЯ). «бе Если о,= О, то перейти к шагу ЧП, если о« ) О, то — к шагу х|. 459 Основной цикл. ЧП. Положить т=!. ЧП1. Вычислить и"+' = и»+ тЛ. 1Х. Вычислить а»+~ = ппп а (х, и"+') нв и вектор х»+' р Я х»+' = агит1пд(х, и"+'). «ео Х. Если о»+1 — — О, то положить й = й + 1, т = т рейти к шагу Ч1П; иначе (если о»+1) 0) положить В»+~ —— и+', й = й + 1 и перейти к шагу ХЧ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
