И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 19
Текст из файла (страница 19)
Основной цикл. П1. Вычислить Ч1» (х»). 1Ч. Если Ч1» (х») = О, то положить х' = х» и прекратить вычисления; иначе перейти к шагу Ч. Ч. Найти е из условия е = гп!п [ео> ~[Ч1» (х») ~[). Ч1. Найти матрицу Н, (з) размера а х а, /-й столбец которой вычисляется по формуле о (Ч1»(Х + е/) — Ч1о(х»», 1=1, 2, ..., и, где е/ — /-й орт. ЧП.
Если существует обратная матрица Н» ' (е) и выполняется неравенство (Ч1» (х»), Н» (е) Ч1» (х»» ) О, то вычислить вектор й~(е) = — Н» ' (е) 71»(х») н перейти к шагу ЧП1; иначе положить е = з/2 и перейти к шагу Ч1. (Шаги ЧП! — ХЧП1 предназначены для вычисления такого р, что р(! — а)(Ч/о( ), а»(»<1»( '+ рй»(з»вЂ” — 1.( ')<р (Ч1.(х»). Ь»(а».
ЧП1. Определить функции 0»(Л) =1,(х»+ Л/»»(е)) — 1,(х") — Л(1 — я)(71»(х ), й»(е»; ф»(Л) =1»("+Лй»(з»-1»(х»)-Р" (Ч1»( ), 6'(з». 1Х. Положить р = р. Х. Вычислить О» (р). Х1. Если 0» (р,) = О, то положить р = р и перейти к шагу Х1Х; если О» (р) < О, то положить р = р + р и перейти к шагу Х; если О» (р) ) О, то перейти к шагу ХП.
ХП. Вычислить ф» (р). ХП1. Если ф» (р) < О, то положить р = р и перейти к шагу Х1Х; иначе положить ао — — р — р, Ь, = р и перейти к шагу Х1Ч; Х1Ч. Положить 1 = О. ХЧ. Вычислить значение о, = (а, + Ь;)/2. ХЧ1. Вычислить О» (о,), ф» (о,). ХЧП. Если О, (и,) !о 0 и ф» (ио) < О, то положить р = о, и перейти к шагу Х1Х; иначе перейти к шагу ХЧП1. ХЧП1. Если О» (о,) ) О, то положить а, ы = ао Ь,+~ = о„ ! = 1+ 1 и перейти к шагу ХЧ; иначе положить а~+~ = п„Ь»ы = *= Ь„( = 1+ 1 и перейти к шагу ХЧ. Х!Х. Если выполняется неравенство 1 ( '+ рй" ('» — 1. (») < — 1' вб то перейти к шагу ХХ; иначе положить е = е/2 и перейти к шагу т71. ХХ.
Вычислить следующее приближение ха-ь' = х" + рй" (е). ХХ[. Положить й = й + 1 и перейти к шагу 1П. Теорема 4. Если выполнены условия: (з) — функция [е дважды непрерывно дифференцируема и ее матрица Гессе невырождена при всех х из достаточно большой области; (В) — функция 7е строго выпукла; (И) — начальное приближение х' в алгоритме 4 таково, что множество Х, = (х([е (х) (~е(хе), х Е В") ограничено,.то бесконечная последовательность (ха)ь" е, порожденная алгоритмом 4, сходится к точке минимума х* функции 7е.
В работе [2881 утверждается, что алгоритм 4 имеет сверхлинейную сходимость. Библиографические уаиаиия. Параграф основан на работах [285, 320, 4861. Методы Ньютона решения задач безусловной оптимизации изучались также [186, 16, 49, 413, 423, 200, 105, 106, 278, 62, 498, 390[. В работах 1469, 544[ изучается метод Ньютона для вырожденных случаев.
В работах [537, 538[ нриводятся модели обобщенных алгоритмов и на их основании устанавливается глобальная сходимость модификаций метода Ньютона. 2.3. Методы двойственнык направлений 3 а д а ч а О. Найти агн ппп 7е (х) для заданной непрерывно ксяи дифференцируемой функции 7з 1 В" — В'. Методы двойственных направлений, обладая сверхлииейной скоростью сходимости, требуют, по сравнению с методами типа Ньютона — Канторовича, значительно меньшего количества вычислений (примерио в и раз),.при этом нет необходимости вычислять втоРые пРоизвоДные фУнкции 7е. С помощью лишь пеРвых пРоизводных так организуется процесс вычислений, что направление поиска приближается к направлению метода Ньютона — Канторовича.
1. Основной вариант А лгоритм л Н а ч а л о. 1. Выбрать: произвольное начальное приближение х'с В"; произвольную линейно-независимую систему и-мерных векторов рце, рц — ', ..., ре — ы-'1 (в частности, можно взять столбцы единичной матрицы 1 размера п Х п); константы у 0 (рекомендуется выбирать у Е [10 ', 10 1), [) Е (0,1) (рекомендуется выбивать Р = 0,8), е Е (О, т[з). 11. Положить Ф = О, р = 1, га = р". О с н о в н о й ц и к л. П[. Вычислить Р)е (ха), 87 1Ч. Если 710 (х") = О, то положить х' = хй н прекратить вычисления; иначе перейти к шагу Ч. Ч. Положить рй = р.
Ч1. Вычислить точку х = х" — рй Ч10 (х'). Ч!1. Если выполняется неравенство !0(х) !0(хй) (~ — ерй (0!0(хй) Ч10 (хй)) то перейти к шагу Ч1П; иначе положить р, = рйр н перейти к шагу Ч1. ЧШ. Положить хй+' = х и перейти к шагу 1Х. 1Х. Вычислить векторы !й-!-1 хй+1 хй. ай+ =%70(х+ ) — Ч10(х ). Х. Если выполняется неравенство (Рй,й — 0 — и ай+1) ~ У1Рй,й — 0з — и), !!00+!!! то перейти к шагу ХЧ; иначе положить б = 1 и перейти к шагу Х1. Х1. Вычислить вектор г'+' = бр" ' — !"-'!. Х11. Если ) гй+' ) (( гй ), то перейти к шагу Х111; иначе положить б = бр н перейти к шагу Х1.
ХП1. Вычислить Ч)'0 (хй + гй+'). Х!Ч. Вычислить вектор ей+! Ч): (хй+ !.й+!) Ч! (хй) ХЧ. Вычислить вектор рй+1.й+! (рй,й-<0-1! б!й+1) й,й — !»-!! ХЧ1. Положить! = О. ХЧП. Вычислить вектор рй!.1 й ! рй й ! (рй,й ! ай+1) рй ! ! й-!-1 ХЧ[П. Если 1( а — 2, то положить / = 1+ 1 и перейти к шагу ХЧ11; иначе перейти к шагу Х1Х.
Х1Х. Если й ( и — 1, то положить й = й + 1 и перейти к шагу Ш; иначе перейти к шагу ХХ, ХХ. Вычислить 7)0 (хй+'). ХХ1. Если Ч)'0 (хй-1!) = О, то положить х* = х"+' и прекратить вычисления; иначе перейти к шагу ХХ11. ХХ11. Вычислить вектор 0-1 /10+1 ~ (Чй (хй+1) рй+1,0+! 1) гй+1 ! ХХ1П. Если Я0 (хй+'), й"+') ( О, то положить рй+! = р и перейти к шагу ХХ1Ч; иначе перейти к шагу ХХЧ1.
ХХ1Ч. Вычислить точку х = хй+' + рй-! !)10+1. ХХЧ. Если выполняется неравенство Ь (х) — 10( "+')(ар+ (ч)0(х"+') л'!!). 88 то положить х»+о = х и перейти к шагу ХХХ1; иначе положить Р»-»~ = рр»„»с и перейти к шагу ХХ1Ч. ХХЧ1 Ес:ли (й~о (х'+'), 6»ы) ) О, то положить р,„, = р и перейти к шагу ХХЧИ; иначе положить р».ьс = р и перейти к шагу ХХ1Х.
ХХЧ!1 Вычислить точку х = х»+' — р»+сй»-~'. ХХЧ11!. Если выполняется неравенство 1о (х) — 1» (х"+') ( — ер»+ (Чо (х'+'), й'+'), то положить х»+' = х и перейти к шагу ХХХ1; иначе положить р»-»с = ~р»~-с и перейти к шагу ХХЧП. ХХ1Х. Вычислить точиУ х = х"+' — Р»+с»>1» (х»+с). ХХХ. Если выполняется неравенство 1» (х) — с о (х»+') ( ер»+с ) Чс'о (х»+') с(», то положить х'+» = х н перейти к шагу ХХХ1; иначе положить р»»с = рр»+с и перейти к шагу ХХ1Х. ХХХ1. Положить й = Ф + 1 и перейти к шагу 1Х.
Теорема». Если функция 1о дважды непрерывно дифференциру- ема и ее матрица вторых производных удовлетворяет условию У,!У(о((Ч~Д(х)У, У)(У»(У((», У»~У,)О при любых х, у Е 11", то бесконеч я последовательность (х»)» о, порожденная алгоритмом 1, сходится к решению х* задачи О со сверхлинейной скоростью (х"+с — х*!(а)»лХн+с ... Хм+с, где а, >Ч ( оо; Ъ.к+с ( 1 при любом 1 ~ О; )с., -~ О при с' -» оо, пРичем ~о (х»~-с) ( ~о (х»)с й = О, 1, ....
Для реализации методов двойственных направлений на ЭВМ требуется хранить в памяти'две системы векторов: г", г' — '...,, 㻠— '"-" и р»", р" » — ', ... р" » — с"-и Р' т. е. фактически две матрицы размера и х и. Частично этот недостаток устраняется, если в качестве векторов г» исполь- зовать векторы, направленные по координатным осям, так как в этом случае в памяти машины необходимо хранить лишь один и-мерный вектор вместо системы г», ..., г'-с" — 'с.
2. Модифицированный метод двойетвениых ваправлеввй, ие требуюшвй вычислении прововодвых Алгоритм 2 Н а ч а л о. !. Выбрать: произвольное начальное приближение х' ~ И"; произвольную систему и-мерных линейно независимых векторов р", р' — ', ..., ро — с"-'> (в частности, можно взять столбцы единичной матрицы ! размера и х и); константы уо ) О, а, Е (О. !), е р (О, >1»), б ) О, 1) 1; последовательность ($»)»" о, стремя- щуюся к нулю достаточно медленно (в частности, можно выбрать ~„= 1((й+ 1), й = О, 1, ...).
П. Положить й = О и перейти к шагу Х!Ч. 0 с н о в н о й ц и к л. П1. Вычислить вектор г», используя для этого алгоритм 2А, или по формуле г» = х» — х" — ', 1Ч. Вычислить вектор у» = х» + г". Ч. Вычислить р = ~! г» '1!. Ч1. Вычислить и-мерные векторы О», »р», »р», /-е компоненты которых О!=А(х»+Ре') — Ьо(х»))(1», (=1, ..., и; % = (1»(У + ре») 1»(У )И» ! 1ю ° ° ° и' »Р!. = »а!. — О», 1 = 1, ..., и, где е' — )сй орт. ЧП. Положить ф' = »р», ЧП1.
Вычислить скалярное произведение (р»-" †", »р»). 1Х. Если (р' '» — ", »р») = О, то положить р = )»/2 и перейти к шагу Ч1; иначе перейти к шагу Х. Х. Вычислить вектор р»,» (1!(р»-Ъ,»-о,г!,»)) р» — 1,» — о Х1. Положить ! = О. ХИ. Вычислить вектор р»,» — »-! р» — !,» — ! — ! (р» — !, » — ! — !»)!») р»,» Х1И.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
