И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 22
Текст из файла (страница 22)
Ниже приводится метод сопряженных направлений, в котором непосредственно находят вектор движения Ь" без вычисления матрицы Н,. Алгоритм 3' Н а ч а л о. 1. Выбрать произвольное начальное приближение х' ~ Н", произвольную строго положительно-определенную симметричную матрицу Н, (в частности, можно выбрать Н, = 1, где 1 — единичная л Х я-матрица); положить Ь = О. 0 с н о в н о й ц и к л.
П. Вычислить Ах" + Ь и положить г" = Ах" + Ь. 1П. Если хч = О, то положить х* = х" и прекратить вычисления; иначе перейти к шагу 1Ч. 1Ч. Если Ь = О, то вычислить вектор Ь' по формуле Ьь = — Ньгь и перейти к шагу Ч; иначе вычислить вектор движения Ь" по любому из алгоритмов 1А, 2А, ЗА, 4А и перейти к шагу'Ч. Ч. Вычислить шаговый множитель р, по одной из эквивалентных формул (,0 Ьь) (Аль, Ьь) ' Ч1. Вычислить следующее приближение х"+' = х" + рьЬ". 103 ЧП. Положить Ь = Ь + 1 и перейти к шагу П. А,ггоритм 1А (алгоритм вычисления вектора Ь») 1. Вычислить вектор д» ' = г" — г» '.
11. Вычислить коэффициент ()» по одной из эквивалентных формул ( Н»» г» ! ) (Н,г», г») — (Ь" ', г! ') (1,» — 1» — !) (Н,»», г") — (»» ', г" ') 1!1. Вычислить вектор Ь» = — ()»Н»г» + (1 — Р,) Ь»-!. Алгоритм 2А (алгоритм вычисления вектора Ь») 1.
Вычислить коэффициент (Ног» г ) (Н, ', г») — (Ь" — ', '-') ' 11, Вычислить вектор Ь» = — Н»г»+()»(Н»г» + Ь '). Алгоритм 3А (алгоритм вычисления вектора Ь») 1. Вычислить вектор 3»-! = г' — г"-'. 11. Вычислить коэффициент ()» по одной из формул (Н,г», у ') (Н,»», а»-') (!»-!» !) ' »'» (»»-~ »-4) 111. Вычислить вектор Ь» = — Н»г»+ '()»Ь' '. Алгоритм 4А (алгоритм вычисления вектора Ь») 1. Вычивлнть коэффициент р» по одной из эквивалентных формул (Н„»", !») (Н»»", г») Р'= (ь,г-)' Р'= (н..-.у-) 11. Вычислить вектор Ь» = — Н г»+))„Ь»-!. Теорема 3'. Если А — строго положительно-определеннол симметричная матрица с постоянными членами, то алгоритм 3' решает задачу 3 за число итераций, не прееосходяи(ее и, и для последоеательности х', ..., х", порожденной алгоритмом 3', спраеедлиеы утверждения (»1), (И), (И») теорема 3.
Методы сопряженных направлений могут быть применены и для минимизации выпуклой квадратичной функции !»(х) с»ь!' (Ах, х) + (Ь, х) + а, 104 где (Ах, х) ~ 0 при х чь О. При этом следует учитывать два случая. 1. Минимум квадратичной функции 1» существует. Тогда ал.
горитм 3 и алгоритм 3' решают задачу минимизации 1» за число итераций, не превышающее л. 2. Функция 1» не достигает минимума. Тогда пыли некотором Ь, 0( Ь( л — ! будет выполняться условие (Ай», Ь) = О, что влечет р» — — оо. 4. Модифиввроееввыа метод еопражеввыа вапреалеаай, ве требующий вычиелеиаа прои»водима А ~»ории»х» 4 Н а ч а л о. 1. Выбрат»п начальное приближение х' е Р 11", удовлетворяющее условиям теоремы 4; ортонормированный коорди- натный базис Ь ', Ь', ..., Ь'"; произвольную константу е ~ (О, 1) (рекомендуется выбрать з Р [10 ', 10 )). П. Положить Ь = 1.
О с н о в н о й ц и к л. П1. Положить ! = 1. 1Ч. Вычислить шаговый множитель р»,1 из условия 1»(х»' '+ Р»,1Ь"') = т!п1»е(х»' '+ Рй»х). Р Ч. Вычислить следующее приближение х" = х»1-1 + р»,1Ь» '. Ч1. Если» и, то положить»= 1+ 1 и перейти к шагу 1Ч; иначе перейти к шагу ЧП. ЧП. Вычислить у» = [ х»" — х»о[. ЧП1. Вычислить вектор Ь'"+1 — (х' " — х» '), ! 7» 1Х.
Вычислить шаговый множитель рд„+1 из условия 1»(х»" +р» +1Ь»х+1) ш!пге(х»»+рй» "+'). о Х. Вычислить следующее приближение х»м +1 х»,е + Р» +1Ь»л ь1 Х1. Найти индекс г Е [11л[, удовлетворяющий условию р»,, = шах (р»г, р»дь ..., р», ). ХП. Если Ь = 1, то вычислить определитель Ь», столбцамн которого являются векторы Ь ', Ь ', ..., Ь '"; иначе перейти к шагу ХШ. ХП1. Если (р»лЛ»/у») ~ з, то перейти н шагу Х1Ч; иначе перейти к шагу ХЧ1П. Х1Ч. Положить 1 = !.
106 ХЧ. Если ! = в, то положить Ь»+14 = й '"+' и перейти к шагу ХЧ1; иначе положить Ь+ л = Ь л и перейти к шагу ХЧ1. »+гл»л ХЧ!. Если 1 ( и, то положить ! = 1 + 1 и перейти к шагу ХЧ; иначе перейти к шагу ХЧП. ХЧ11. Вычислить Л»ь~ = р»лй»/у» и перейти к шагу ХХП. ХЧ11!. Положить ! = 1, Х1Х. Положить й»+гв = [тд1. Х Х. Если 1 ( и, то положить 1 = 1 + 1 и перейти к шагу Х1Х; .иначе перейти к шагу ХХ1. ХХ1. Положить г!».д = ех» и перейти к шагу ХХП.
ХХ11, Положить х»+гл = х'"+'. ХХП1. Положить й = й + 1 и перейти к шагу П1. Теорема 4. Если выполнены условия: (г) — функция 1» — кипре рывно дифференцируема; (ьв) — функция 1 — строговыпуклая; (а٠— начальное приближение х'о в алгоритме 4 таково, что множество Х,=(х[1,(х)(1,(х''), хай") ограничено, то последовательность х»', 1 = О, 1, ..., и; й = 1, 2, ...
..., порожденная алгоритмом 4, сходится к единственной точке минимума х* функции 1». Библиогрогрилеекие улан»лил. Параграф основан на работах [320, 108, 110, 1!2, 4981. Методы соприженных направлений исследовались также в работах [109, 295, 540, 570, 470, 3621. 2.6. Методы псевдообратпых операторов 3 ад а ч а О. Найти агй ппп 1, (х) для заданной функции »оял 1» ° е» Предположение О.
(а) — функция 1» (х) дважды дифференцируемая по Фреше; (й) — градиент Ч1» (х) функции 1, (х) удовлетворяет в В" условию Липшица с константой у, ~ О; (!!!) — матрица вторых производных гл„1» (х) (гессиан) функции 1, (х) удовлетворяет в Вл условию Липшица с константой у, ~ О. Методы псевдообратных операторов по существу являются квазиньютоновскими. Скорость сходимости этих методов — сверх- линейная. В й-й итерации за направление движения к следующему приближению х»+' выбирается вектор ( — В„Ч1, (х»)), где „— матрица, аппроксимирующая обратный гессиан функции 1, (х) в точке х'. Вычисление матрицы В» основано на алгоритмах устойчивого псевдообращения прямоугольных матриц.
Достоинством методов псевдообратных операторов является то, что они не требуют вычисления матрицы вторых производных функции 1, (х), устойчивы к возмущениям, которые возникают из-за ошибок аппроксимации и дискретизации вычислений, обладают сверхлинейной скоростью сходимости и тогда, когда гессиан вырождается. 106 1. Ооиоаиоа алгоритм Алгорив»м 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение хо Е В ° П. Выбрать значение параметра и, »и ) и. П1. Положить й = О. О си о в но й ц и к л.
1Ч. Вычислить Ч(» (х'). Ч. Если й ~ и, то перейти к шагу Ч1; иначе положить х"+' = = х» — Ч)о (х») и перейти к шагу Х1. Ч1. Сформировать вспомогательную а Х и»-матрицу А»,, )см столбцом которой является вектор а'=х' < — в — х» < — /+'>, 1=1, ..., л». ЧП. Сформировать вспомогательную а х т-матрицу Н»„„1-м столбцом которой является вектор й~=РГ,(х»-< -л) ЧГ»(х» — ( — !+и), )=1, ..., л». ЧП1. Используя алгоритм 1' устойчивого псевдообращения конечномерных прямоугольных матриц, вычислить псевдообратные матрицы А» и (Нк Ах ), где символ С+ обозначает матрицу, + + + нсевдообратную к матрице С. 1Х.
Вычислить матрицу В», аппроксимирующую обратный гессиан В» =(Нь А», ) +1 — Н» Ах (Нх А». ) ° + + + + + Х. Вычислить следующее приближение х»+' = х» — В»Ч1» (х»). Х1. Положить й = й + 1 и перейти к шагу 1Ч. Ниже приводится алгоритм П,'н для псевдообращения и х тматрицы С„, состоящей из строк а', » = 1, ..., и, (а'=(а',, а', ..., а')). Алгори»мм 1' (регуляризованный рекуррентный алгоритм П) ~ устойчивого псевдообращення конечномерных прямоугольных матриц) Н а ч а л о. 1. Выбрать параметр регуляризацни а ~ О. и П.
Вычислить ) а»), = ~ ~ а,'- ~. ~»о П1. Если )а»1») е, то вычислить матрицу размера п х 1 С;Ь = (о»)' (о» (п»)г) — ' и перейти к шагу 1Ч; если) а' '1» =' е, то положить Сг = О и перейти к шагу 1Ч. 1Ч. Положить 1 = 1. чйт Основной ц и к л. Ч. Если 1( и, то перейти к шагу Ч1; иначе прекратить вычисления.
Ч1. Вычислить вектор-строку с(' размера с с( =асыС». Ч11. Вычислить вектор-строку Ь' размера и Ь = а — с(Сс, с ь~.с с где Сс — матрица размера с х т, состоящая из первых с строк ис- ходной матрицы С„. Ч111. Вычислить 1 Ь' 1с = ~ ~ Ь'; ~, если ) Ь 1с ) е, то перейти с к шагу 1Х; иначе перейти к шагу Х1. 1Х. Вычислить вектор-столбец йс размера т д' = (1 — С,"'С,) (а + ) . Х. Вычислить вектор-столбец гс+с размера т гс+с = йсс(Ьсйс) с и перейти к шагу ХП, Х1. Вычислить вектор-столбец г'+' размера и гс+с С)С(с(с)г(1+ с(с(с(с)г) с и перейти к шагу Х11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
