И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 21
Текст из файла (страница 21)
Найти агн пип (е (х) длЯ заданной квадРатичной гаа» функции ~е (х) Й Чт (Ах, х)+ (Ь, х) + сг. Алгоритм 4 Н а.ч а л о. 1. Выбрать произвольное начальное приближение х' Е В" и положить Ь = О. П. Вычислить Ах'+ Ь и положить Ье = — (Ахе+ Ь), ге = Ье П1. Если Ь' = О, то положить х' = х' и прекратить вычисления; иначе перейти к шагу 1Ч. О с н о в н о й ц и к л.
1Ч. Если Ь = О, то перейти к шагу ЧП; иначе вычислить вектор д» ', у» — ' = А (х» — х»-') = р» ~АЬ» — ' и перейти к шагу Ч. Ч. Вычислить коэффициент р» по одной из эквивалентных формул (г», г ), (г», г») . (г», г») (Ь г ) (Ь г ) (г г ) Ч1. Вычислить вектор Ь» =. — г' + (3»Ь»-'. ЧП. Вычислить шаговый множитель р, по одной из эквивалентных формул (ге, Ь») (г», Ь») (ЛЬ», Ь») * ' (ЛЬ', Ь») ЧП1. Вычислить следующее приближение х'+' = х" + р»Ь'.
1Х. Вычислить Ах»+' + Ь и положить г'+' Ах"+' + Ь. Х. Если г»+' = О, то положить хе = х»+' и прекратить вычисления; иначе перейти к шагу Х1. Х1. Положить Ь = Ь + 1 и перейти к шагу 1Ч. Теорема и. Если А — строго положительно-определенная симметричная матрица, то алгоритм 4 решает задачу 4 за число итераций, не превосходящее и и (г) — для всех 1, О < 1( и — 1, выполняется неравенство (Ах' + Ь, Ьг) чь О, если Ах' + Ь Ф О; (11) — точка х' (1 = 1, ..., и — 1) является точкой минимума квадратичной функции Д на подпространстве, образованном векторами Ь', ..., Ь' и проходящем через точку хе. г-зц 97 5. Реалиеуемаа модификации алгоритма е переменкой метрикой Алгориизлз д Н а ч а л о. 1.
Выбрать произвольное начальное приближение хе Е //", целое число а (! ( а( !О), константу )) ~ ('/„'/,) и положить Ь = О, / = О. П. Вычислить Ч/е (хе), если Ч/е (хе) = О, то положить х' = хе и прекратить вычисления; иначе перейти к шагу 1П. 1П. Положить Ие= / (/ — единичнаЯ и Х и-матРнца), йл = Ч/е (хе) О с н о в н о й ц и к л. 1Ч. Вычислить вектор Ь" = //зйз. Ч. Если число Ь кратно а, то положить / = / -)- 1, а = За и перейти к шагу Ч1; иначе перейти к шагу Ч1. Ч1.
Положить х = хз, Ь = Ь", / = О. ЧП. ОПрЕдЕЛИтЬ фуНКцИЮ О1 ://' -ь //' О (сс) = /, (х + аЬ) — /з (х). ЧП1. Положить р = О. 1Х. Вычислитыр (р) = (Ч/е (х + рЬ), Ь). Х. Если гр (р) = О, то положить р„= р и перейти к шагу ХЧ; иначе перейти к шагу Х!.
Х1. Положить )ь = 1. Х П. Вычислить Л = О (р — йхр (о)) — О (р) + — )ор'(р). ХП1. Если Л ( О, то положить / = 1+ ! и перейти к шагу Х1Ч; иначе положить )ь = р)ь и перейти к шагу ХП. Х1Ч. Если / ( /, то положить р = р — )ь~р (р) и перейти к шагу 1Х; иначе положить р„= р — )ьгр (р) и перейти к шагу ХЧ. ХЧ. Вычислить следующее приближение хз+' = х [- р Ь. ХН1. Вычислить Ч/е (х"+') и положить дл+' Ч/о (х'+').
ХЧП. Если дз+' = О, то положить хе = хз+' и прекратить вычисления; иначе перейти к шагу ХЧ1П. ХЧП1. Вычислить векторы гз = дз+' — йз; гз = хз+' — хз. Х1Х. Вычислить матрицу И и Нз" (Н ')'+ з[")' а+1= з (Нзгз, ге] [г", гз) ХХ. Положить Ь = Ь -)- ! и перейти к шагу 1Ч. Библиографические указания. Параграф написан на основании работ )285), [320).
Методы сопряженных градиентов и алгоритмы с переменной метрикой рз. шения задач безусловной оптимизации исследовались также в работах 1229, 494, 230, 291, 292, 539, 471, 506, 492, 470, 390, 454, 362). В работе [542) доказываются теоремы о конечной сходимости варианта метода сопряженных градиентов для минимнзлции начального направления поисиа.
В рае ботах [482, 484, 534, 466) изучаются методы типа переменной метрики. 98 2.5. Методы сопраженных направлений 3 ад а ч а 1. Найти агя пйп 1»(х) для заданной непрерывно „еле дифференцируемой функции 1» . Н" ~- В'. Предположение 1. Функция )е дважды непрерывно дифференцируема и ее матрица вторых производных Ч'„1е (х) удовлетворяет условию У!)У)~((Ч,„~»(х)У, У) (У»~У)т, тт >У! >О, при всех х, у Е Н", Определение 1.
Векторы р', р', ..., р"-' называются сопряженными, или А-ортогональными, если (р', Ар!) = О при ! чь 1, где А— строго положительно-определенная матрица. 1. Метод еопрямеппых папраалеппя е аоеетапоалеппем матрицы г»-' = х' — х»-' = р» !й"-', а'-'= Че(х') — Ч1»(х ') Ч!1. Вычислить матрицу Н» по одной из приведенных ниже фор- мул: , -! ( — )т Н~,к !(У )тн», Н» = Н» — ! +»-!»-! т»-!»-! ', (2.3) (г,л ) (Н~ !2,2 ) » — »т Н» — — Н~ !+(г»-' — Н» !д' ') (ь-!т Н» = Н» ! + (г»-! — Нейь !) (» — 1»-!) (2.4) (2.$) Алгорип»м 1 Н а ч а л о.
1. Выбрать произвольное начальное приближение х' Е Н", произвольную симметричную строго положительно-определенную матрицу Н„удовлетворяющую условию уа ) у 1» ( ~~ (Неу У) ~ г»! УГ. 7» ~ уе > О, ЧУЕВ", (в частности, можйо выбрать Йе = 1, где 1 — единичная п )( л-матрица); положить й = О. О с н о в н о й ц и к л. 11. Вычислить Ч1е (х»). 111.
Если ЧД„(х») = О, то положить х* = х» и прекратить вычисления; иначе перейти к шагу ! Ч. 1Ч. Если й = О, то перейти к шагу Ч111; иначе перейти к шагу Ч. Ч. Если 2 делится нацело на а, то положить Н» = Н, и перейти к шагу Ч!11; иначе перейти к шагу Ч1. Ч1. Вычислить векторы «-! ( «-! т Н,-Н,— (т,г ) ь-! ( «-!)т «Нь-! «! ! ) (г, г"= ) Н Н )(«Р!«(»«) Ф«Р!«( «) + "~~) (н,р1,( ), 91,( «))-(й~', 91,(' !)) н,я«-! (й« вЂ” !)т н,=н,+ , и! (» (2.9) н«7!«( «) («~~)~ Н«=Н,+ (», т!0(» Э (зло) 71П.
Вычислить вектор движения й' к следующему приближению х"+' (2 т) Н«т!«(" ) 1Х. Вычислить шаговый множитель р«из условия 1«(х«+ р,й') = ппп !«(х" + рй«) яво Х. Вычислить еледующее приближение х'+' = х«+ р'й'. Х1. Положить й =» й + 1 и перейти к шагу П. Теорема 1. Если еыполнено предположение 1, то бесконечная последоешпельность (х«)«=о, порохсденная алгоритмом 1 (где матрица Н, еычисляетея по одной из формул (2.3) — (2.10)), сходится к решению х* ео егер»линейной скоростью 1х(Е+!)я хо)() )х!» »«3 1 0 где Ц„-«О при ! -э оо. Замечание 1. Если на какой-либо итерации начальной стадии процесеа минимизации по алгоритму 1 вектор й" = О, то необходимо начать процесс заново, восстановив матрицу Н,.
В. Метод оопряя!ввв««я пяпряяяовва бея «от«таво«я«вдов«травм Алгоритм 2 Н а ч а л о. 1. Выбрать произвольное начальное приближение х' е НЯ, произвольную симметричную строго положительно-определенную матрицу Н„удовлетворяющую условию у«ЬГ<(Нр р)<у ЬГ у '-Ъ>0. ЧрбН' (в частности, можно выбрать Н, 1, где 1 — единичная и )( и- матрица); положить й О. О с н о в и о й ц и к л. 11.
Вычислить Р!«(х"), если !«1«(х") ,! ! (»-!)т н,,~ ! (2»-!)т)) Н=Н + (т ° у ) (Н» е к ) »-! т Н =Н»,+(т — — Н» !д — ) » — !» — ! (2 ) (т,е ) (»-!)т Н =Н! !+(т»-' — Н,у» — ') » — ! (,» — 1,» — !) и ек ! (ь» — !)т Н,=Н,+ — ь+ Ч1. Вычислить вектор движения й" к следующему жению х»+! (2.12) (2.12) (2.!4) прибли- й» = — Н»Я (х»). ЧП. Вычислить шаговый множитель р, из условия 1 (х»+ р»й») = ш)п( (х»+ рй"). рьо ЧП1. Вычислить следующее приближение х»+' х" + р,й'.
1Х. Положить й = й + 1 и перейти к шагу П. Теорема 2. Пусть выполняются предположения 1. Тогда: 1) если первые т точек (т ( ьь и зависит от точки х') бесконечной последовательности (хл)»=ь вычислены с помощью метода сопряженных направлений с восстановлением матрицы Н» (т. е.
с пол!ощью алгоритма 1), а остальные точки этой последовательности— с помощью метода сопряженных направлений беэ восстановления (т. е. о помощью алгоритма 2), то последовательность (х»)» ь сходится к решению х* при произвольном выборе начального приближения хр; 2) если нач льное приближение х' выбрано в достаточно молой окрестности точки минимума хр, то бесконечная последовательность (х»)»-ь, порожденная алгоритмом 2, сходится к решению хь; 3) бесконечная последовательность (х»]» р, порожденная алгоритмом 2, где матрица Н вычисляется по формуле (2.14), неэа- 1О1 О, то положить х* = х" и прекратить вычисления; иначе перейти к шагу П1. П1.
Если й = О, то перейти к шагу Ч1; иначе перейти к шагу 1Ч. 1Ч. Вычислить векторы т»-' = х» — х"-' = р» !й' д»-! = 71 (х») — Ц,(х" — '). Ч. Вычислить матрицу Н„по одной из приведенных ниже формул: (2.11) висимо от выбора начального приближения хе сходится и решению хе со сверхлинейной скоростью 1хрьпя — хе!!(Лс„!1хгл — хе!Ь ! = О, 1, где Лс„-» 0 при !-» оо. 3 а м е ч а н и е 2. Из оценок скорости сходимости методов сопряженных направлений следует, что и итераций метода сопряженных направлений эквивалентны (в смысле скорости сходимости) одной итерации методов типа Ньютона — Канторовича или методов двойственных направлений.
Однако они значительно превосходят по скорости сходимости градиентные методы. С теоретической точки зрения метдды сопряженных направлений без восстановления матрицы предпочтительнее в том случае, когда Ню -» (7„,Де (х»з)) — ' при ! -» оо. К настоящему времени установить строгое выполнение этого условия не удалось. Однако можно предполагать, что такое условие будет выполняться для методов, которые при минимизации квадратичных функций — (Ах, х) + 1 + (Ь, х)+ у дают Н„= А В (188) рекомендуется применять алгоритм 1 с восстановлением матрицы, если матрица Н, вычисляется по формулам (2.6) — (2.10), а алгоритм 2 без вос тановления матрицы, когда матрица Н» вычисляется по формулам (2.3) — (2.5). 3.
Маяка«язацвя каадратвовых В«уякцвй с помощью метода сопряжеввых ваправяеввй 3 а д а ч а 3. Найти агу ппп !е для заданной квадратичной функ««а» цин !е (х) Й вЂ” (Ах, х) + (Ь, х) + а. Алеоритле 3 Н а ч а л о. !. Выбрать произвольное начальное приближение хе ~ Н", произвольную строго положительно-определенную матрицу Н, (в частности, можно выбрать Н, = 1, где 1 — единичная п х и-матрица); положить я = О. Ос но в н о й ц и к л. 11.
Вычислить Ада+ Ь и положить га = Ахе + Ь. Если ге = О, то положить хе = х" и прекратить вычисления; иначе перейти к шагу П1; 1П. Если й = О, то перейти к шагу Ч1; иначе перейти к шагу 1Ч. 17. Вычислить векторы гь-' = х" — хь — ' = р,,йе-', д" ' = Аге-'. Ч. Вычислить матрицу Н, по любой из формул (2.3) — (2.10), !02 Ч1. Вычислить вектор движения Ь' к следующему приближению х"+' Ьь = — Н~~гь. Ч11. Вычислить шаговый множитель р„по одной нз формул (го, ЬФ) (гй, Ьь) (Лаь, Ь1 ' Р" (ЛЬ", аь) ЧП1. Вычислить следующее приближение хь+' = х~+ р„Ь~.
1Х. Положить Ь = Ь + 1 и перейти к шагу П. Теорема 3. Если А — строго положительно-определенная симметричная матрица с постоянными членами (т. е. (Ах, х) ) О яри любом х Ф О), то алгоритм 3 решает задачу 3 за число итераций, не превосходящее и, и (1) — точки хь, х', ..., х", порожденные алгоритмом 3 яри различных снособах вычисления матриц Н„одни и те же; (Й) — для всех 1, О ( 1 ( п — 1 выполняется условие (Ах' + + Ь, Ь') Ф О, если Ах' + Ь Ф О; (1м) — точка х', 1 = 1, ..., я — 1, является точкой минимума квадратичной функции гь на яодпространстве, образованном векторами Ьь, Ь', „Ь' ' и проходящем через точку хл; ((о) — если в алгоритме 3 матрицу Н» вычисляты яо формулам (2.3) — 12.3), то Н„= А ', по формулам (2.3), (2.Н)), то Н„= Н;, по формуле (2.6), то Н„= О; по формуле ~2.9), то Н„чь Н,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
