XIV Аттетков и др. Методы оптимизации (1081420), страница 36
Текст из файла (страница 36)
242 5. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ Матрицы (Аь1 определякьт таким образом, чтобы последовательность (Аь~ при й — > оо имела предел, .равный Н ь(х*), где Н(х*) — матрица Гессе целевой функции, вычисленная в точке минимума х* этой функции. На к-й итерации алгоритма поиска точки минимума происходит спуск из точки х с тазом спуска нь~р'~, причем значение нь выбирают путем исчерпываюшеэо спуска в направлении вектора р . На первой итерации (й = 1) спуск начинают из выбранной начальной точки х~ и при этом обычно в качестве А1 берут единичную матрицу 1„порядка и.
Отметим, что в этом случае р = ло = — ига<1)'(х ), т.е. первая итерация алгоритма квазипьютоповского метода полностью совпадает с итерацией метода наискорейшего спуска (см. 5.1). Если принять Аь = Н 1(хь ') в (5.23) и нь = 1 в (5.14), то придем к „классическому" методу Ньютона (см. 5.3). Как было отмечено выше (см. 5.3). если целевая функция является сильно выпуклой, то алгоритмы метода Ньютона обладают квадратичной скоростью сходииости.
Поэтому можно ожидать, что алгоритмы квазиньютоновских методов будут иметь достаточно высокую скорость сходимости, если на каждой к-й итерации матрица Аь выбрана близкой к матрице Л ~(х~ ~) в точке х~ 1 Е К". Используя при конструировании матрицы Аь аппроксимацию матрицы Н 1(х" ') с учетом информации о градиенте целевой функции в той же точке х можно существенно упростить процедуру нахождения направления спуска на Й-й итерации.
Именно эти соображения лежат в основе построения алгоритмов квазиньютоновских методов. Остановимся на вопросе построения последовательности матриц Аь. Эти матрицы строят в соответствии с рекуррентным соотношением (5 21) Аь-ы =Аь+ЬАя, Й 614, где ЬАь — положительно определенная матрица порядка и, называемая поправ очной.
Способ ее выбора определяет вариант 5.5. Коезиньютоноеекие методы алгоритма квазиньютоновского метода. На первой итерации, как уже отмечалось, обычно принимают А1 = 1„. 1 Предположим, что 1(х) = — Ях, х) + (с, х) — кеадратиинвя функция с положительно определенной матрицей Я. В этом случае функция 1(х) сильно вьпдкла, ягас1Д1х) = Ях+ с (см. 3.6), Ь1о~ = рас11(хь 1) — ~гаду(х~) = 1,11х~ 1 — х"), и мы можем записать Я 'Ью~= — Ьх~, йЕИ, (5.25) где матрица Я совпадает с матрицей Гессе Н1х) функции ) 1х). В общем случае, проводя аналогию с (5.25), потребуем, чтобы матрица Аь ь1 в (5.24) удовлетворяла так называемому кввзиньютоновскому условию Аь маею~ = — Ьх~, к Е И, (5.26) а поправочную матрицу ЬАь в (5.24) выберем, исходя из условия !пп (/Аь.ь1 — Н '(х~))! = О, т.е. так, чтобы последовательность 1Аь) имела при й — 1 оо предел, равный Н '(хе).
Подставляя (5.24) в (5.26), получаем ЬАьЬше = — ахов — АьЬю . Непосредственной подстановкой можно убедиться, ь что для любого й Е И одним из решений этого уравнения будет матрица Ьх~у АьЬео"я (Ьы~,. у) ( зло", я) где у, я е 1Я'." — произвольные элементы из Бо.
Полагая у = Ьхь и я = Аьш", получаем с учетом (5.24) формулу Ьх" (Ьх~) АьЬлоЯ~Ьяо~) А„' (Ьшь, Ьхл) (АлЬьо", 1.'лю") 244 5. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ (Ьх~(Ьхя) у, у) (Аь~1у, у) = (Аьу,. у)— (АьЬю" (Ьюв)'А'у, у) (А~Ьюь, Ью") Из курса линейной алгебры известно ~1У), что любая положительно определенная матрица Аь порядка п может быть предт ставлена в виде Аь = СяС, где Ся невырожденная нижняя т треугольная матрица порядка и. Обозначив и = С у и и = = С Ьюь, перепишем (5.28) в виде (Ьх, у) (и, е) (Ью", Ьх~) (е, е) (5.29) /и/з!и!з — (и, и)в (Ьх ', у) )и)2 (~юя ~хй) ' (А~< 1у, у) = (и, и) Покажем, что знаменатель второго слагаемого в правой части (5.29) отрицателен.
В самом деле, учитывая, что Ьхь = = хьр, а направление спуска р на Й-й итерации определяется для выбора элементов последовательности ~Аь). Такой способ выбора матриц Аь приводит к одному из алгоритмов квазиньютоновского типа, известного в литературе как метод Давидона — Флетчера — Пауэлла., или ДФП-метод. Рассмотренный способ „обновления" матрицы Аяэ1 сохраняет ее свойство положительной определенности на каждой Й-й итерации. Для того чтобы убедиться в этом, воспользуемся методом математической индукции. Очевидно, что матрица А1 положительно определенная, если принять А1 = 1„.
Предположим, что при к > 1 матрица Аь также положительно определенная, и докажем, что матрица Ая ~~ в (5.27) положителы1о определенная. Выберем ненулевой вектор у Е К". Тогда с учетом (5.27) можно записать 245 о.оц Кннзиннютононекие методы согласно (5.23), получаем (Ьто,Ьх ) = (Зги~(х ') — рас1~(х ),х — х' ) = = — ось(бган~(х~ ), Аь ассад~(х~ 1)) — тсь(рас1~(х"), р ) < < — тсь(бгас1Дх ), р ), (х, у)л — — (Ах, у). (5. 30) Из представления Дх+6) — ~(х) = (АА 'бгЫ~(х), Ь) +о(~Ь~) = = (А 'рЫ~(х), Ь) +о(~п~) заключаем, что в евклидовом пространстве йси со скалярным произведением (5.30) градиент целевой функции принимает вид дтпл~(х) =А 'дезам~(х). Отсюда следует, что алгоритм квазиньютоновского метода, в котором используется (5.23), можно поскольку по предположению индукции матрица Аь положительно определенная.
Так как точку х~ находим при помощи исчерпывающего спуска из точки х в направлении вектора рн, то в соответствии со свойством (4.57) исчерпывающего спуска правая часть последнего соотношения равна нулю, т.е. (Лтоь, Лх") < О. В силу неравенства Коши -- Буняковского имеем ~и~з~е~з ) > (и, и), причем равенство возможно лишь при и = о, что с з учетом невырожденности матрицы Сь эквивалентно равенству у = Ьюь. Но тогда (Ьхь, у) = (Ьх", Ьи~") < 0 и в итоге при любом ненулевом векторе у Е Б'.и из (5.29) следует, что )и)2(е(з — (и., е) (Лх, у) с "с'" и) ~,~з ~~ ь ахь) ~ т.е.
матрица Аь 1 положительно определенная. К соотношению (5.23) можно прийти и из других соображений. Пусть А — положительно определенная матрица порядка и. Введем в Ки наряду со стандартным скалярным произведением (х, у) скалярное произведение 246 от МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ рассматривать как алгоритм наискорейшего спуска в меняющейся на каждой й-й итерации метрике р(х, .у) = (А 'х, у) при условии, что Аь — положительно определенная матрица. Поэтому квазиньютоновские методы иногда называют методами переменной метрики*. Можно показать**, что если то при минимизации квадратичной функции с положительно определенной матрицей Я алгоритм ДФП-метода позволяет получить точку минимума, не более чем за и итераций.
Векторы р ', Й = 1, и, определяющие направления спуска, являются сопряженными относительно матрицы е2 и связаны сооношениями При к = и эти соотношения означают, что симметрическая матрица АьЦ имеет н собственных значений, равных единице, а такая матрица является единичной, т.е. АиД = Ти. Отсюда А = е, ~, и, следовательно, матрица А„является обратной к матрице Гессе Н(х') = с2 квадратичной функции, вычисленной в точке минимума х'. Отметим, что если в алгоритме ДФП-метода А~ = 1и, то для квадратичной функции траектория поиска совпадает с траекторией, полученной по мезподу сопряженных направлений. Например, при минимизации квадратичной функции, рассмотренной в примерах 5.1 и 5.3, алгоритм ДФП-метода приводит к точке х* = ( — у'5, — 2~ 5) минимума этой функции из начальной точки ( — 2, 1) за две итерации, причем траектория поиска при выборе А1 = 12 полностью совпадает с полученной в примере 5.3 методом сопряженных направлений (см.
рис. 5.4). При минимизации целевой функции, не являющейся квадратичной, использование ДФП-метода в общем случае не позволя- *Сил Поляк. Б.Т. "*Сил Аоки М., а также: Базара М., Шетти К. 5.5. Квазикълотововские методы 247 ет найти точку минимума за конечное число итераций. Как и в методе сопряженных направлений„чтобы ослабить влияние накапливаемых погрешностей на сходимость ДФП-метода и уменьшить вероятность появления после очередных и итераций линейно зависимых направлений спуска, применяют процедуру „обновления" алгоритма, в соответствии с которой через каждыо и итераций в качестве матрицы Ае используют единичную матрицу, т.е.
полагают А„„вл.~ = А~ = 1„, т Е сл. Опишем алгоритм ДФП-метода в случае, когда (не квадратичная) целевая функция 11х) дифференцируема в вс". На предварительном этапе задаем значение ез параметра точности поиска в условии прекращения итераций ~ло~~ < ез и выбираем начаяьнук> точку хо. Принимаем Ал = 1„, формируем множество Хо = )п, 2п.....) моментое обновления алгоритма, полагаем Й = 1 и переходим к основной части алгоритма. 1. На к-й итерации в точке х~ ~ вычисляем антиградиент ло = — 5гас11(х ) целевой функции и проверяем выполнение неравенства ~ло ~ < ез. Если оно выполнено, то итерации прея кращаем и полагаом х' — хь ., 1(х*) = 1(х~ ).
В противном случае переходим к п.2. 2. Используя (5.23), вычисляем вектор р" = Аллою определяющий направление спуска из точки х, и, минимизируя функцию фь(лс) = 1(х + лср ), находим значение лся и точку хя = хк ~+ леере. Ес.ли /с Е Хо, то принимаем Аел ~ = 1„, полагаем к:= 1+1 и возвращаемся к п.1. В противном случае переходим к п. 3. 3. Полагаем Ьх =хи — хь ', скло~ =ли~+~ — ло~, по формуле (5.27) вычисляем матрицу Асл и полагаем й: = й+ 1 и возвращаемся к п.1.
Как отмечено выше (см. 5.2), применение процедуры,,обновления" алгоритма увеличивает общее число итераций, необходимых для достижения заданной точности поиска. Поэтому на практике используют варианты ДФП-метода, в которых (как и в случае метода сопряженных направлений) не используется 248 и. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ „обновление" алгоритма через фиксированное число итераций*. Поясним суть такого подхода на конкретном примере. Пример 5.8. Применив ДФП-метод, найдем минимум функции ~(тмхг) = (л~~ — хв)з + (и1 — 1)в (см.
пРимеРы 5.2, 5.5 — 5.7). Зададим параметр точности поиска ез = 10 з и выберем в качестве начальной точку хб = ( — 1, — 2), в которой ~(хо) = 13. Графическая иллюстрация процесса поиска точки минимума ю* = (1, 1) представлена на рис. 5.10. Здесь первая итерация совпадает с первой итерацией в примере 5.5,проведенной как по методу сопряженных направлений (см. рис. 5.6,а, б), так и по методу иаискорсйпп го спуска,. В табл. 5.8 приведены координаты точек хь, найденных при помощи алгоритма ДФП-метода, значений ~(жи) целевой функции в этих точках, а также матрицы Аь и матрицы, обратные к матрицам Гессе Н(х~) целевой функции.
Рис. 5.10 Подробнее сил Пиааниннмй Б.Л., Данилин ХО.М. 249 5.0. Кввоинъютоновеиие методы Таблини 5.8 Н 1(хи) 1(х~) Аи о) 3,0312 0,7246 0,0526 0,0168 3,4 Ш-4 4,3. 10 — 0 3 3,10 — 10 Из результатов вычислений видно, что заданная точность поиска минимума достигнута за 7 итераций, матрицы Ат и Н '(х7) на конечном, седьмом шаге поиска близки друг к другу. Матрица Н (х*), вычисленная в точке минимума х*, имеет вид (ед 1е) и также мало отличается от Ат и Н 1(х1). Отметим, что для достижения той же точности в методе наискорейшего спуска потребовалось 96 итераций. ф Возможны и другие способы построения последовательности (Ан) матриц с применением (5.24). Так, например, в алгоритме квазиньютоновского метода., называемого в литературе методом Бройдена Флетчера Шенно, или БФШ-методом, 1 (0,3787, — 1,4830) 2 (0,1584, — 0,1027) 3 (0,8593, 0,5572) 4 (0,8707, 0,7660) 5 (0,9942, 0,9708) 6 (0,9980, 0,9964) 7 (0,9999, 0,9999) с 0,100 — 0,127 с 0,073 — 0,005 0,382 0,382 с 0,272 0,481 с 0,494 0,914 0,512 -0,127) 0,986) — 0,005'1 0,456) 0,382 1 0,782) 0,481 1 1,351) 0.,914 1 '2,160) 1,016'1 2,516) 0,071 -0,143 0,118 0,089 0,.398 0,126 с 0,367 0,631 0,885 с 0,483 0.960 с 0,500 0,999 — 0,143'1 0,786) 0,089 ~1 0,567) 0,126 1 0,540) 0,631 1 1 584) 0,885 1 2,040) 0,999 ') 2,494) 250 о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
