И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 35
Текст из файла (страница 35)
Положить й = О. 175 П1. Найти множество Х« ~ (х ( шах ф, (х) ( шах ф; (х'), х с 11"). ~е.у 'е.« 1Ч. Вычислить константу Ц, = шах гпах(Чф,(х)(. ««х Жт Ч. Найти множество 1«= (У! (У((сФь УЕЛ"). Ч1. Вычислить константу р«= шах шах1 «Ех«иег«сну 1 где д«В(«+и) ~ д«« ЧП. Если р«О, то вычислить константу а = ппп (а, е!(2р()) и перейти к шагу 1Х; иначе перейти к шагу ЧП1. ЧПЕ Вычислить константу а = ппп а, 2ф„б'+ Р'+ Р" р!ц 1Х. Выбрать произвольное а« ~ (О, а). Ос нов но й ц и к л. Х. Найти множество индексов Ж,(х«) Й (1(шах ф, (х~) — ф, (х")(е, (~У).
~е.т Х1. Используя алгоритм 1', определить, принадлежит ли начало координат многограннику 1,«(х«), который является выпуклой оболочкой, натянутой на множество точек (Чф, (х~), Е Я«(х")). Если начало координат принадлежит 1., (х"), то положить х«= х«и прекратить вычисления; иначе перейти к шагу ХП. ХП. Используя алгоритм 1", найти точку»„которая является ближайшей к началу координат точкой многогранника Е«(хь). ХП1. Вычислить р, = (»,(.
Х1Ч. Вычислить вектор й'( ) = — (1 1» 0 »' ХЧ. Вычислить следующее приближение х"+' = х" + а р„Ь»(е). »76 ХЧ1. Положить й = й + ! и перейти к шагу Х. Теорема 4. Если выполнено предположение 4 и начальное приближение хе тшсово, что множество Хе ограничено, то любая предельная точка бесконечной последовательности (х') ы о, порожденной алгоритмом 4, является е-стационарной точкой функции шах ф, (х). %Я б. третий метод поеледовательпыл приблищевий, иепольвуюпщй !З.щуввпвы Третий метод последовательных приближений, использующий Е!-функцию, весьма зффективный при малых и и небольшом количестве элементов множества И. Алгоритм б Н а ч а л о. 1. Выбрать произвольное начальное приближение хеба 11. Выбрать константу е ~ О. П1. Положить й = О.
Ос нов но й ц и к л. 1Ч. Найти множество индексов Р(е(х')Й(1)шахфк(хе) =ф,(хь), !ЕО). ~ау Ч. Используя алгоритм 1', определить, принадлежит ли начало координат многограннику Ле (х"), который является выпуклой оболочкой, натянутой на множество точек (Чф, (хе), ! Р Же (хе)). Если начало координат принадлежит Ее (хе), то положить хе= хь и прекратить вычисления; иначе перейти к шагу У1. Ч1. Найти множество чисел фр ! Е (О: тЦ, удовлетворяющее условиям: (1) — ()е) р, ) ...
) рей (В) — для каждого (Е о существует индекс ! ~ (О: т) такой, что ф, (х") = ~!, ((и) — для каждого ! Е (О: т) существует по крайней мере один индекс ! С й! такой, что ~! — — ф, (хе). ЧП. Положить в = О, ае = О. Ч111. Положить е = а,. 1Х. Найти множество индексов Хе(хе)(,1 (1(шах ф~ (хе) — ф~(хе) ~!,е, ! ЕО). кеу Х. Используя алгоритм 1', найти точку г, — ближайшую к началу координат точку многогранника Ее (х"), который является выпуклой оболочкой, натянутой на множество точек (Чф, (х'), (й Е Я, (хь)).
Х1. Вычислить вектор й» (е,) — направление е,-наискорейшего спуска функции максимума в точке х" Й (е,) = — (Ц)ге())ге. Х11. Вычислить значение тра (хе) ~ ((ге( 1гт Х1П. Вычислить значение а„1 « — — ' шах «р«(х') — р,+г. «ет Х1Ч. Если а,+«( в, то перейти к шагу ХЧ; иначе перейти к шагу ХЧ1; ХЧ. Если в + [ ( т, то положить в = в + 1 и перейти к шагу ЧП1; иначе перейти к шагт ХЧ1.
.ХЧ1. Положить а,+« —— и. ХЧП.'Найти индекс за ~ [О: в[ такой, что ае„+««[«„(ха) = ш[п (ат«ро, (х"), аа«ра,(Х ), ю а««ра 1(Х ), а«+1«ро (Х ))' ХЧП1. Положить Р (х") а, ~ ««р„, . Х [Х. Положить й' = Ьа (в,„). ХХ. Найти шаговый множйтель ра из условия шах«р,(ха+ раИа) = ппп шах«р,(х'+ р[га). «Я.У пего,«» «Ет ХХ1. Вычислить следующее приближение х"+' = ха + р„й".
ХХП. Положить й = я + 1 и перейти к шагу !Ч. Теорема б. Если выполнены предположения 0 и начальное поиближение х' в алгоритме 5 таково, юпо множество Ха~ (х(шах ф«(х) (гпах ф«(ха), хс В"] «Е.у ' «ку ограничено, то любая предельная точка х* бесконечной последовательности (х")а о, порожденной алгоритмом б, является стационарной таю«ой функции !пах «р, (х), причем Р (х') = О. гея Библиографические укан«ния. Пункты 1, 2 написаны на основании работ [117, 1!8, 127, 128, 254[. Пункты 3, 4 написаны на основании работ [! 17, 118, !27, 128, 86[. Пункт 5 основан на работах [119, 120, 122, !27, 128[. 3.13.
Сеточный метод последовательных приближений решении непрерывных минимаксных задач 3 а д а ч а [. Найти ага ппп шах «р (х, у) для заданной функции «ояо ену «р: В" х В"-ч В' и заданного ограниченного замкнутого множества У с В". Предположение 1. Функция ф (х, у) непрерывна вместе с Ч,ф (х, у) по совокупности переменных в В" 14 У.
178 Алгоритм 1 Н а ч а л о. 1. Выбрать начальное приближение х' ~ В" и сетку Ун, = (У'[У'Е 1', 16 [О: )Чо[) удовлетворяющие условиям теоремы 1. П. Выбрать произвольную константу ао ) О. П1. Положить в = О. Основной цикл. 1Ч. Положить се=а„О=[О:!Ч,). Ч. Определить функции фг: В" -ь В', [Е 71 по следующим правилам гр, (х) ~ <р (х, у'), [Е й. Ч1.
Если з О, то перейти к шагу Ч1П; иначе перейти к шагу ЧП. ЧП. Если выполняется неравенство шах гр; (х") ( шах ~р, (х'), сеу !еу то положить х' = х" и перейти к шагу ЧШ; иначе положить х' = = х' и перейти к шагу ЧП1. ЧП1. Используя алгоритм 12.5 (см. 9 3.12, алгоритм 5) с начальным приближением хо = х', за конечное число итераций вычислить первую точку х", для которой Р-функция удовлетворяет условию — Р(хь) (а. 1Х. Положить У,+~ = 2У„сев~.~ — — а,/2. Х.
Построить сетку Ун,+, (у' [у' Е У, 16 [О: У,.ьз[), удовлетворяющую условиям теоремы 1. Х1. Положить в = в+ 1 и перейти к шагу !Ч. Теорема 1. Пусть выполнено предположение 1 и (1) — множество 'г' ограничено и замкнуто; (Й) — последовательность сеток ()гн ), о всюду плотная на множестве У, причем Ун с: У н, „в = О, 1, ...; (ш) — начальное приближение х' Е В" и сетка Ун, таковы, что множество Хе ~ [х( шах <р, (х) ( так гр (хо, у), х ~ В"), ~яо:на есу ограничено, тогда любая предельная точка последовательности (х'),=о, порожденной алгоритмом 1, является стационарной точкой функции так гр (х, у) на В". ееу Бпблпоерофчяескпе указания.
При написании параграфа использовались работы [!27, 1201. 179 3.14. Методы Эрроу — Гурвица решении непрерывных минимаксных задач 1. детермвввровеввыя метод Эрроу — Гурвиче 3 а да ч а 1. Найти ага ш!п шах ф (х, у) для заданной функции Ея" еи Д х Д Д» Предположения 1. (») — функция ф (х, у) непрерывно дифференцируема по х и у; (и) — функция ф (х, у) выпукла по х при любом у и вогнута по у при любом х. В методе Эрроу — Гурвица на й-й итерации вычисляют (й + 1)-е приближение (»»+', у»+') в направлении антиградиента по х и градиента по у функции ф (х, у), вычисленных в точке (х", у»). Шаговые множители по переменным х и у удовлетворяют классическим условиям и могут быть различными.
Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хл ~ 11", уе ~ 11~. П. Положить я = О. Ос н о в н о й ц и кл. 1П. Вычислить векторы 7»ф (х", у») и 7»ф (х», у») — градиенты функции ф (х, у), соответственно, по переменным х и у, вычисленные в точке (х", у»). 1Ч.
Вычислить шаговые множители р» и р», удовлетворяющие условиям теоремы 1. Ч. Вычислить следующие приближения: + = — р»ч,ф(, у); у + = у'+ р,'Ч„ф ( ", у'). Ч1. Положить й = й + 1 и перейти к шагу П1. Теорема1. Пусть выполняются предположения.1 и пусть (»)— у функции ф (х, у) существует по крайней мере одна седловая точка; (11) — шаговые множители р» и р» алгоритма 1 удовлетворяют условиям р» ) 0 и р' ) 0 при й = О, 1, ..., 1м р» = оо; »=о р'„-~-0, р»/р'-»О и р»» ~1р»-~-1 при й — » оо.
Тогда, если последовательности (х») и о и (у»)»=о, порожденные алгоритмом 1, ограничены, то любая предельн я точка х последовательности (х»)» е является первой компонентой х некоторой седловой точки (х, у) функции ф (х, у). Замечание 1. При сделанных в теореме предположениях относительно последовательности (у')»" е можно утверждать лишь ее 1ВО сходимость к множеству у (у~<р(хе, у)=гпах~р(хе, у), УсВ ), те~ где х' — вектор, пробегающий множество первых компонент седловых точек функции <р (х, у). В некоторых случаях г совпадает с множеством вторых компонент седловых точек функции ~р (х, у), однако в общем случае эти множества различны (примером этого служит функция <р (х, у) = ху). и.
Стоаастачсскиа метод Энрот — Гтраада 3 ада ча 2. Найти агяш(п шах Ео~р(х,у, в) для заданной „ало таам функции ~р: В" Х В х Й -о В'. Предположения 2. (1) — функция 1» (х, у) ~ Е щ (х, у, в) непрерывно дифференцируема по х и у; (В) — функция 1» (х, у) выпукла по х при любом у и вогнута по у при любом х. В стохастическом методе Эрроу — Гурвица на й-й итерации вычисляют (й + 1)-е приближение в направлении статистических оценок антиградиента по х и градиента по у функции ~о (х, у) в точке (х', у»). Шаговые множители по переменным х и у могут быть различны и удовлетворяют классическим условиям.
Алгоритм 2 Н а ч а л о. 1. Выбрать произвольное начальное приближение хоЕВ", уоЕВ П. Положить й = О. Ос н о в ной ци к л. П1. Вычислить шаговые множители р„и р», удовлетворяющие условиям теоремы 2. 1Ч. Вычислить реализации $», Ь» случайных векторов $», удовлетворяющих условиям Е(Р~Ф»)=Ч»1»(х", у') ЕЯ'1Ю»)(а' Е(~»/Ф») = Чо1»(х", у"), Е(Щ'/Ф») (а, где Ԅ— о-алгебра, порождаемая случайными величинами хо, уо, х', у', ..., х», у"; а ( оо. Ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
