И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 36
Текст из файла (страница 36)
Вычислить следующие приближения' х»+' = х» — рД»1 у»+1 у»+ и ~» Ч1. Положить й = й + 1 и перейти к шагу П1. 1а1 Теорема 2. Пусть выполняются предположения 2 и пусть шаго вые множители р» и р'„удовлетворяют условиям р») О, р„') О при й = О, 1, ...; «„(р») ~со, р»/р'-~-О при й-~со ~ р = со. »=о »=о Тогда, если последовательности [х»)»~ и [у»]» е, порождаемые алгоритмом 2, ограничены почти наверное, то любая предельная точка последовательносгии [х»[»=е минимизирует Функ[!ию [пах [го (х, у), т. е. является решением задачи 2. усял3 Библиографические укаюниа. Параграф написан на основаннн работ [272, 3141.
3.15. Методы анстремального базиса для решения непрерывных минимаксиых задач ' 3 ад а ч а О. Найти агд ппп шах ф (х, у) для заданной функции ляял еяу ф: В" х В'" -г- В' и заданного компактного множества У в В". Предположения О. (») — функция ф (х, у) непрерывна по х и у на В" х у'; (И) — функция ф (х, у) выпукла по х в В" при любом у б у; (Вг) — функция ф (х, у) дважды непрерывно дифференцируема по х на В" х г; ()п) — г' — компактное множество. В методах экстремального базиса на й-й итерации вычисляют следующее (й+ 1)-е приближение х"+' как решение (точное или приближенное) некоторой вспомогательной задачи безусловной минимизации.
Для этого на каждой итерации строят базис из и + 2 точек, принадлежащих множеству г", в котором при переходе от одной итерации к другой меняется лишь одна точка. Вводимую в базис новую точку находят как решение (точное или приближенное) некоторой вспомогательной задачи условной максимизации. Для отыс-. кания выводимой из базиса «лишней» точки в общем случае требу-. ется иметь процедуру проверки на принадлежность этой точки к выпуклой оболочке заданных п + 1 точек. 1. Првнцнпаальвый алгорнтм Алгоритм 1 Н а ч а л о, 1. Выбрать произвольную точку ха ~ В" и произвольный набор (базис) Оо, состоящий из п + 2 точек множества )' 6а [уел уол уо, +а) угле У 17'1~[1.и [ 2) 11.
Положить й = О. Основной ци кл. П1. Определить функцию ф»(х) = шах ф(х, у»'). (3.13) ге[не+«1 182 (Злв) ~вз 1Ч. Найти точку х»ч-', удовлетворяющую условию ф»(х»+') = ппп ф»(х). „енп Ч. Найти точку у»Е У, удовлетворяющую условию Ч(х»+', у') = шах ф(х»+', у). »ву Ч[. Если выполняется равенство Ч( "+', у ) = Ф,(х"+') <зла) то прекратить вычисления (в этом случае х»+' является решением задачи 0); иначе (если <р (х"+', у') ) ф» (х»+')) перейти к шагу ЧП. ЧП.
Вычислить множество индексов /» = [1[~р(х»+', у»') = ф»(х»+'), 1Е[1: п+ 2Ц. Если множество 1» содержит все элементы множества [1: п -[- 2), то перейти к шагу ЧП1; иначе обозначить через 1» любой индекс из множества [1 п+ 21, которого нет в множестве 1», и перейти к шагу 1Х. ЧП1. Найти индекс 1» ~ [1: п + 2[ такой, что 0 С Е», где множество Е, является выпуклой оболочкой множества Й» Е~ [Ч,~р(х'+', у") [1Е(l»~;[1»[)). (Отметим, что по необходимому условию минимума функции ф» (х) точка х"+' удовлетворяет условию 0 ~ Ею где множество Е» является выпуклой оболочкой множества Н» Ь [Ч„~р(х»+', у»л)[1Е1»).
Поэтому начало координат (точку 0) можно представить в виде выпуклой комбинации не более чем и + 1 векторов Ч„Ч(х»+', у"'), 16(1»~,[1»))). 1Х. Построить новый базис б»+~ = (у»+", ..., у»+~ +») по правилу »+ы у"', если 1~1»; (з. 1т) у', если 1=1„1=1, ..., п-[-2. Х. Положить й = й + 1 и перейти к шагу П1. Теорема 1. Пусть выполняются предположения 0 и пусть суп(ествуют числа и, ) 0 и а»( оь такие, что (Ч„',р(х, у) ° г, г)~а,[[г[», УхЕН", уЕУ, гЕВ"; [[Ч„Ч(х, у) [( а», Ч хЕ Н", у Е У. Тогда бесконечная последовательность (х»[» ь, порожденная алго.ритмом 1, сходится к точке минимума функции шах Ч (х, у).
чт й. е-метод В общем случае е-метод практически не реализуем из-за бесконечности процедуры безусловной минимизации. Алгоришм 2 Н а ч а л о. 1, П (шаги 1 и П такие, как в алгоритме 1). Ш. Выбрать последовательность (е,]»" т, удовлетворяющую условиям е»->-+0 при й-~оо, 2, е»(оо. О.снов ной ци кл. 1Ч. Определить функцию ф» (х) по (3.13). Ч. Вычислить точку х'+' такую, что ОЕ 1.».»> где 1-»,т» яв. ляется выпуклой оболочкой множества точек Оде 1!» (Чтф (х + > у ' )! ! Е У»,е»]> здесь .г»т = (! ] >р(х»+!> у»!) ~Р ф»(х»+!) — е», »~ (1! л + 2]]. Ч1. Вычислить точку у' Е 1' по (3.15). Ч11. Если выполняется равенство (3,16), то прекратить вычисления (в этом случае х»+' является решением задачи 0); иначе перейти к шагу ЧШ.
ЧП1. Если множество 1»,», содержит все элементы множества И: л + 2], то перейти к шагу 1Х; иначе обозначить через !» любой индекс множества 11 ! и + 2], которого нет в множестве (», и перейти к шагу Х. 1Х. Найти индекс 1,Е П ! л+ 2] такой, что ОЕ Ь»д»> где множество Е»дд является выпуклой оболочкой множества Н»,т 1.> (Чтя>(х +, у ' )] ! Е Ц»,е ~~ (1»))) ° Х.
Построить новый базис 0».!.! — — (у»+'', ..., У»+'"+'] по (3.17). Х1. Положить й = й+ 1 и перейти к шагу 1Ч. Для алгоритма 2 имеет место теорема, аналогичная теореме 1. Замечание 2. На шаге Ч1 алгоритма 2 точку у» б 1' можно вычислять по правилу шах ч>(х»+!, У) — ч!(х»+!, у") ~ р»~-!, <зла) иег где р»т! -+ + 0 при й -+ оо, что требует приближенного решения задачи максимизации по у ~ у функции !р (х»+', у). 184 3. р.метод Приводимый р-метод реально осуществимый, так как требует лишь приближенного решения промежуточных задач оптимизации. Алгории»м 3 Н а ч а л о. 1, П (шагн 1 и П такие, как в алгоритме 1). И1.
Выбр Вть последовательность (р,)» о, удовлетворяющую условию р»-о+0 при й — » со, ~, "р»(оо. »=е Основной ц и кл. 1Ч. Определить функцию ф» (х) по (3. 13). Ч. Вычислить точку х'+' такую, что ш!п[~ г [~ р», »8»» где Ь» является выпуклой оболочкой множества Н»й (Ч,~р(х»+', у"'), !Е,!»); здесь ,!» = (! [ р(х»+', у» ') = »р» (х»+'), ! Е [1: и + 2[).
(Для вычисления х»+' требуется решать приближенно задачу минимизации функции ф, (х) в »г'). Ч1. Вычислить точку у' Е 'г' по формуле (3.15) (как н в замечанин 2 точку у» можно также вычислять в соответствии с неравенством (3.18), т.
е. для отыскания у» достаточно решать приближенно задачу максимизации по у Е 'г' функции ~р (х»+', у)). ЧП. Если /» = [1 ~ а + 2!, то перейти к шагу ЧП1; иначе в качестве 1, выбрать любой индекс из множества [1 ~ и + 2! '«,,!» и перейти к шагу 1Х. Ч1П. Найти индекс !» Е [1 ~ л + 2[ такой, что множества Ц н !.„совпадают, где С» определяется на шаге Ч, а 1,» является выпуклой оболочкой множества Й» ~ [7,(р (х»+', у»л) [ ! Е (у»~(!»))). !Х. Построить новый базна б»+, (у»+' ', ..., у»+'"+') по формуле (3.
!7). Х. Положить й = й + 1 н перейти к шагу !Ч. Для алгоритма 3 имеет место теорема, аналогичная теореме 1. 4. Комбвввровеввмй е,р-метод Приводимый здесь алгоритм является комбинацией методов, приведенных в пунктах 2, 3, н является практически реализуемым Алгория»л» 4 Н а ч а л о. 1, П (шаги 1 и П такие, как в алгоритме 1). 185 П1. Выбрать последовательности (е,)»".=о, (р»)Г е, удовлетворяющие условиям е»-'+О, р~-ь+ О прн [е-» ею; ха е»<оо, 2„р <оо, »=е «-е Основной ци кл. 1Ч. Определить функцию тр» (х) по формуле (3. 13).
Ч. Вычислить точку х»+' такую, что т! п [г[< р», »еь»,а где й»л определяется, как на шаге Ч алгоритма 2. Для вычисления х»+' необходимо решить приближенно задачу минимизации функции ф» (х) в В". Ч1. Вычислить точку у» по (3.15). По аналогии с замечанием 2 для отыскания у» достаточно решить приближенно задачу максимизации по у Е 1' функции р (х"+', у) ЧП. Если [»л, — — [1: л+ 2), то перейти к шагу ЧП1; иначе в качестве !» выбрать любой индекс из множества П: л + 2)~,.[»,е и перейти к шагу 1Х.
ЧП1. Найти индекс 1,~ [11п+ 2! такой, что множества 1,»л» и (.»л, совпадают, где Ь»л» определяется, как иа шаге Ч алгоритма 2, а 7.»,е» вЂ” как на шаге 1Х алгоритма 2. !Х. Построить новый базис 6»+1 = (у»+' ', ..., у»+ь"+э) по (3.17). Х. Положить й = й + 1 и перейти к шагу 1Ч. Для алгоритма 4 имеет место теорема, аналогичная теореме 1. Замечание 4. Если'в алгоритмах пунктов 2, 3, 4 точку у» вычислять в соответствии с неравенством (3.18), где р» = р ) О, то последовательности точек (х»)» о, порождаемые этими алгоритмами, будут сходиться к [»-стационарной точке функции »пах»р (х, у) »ау (определение р-стационарной точки приведено в 5 3.12).
Библиографические указании. При написании параграфа была использована ратота [!251. дополнительную информацию о методах экстремального базиса можно найти в работах [124, 12б[. 3.16. Обобщенный градиентный метод отыскания седяовык точек 3 а д а ч а 1. Найти седловую точку (х*, уа), удовлетворяющую соотношениям «р(х~, у ) = ш«п шах «р(х, у) = «пах ш(п «р(х, у), я я ч г е и ~ г я и ~ ~ е к и где «р .* В" Х В"-«- В' — заданная функция. Предположения !. (1) — для каждого фиксированного вектора у Е В" функция «р (х, у) выпукла и непрерывно дифференцируема по х; (В) — для каждого фиксированного вектора х ~ В" функция «р (х, у) вогнута по у; ((и) — множество седловых точек Х'«х У'" задачи 1 непусто.
Приводимый ниже метод является вариантом метода Эрроу— Гурвица. На й-й итерации алгоритма движение к следующему при- ближению (хь+«, у~+«) по переменной х осуществляется в на- правлении антиградиента по х функции «р (х, у'), а по переменной у — в направлении обобщенного градиента по у функции «р (х««, у). Шаговые множители удовлетворяют классическим условиям. При определенных условиях алгоритм сходится к неустойчивому по Гольштейну 182) множеству седловых точек функции «р (х, у) (определение устойчивости множества седловых точек функции «р (х, у) приведено в $ 6.9). Алгоритм 1 Н а ч а л о.
1. Выбрать произвольное начальное приближение (х~, у')~В" х В. П: Положить й = О. 1П. Выбрать константу а ( оо, удовлетворяющую условиям теоремы 1. 0 с н о в н о й ц и к л. 1Ч. Вычислить п-мерный вектор Ч„«р (х", у') — градиент функции «р (х, у) по х в точке (х", у'). Ч. Вычислить т-мерный вектор Чг«р (х", уг) — обобщенный градиент функции «р (х, у) по у в точке (х", у'), Ч1.
Вычислить шаговые множители р„и рм удовлетворяющие условиям теоремы 1. ЧП. Вычислить следующие приближения: хь«« = х" — р,Ч «р(ха, у'), если (х", у') Е5„х 5„, ха, если (х', у') Я 5, х 5„; у'+ р,'Чгф (ха, у'), если (х", у") б 5, х 5„, уг, если (хг, уг) Ы 5, х 5„, где 5„«л(х$~х~(а, хЕВ"), 5г«'«(у~)у$(а, убей ). ЧП1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
