И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 20
Текст из файла (страница 20)
Если ! ( и — 2, то положить ! = 1+ 1 и перейти к шагу ХП; иначе перейти к шагу Х1Ч. Х1Ч. Если й ( и — 1, то положить а = а, и перейти к шагу -ХЧ; если й = и, то положить а = )» и перейти к шагу ХХ1; иначе перейти к шагу Х1Х. ХЧ. Вычислить вектор я», 1-я компонента которого а»!=Уо(х" +аег) — ~о(х»))~а ! =1. ХЧ1. Если го (х" — д») ( (о (х»), то положить х»-»! = х» — д» и перейти к шагу ХЧП1; иначе перейти к шагу ХЧП. ХЧП.
Если ~о(х»+д») ()о(х'), то положить х»»! = х" + + я» и перейти к шагу ХНП1; иначе положить а = а/2 и перейти к шагу ХЧ. ХЧП1. Положить й = й + 1 и перейти к шагу 1П. Х1Х. Вычислить ) 6" "' »о. ХХ. Если 1Ь" ' '1»( )», то положить а =1!»~'1» и перейти к шагу ХХ1; иначе положить а = р и перейти к шагу ХХ1. ХХ1. Вычислить вектор д», )ся компонента которого а! =((о(х»+ е') — )о(х»)Уа, /=1, ..., и. ХХ!1.
Положить д» = д". ХХП1. Вычислить вектор Ь» ~ (оа.» — г йа) 㻠— г ХХ1Ч. Если сс( $»!Ь'~!, то перейти к шагу ХХЧ; иначе положить а = а/2 йперейти к шагу ХХ1. ХХЧ. Если выполняется неравенство /а (х» — у»Ь») (/а (х»), то положить Ь"= — Ь' и перейти к шагу ХХЧП1; иначе перейти к шагу ХХЧ1. ХХЧ1. Если выполняется неравенство /а (х'+ у»Ь») (/а (х') то положить Ь' Ь" и перейти к шагу ХХЧП1: иначе перейти к шагу ХХЧ11. ХХЧ11. Положить у, = у,/2 и перейти к шагу ХХЧ.
(Если (Ч/а (х'), Ь») = О (такой случай возможен лишь на начальной стадии процесса), то следует поменять вектор й», изменив число р. Иначе на шагах ХХЧ вЂ” ХХЧП будет зацикливание). ХХЧП1. Вычислить число р, = ш!п/1, 6!(а ' !»»!г ХХ1Х. Положить р = р». ХХХ. Вычислить (3» = з!ип (Ь', я»). ХХХ1. Вычислить Ь =* (/а (х»+ рЬ') — /а (х»))/ра. ХХХ11. Если 6 ( ер» (Ь", д»), то положить р, = р и перейти к шагу ХХХП1; иначе положить р = р/2 и перейтй к шагу ХХХ1. ХХХП1. Вычислить следующее приближение х"+' = х' + р»Ь', ХХХ1Ч. Положить Ь = Ь + ! и перейти к шагу П1.
Алгорин»яа 2А (алгоритм вычисления вектора г» для алгоритма 2) 1. Выбрать произвольную последовательность (Х,);=и сходящуюся к нулю (рекомендуется выбрать Х,= (!/!)", т! Е (О, 2)). 11. Положить е = О. П1. Положить з = 1. 1Ч. Вычислить индекс Ь = тп + з. Ч. Вычислить вектор г' = Ь»е', где е' — з-й орт. Ч1. Если з ( и, то положить з = з + ! и перейти к шагу 1Ч; иначе положить т = т + 1 и перейти к шагу 1П.
Для алгоритма 2 справедлива теорема, аналогичная теореме !. Бибеиографиаеасие указания. Параграф написан на основаннн работ [320, 111, 1!2!. 91 2.4. Методы еонряиенньгх градиентов 3 а д а ч а 1. Найти агй ппп 1о (х) для заданной чепрерывно гсял дифференцируемой функции Де ~ В" -е В'. 1. Обмов евеме евгорвтмоо ооврвжеввмв греввевтов Алгоритм 1 Н а ч а л о. 1. Выбрать начальное приближение хо Р В", удовлетворяющее уаловиям теоремы 1; положить й = О. О он о в но й ц и к л.
11. Вычислить Ч)о(х'). 1П. Если Чге (х') = О, то положить х' = х' и прекратить вычисления; иначе перейти к шагу 1Ч. 1Ч. Вычислить вектор движения й" Е Я(х"), где множество Я (х) задается формулой Я(х)= (й((ЧРо(х), й)(О, йЕВ!. Ч. Вычислить шаговый множитель р„, удовлетворяющий условию 1е(х" + рейг) = пппГо(х" + рйь). рва Ч1. Вычислить следующее приближение х"+' = х' + р,й".
Ч11. Положить й = й + 1 и перейти к шагу П. Теорема 1. Пусть ге — строговыпукла и дважды непрерывно дифференцируема функция, причем для всех х ~ Хо, Хей (х! 1о(х) <1е(хе), хб В") и всех у ~ В" выполняется тд!!УГ~ ~~(Чхчо(х) У~ У) ч уе!!У!~ в уг ) О. Тогда, если на шаге Ю алгоритма 1 вектор йг выбирать так, что для некоторого фиксированного а ) 0 выполняется неравенство — (ЧР (х"), йе) ва(Цо(х")!! ° !!й"!!, то алгоритм 1 порождает либо конечную последовательность (х")гн о, последний влемент которой минимизирует функцию ')о в В", либо бесконечную последовательность (х')Г=о, сходящуюся к точке минимума х'. Все варианты сопряженных градиентов отличаются только разными способами вычисления векторов й' на шаге 1Ч алгоритма 1 и способами вычисления шагового множителя р„на шаге Ч алгоритма 1. 92 2.
Метод еоиряжеввыя традиевтое е воеетаиовдевием Алгоритм 2 Н а ч а л о. 1, Выбрать произвольное начальное приближение хе Е 11", натуральное число т в и (т — момент восстановления); положить й = О. 11. Вычислить Цо (хе) и положить уе = — ЧГе (х'), й' = Ч1а (х ) О с н о в н о й ц и к л.
111. Вычислить шаговый множитель р„, удовлетворяющий условию ~,(ха+ р,й~) = гп!п),(х" + рй~). оьо 1Ч. Вычислить следующее приближение ха+1 = х" + р,й'. Ч. Вычислить Ч1е (х"+') и положить д" ь' = — Це (х'+'). Ч1. Если дьь' = О, то положить х* = х"+' и прекратить вычисления; иначе перейти к шагу Ч11.
Ч11. Вычислить коэффициент ь+1 1 <а+ е~ е ~') йе=ш — / -( )'' (е', е') О, если 1 целое число; где ш(1) = 1, если 1 нецелое число. Ч1П. Вычислить вектор йа+1 йе-~-1 ( () йь 1Х. Положить й = й + 1 и перейти к шагу П1. Теорема 2. Если функция ~о трижды непрерывно дифференцируема и ее матрица вторых производных Ч'„„1е (х) удовлетворяет условию У ((У((т<(7я4(х)У У)(У ((У~' О(У (У < для всех х, у Е В", то бесконечная последовательность (хе)ь о, порожденная алгоритмом 2 с произвольным начальным приближением х', сходится к решению х* и существуют такое целое число т ) О и константа 6, Е (О, оо), что '1 х'+" — '((< дт(( "— *((т для всех й ) т, принадлежащих множеству (О, т, 2т, ...). Алгоритм 2' Н а ч а л о. 1.
Выбрать произвольное начальное приближение хе ~ В", натуральное число т ) и (т — момент восстановления); положить й = О. П. Вычислить Цо (х') и положить 2о = — Це (х'), йе = — Ч~е (хе). О с н о в н о й ц и к л. 111. Вычислить шаговый множитель р„удовлетворяющий условию )е(ха+ райт) = ппп ~ (х'+ рйе).
оьо 1Ч. Вычислить следующее приближение ха+а „а ( райа Ч. Вычислить 7!е (ха+'). Если 7!е (ха+') = О, то положить хе = ха+' и прекратить вычисления; иначе перейти к шагу Ч1. Ч1. Если й кратно т, то перейти к шагу НП; иначе перейти к шагу ЧП1. ЧП, Положить д"+! = — Ч~о (ха+'), йа+! = — 7~о (ха+') и перейти к шагу Х1. ЧП1. Положить д'+' = — 7(е (х'+'). 1Х. Вычислить коэффициент ~~ ~~~~~~а !1 аа !!- Х. Вычислить вектор л'+! = на+! + раЛа.
Х1. Положить й = й + 1 и перейти к шагу П1. Для алгоритма 2' имеет место теорема, аналогичная теореме 2. 3. Реалнеуемые модифннанин алгоритмов еонрлмеиимл градиентов Алгоритм Л Н а ч а л о. 1. Выбрать произвольное начальное приближение х' р Л", константы е, ) О, те ) О, р е ~0, 1), ()' е (О, 1), р" е (О, 1) (рекомендуется е, = соз 85', у, = соз 5, р = 0,6, рч = р" = 0,8), натуральное число т ) и (т — момент .восстановления); положить й = О.
П. Вычислить Це (х'). П1. Если Чге (ха) = О, то положить хе = хе и прекратить вы- числениЯ; иначе положить да = — 71е (х'), Ье = — 71е (х'), е = е„ у = уе и перейти к шагу 1Ч. Основной цикл.!Ч.Положитьх=ха. Ч. Вычислить вектор Ь = — Ьа, ! Иа!! У1. Определить функцию О: Н' -а- Ва 8(Р) = 1е(х+ РЬ) — 1е(х). Ч11. Положить р = О. ЧП1. Вычислить скалярное произведение (Ч!а (х+ рл), Ь) и положитыр (р) = (7Д> (х + рй), й) 1Х. Если ар (р) = О, то перейти к шагу ХЧП1; иначе перейти к шагу Х.
Х. Положить 1, = 1. Х1. Вычислить Л=О(р — ) р(р)) — В(р)+,' Ьр'(р). ХП. Если Л ( О, то положить р = р — ахи (р) и перейти к шагу ХП1; иначе положить )а = р). и перейти к шагу Х1. Х1П. Вычислить Ч1, (х + рй). Х1Ч. Если Ч1» (х + рй) = О, то положить хо = х + рЬ и прекратить вычисления; иначе перейти к шагу ХУ. ХЧ. Вычислить ч>(р) = (71,(х+ рй), Ь).
ХН1. Вычислить 6 = ч(р)/) Ч1»(х+ рй)« ХЧП. Если < 6 < ( е, то перейти к шагу ХЧ1П; иначе перейти к шагу Х. ХЧ1П. Вычислить следующее приближение х»+' = х + рЬ. Х1Х. Положить д»+' = — 71» (х + рй). ХХ. Вычислить коэффициент — l Ь»1 где О, если / — целое число, ш(/) = 1, если / — нецелое число.
Х Х1. Вычислить вектор Ь"+' = д~+' + р»й». ХХП. Положить Ь = й + 1. ХХП1. Если выполняется неравенство (а', й") > у«а'<<1Ь'( то перейти к шагу 1Ч; иначе положить е = <)'е, у = <1"у и перейти к шагу 1Ч. Для алгоритма 3 имеет место теорема, аналогичная теореме 2. Алгоритм 3' (реализуемая модицикация алгоритма 2) Все шаги алгоритма 2, кроме шага П1, остаются без изменений. Шаг П1 алгоритма 2 следует заменить шагом П1'.
ПГ. Вычислить шаговый множитель р», используя для этого алгоритм 1Б или алгоритм 2Б. '; Алгорняом 1Б (алгоритм вычисления шагового множителя р») 1. Выбрать константы р ) О и )» Р (О, '/о). П. Определить функции 0(м х ) = 1о(х" + мй ) 1о(" ) м(1 )о)(Ч1»(х") Ь )' <р(со, х») = 1,(х»+ сой») — 1»(х») — сй(Ч1,(х»), Ь"). П1. Положить р = р. 1Ч. Вычислить значение 0 ()», х'). Ч. Если 0 (р, х») = О, то положить р» = 1» и прекратить вычисления; если 0 (р, х») ( О, то положить 1» = 1» + р и перейти к шагу 1Ч; если 0 (р, х») ~ О, то перейти к шагу Ч1. Ч1. Вычислить значение ф (р, х»).
ЧП. Если <р (р, х») (О, то положить р» = р и прекратить вычисления; иначе положить ар —— р — р, Ь» = р и перейти к шагу ЧП1. ЧП1. Положить ! = О. 1Х. Вычислить о~ — — (а -)- Ь;)/2. Х. Вычислить значения О (о~, х"), ~р (оь х»). Х1. Если выполняются неравенства О (о;, х') ) 0 и ~р (о/, х") ( ( О, то положить р„= о/ и прекратить вычисления; иначе перейти к шагу ХП. ХП. Если 8 (о„х») ) О, то положить аоь~ = аь Ь,+1 = о; и перейти к шагу Х!Н; иначе положить а~+~ = о;, Ь,,1 = Ь| й перейти к шагу ХП!.
ХП1. Положить / = ! + 1 и перейти к шагу 1Х. Алгоритм 2Б (алгоритм вычисления шагового множителя р» по методу золотого сечения) !. Выбрать произвольные константы е, ) О, а ) О, р ) О, 1Е(0 !). П. Вычислить дроби Фибоначчи Р, = (3 — )/5)/2 и Р, = = ()/5 — 1)/2. 1П. Положить е = е». 1Ч. Определить функцию 8: Б» -~ Л' 0(р) = /. (х + рй") — /,(х"). Ч. Вычислить значения О (р) и 0 (0). Ч1. Если 0 (р) ) 0 (0), то положить а, = О, Ь, = р и перейти к шагу Х; иначе положить» = О, р» — — 0 и перейти к шагу ЧП. Ч!!. Вычислить р~ »1 = р, + р.
Ч!11. Вычислить 0 (рьы). 1Х. Если О (р;, ~) в О (р;), то положить а, = рх ь Ь, = р»»» и перейти к шагу Х; иначе положить ! = ! + 1 и перейти к шагу Ч11. Х. Положить ! = О. Х1. Вычислить !~ —— Ь/ — а;. Х! 1, Если !; ( е, то перейти к шагу ХЧП; иначе перейти к шагу Х П1. ХП1. Вычислить о; = а/+ Р»!/; ш; = а~+ Р,!/. Х1Ч. Вычислить 0 (о;), 8 (о0). ХЧ. Если О (о;) ( О (ш/), то положить а~+, — — ап Ьн., = ш н перейти к шагу ХЧ!; ийаче положить ан| = оь Ь;ь| =- Ь| и перейти к шагу ХЧ1.
ХЧ1. Положить / = / + ! и перейти к шагу Х1. ХЧП. Положить р = (а; + Ь|)/2. ХЧП1. Если 0 (р) ( — ае, то положить р„= р и прекратить вычисления; иначе положить е =- ре и перейти к шагу Ч. Алгоритм Я" (реализуемая модификация алгоритма 2') 96 Все шаги алгоритма 2', кроме шага П1, остаются без изменений. Шаг П1 алгоритма 2' следует заменить на шаг П1". П1". Вычислить шаговый множитель р», используя для этого алгоритм 1Б или алгоритм 2Б. 4. Метод еовраыеввыв градвевтов два иивиивааиив квадратиивыв 4чпгкивй 3 а д а ч а 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
