XIV Аттетков и др. Методы оптимизации (1081420), страница 33
Текст из файла (страница 33)
Выше (см. 4.5) показано, что, располагая произвольной системой векторов р' С К"., 1 = 1, и, сопряженных относительно матрицы 11, обратную к ней матрицу 11 ь можно вычислить при помощи соотношения (4.65) Но построение системы сопряженных векторов представляет собой самостоятельнук> и в общем случае достаточно сложную и трудоемкую в вычислительном отношении задачу*.
Особенность алгоритмов метода сопряженных направлений состоит в том, что систему сопряженных векторов строят последовательно в процессе выполнения итераций, причем найденный на очередной, А-й итерации вектор р Е К" определяет на этой итерации направление спуска. Выше (см. 4.5) изложена элементарная процедура постросния системы из двух сопряженных векторов в К, используемых при минимизации квадратичной функции двух переменных. Обобщим эту процедуру применительно к минимизации функции (5.3).
Выберем начальную точку хо е К"', найдем в этой точке антиградиент ш' = — рае11(хв) = — Яхв — с и положим р' = ю'. Ясно, что если ~р ~ у-. О, то вектор р определяет на первой Сми Пшеничный Б.Н., Динилин Ю.М. 221 о52. Метод сопряженных направлений (Й = 1) итерации направление спуска (в противном случае точка хс удовлетворяет необходимому условию минимума, а это в случае функции (5.3) равносильно тому, что хв = х* — единственная точка наименьшего значения этой функции). Считая., что ~р1 ~ ф О, и проводя исчерпывающий спуск, при помощи (4.55) находим значение ! 1)2 ( 1)2 яе ~1 О '1сею1 1) ЯР1; Р1 ) и точку х' = хо + лс1р'. Таким образом, псрвая итерация полностью совпадает с итерацией алгоритма наискорейшего спуска. На второй итерации (й = 2) вычислим антиградиент и12 = = — дгасуДху) = — Яху — с в найденной точке х1. Пусть |ю2~ ~ О, так как в противном случае х1 = х*.
Положим Р = У1Р +и' 2 ! 2 (5.4) и, умножив это равенство скалярно на вектор Ор ф О, запишем (с1Р1,Р2) = (ЯР1,.у1Р1+ю2). Потребуем, чтобы векторы р1 и р2 были сопряженными относительно матрицы ф т.е. чтобы выполнялось равенство 11хУР1, рз) = О. Тогда у1 = = — (сУР1, ю2) У ЯР1, р'). Убедимся, что ~р2( ф О. В самом деле, при ~р2~ = О имеем ю2 = — у1р' и после умножения скалярно на вектор ю2 ф Он приходим к противоречию: 2 2) ~ 22 поскольку при исчерпывающем спуске в соответствии с (4.45) антиградиенты на двух следующих друг эа другом итерациях ортогональны. Вектор р задаст направление спуска из точки х1, так как с учетом (5.4) (рас11(х'), р ) = — (ю~, уур'+юв) = = — у1 (ю ., р ) — (ю, ю ) — — ~ю ~ ( О.
222 и. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ Если в направлении вектора рг провести исчерпывающий спуск, то теперь при нахождении точки хг = х'+ ввгрг для вычисления значения ввг нельзя использовать (4.55), так как в общем случае П ф О и поэтому направление спуска из точки х не совпадает с направлением антиградиента в этой точке. Вычислим в точке х антиградиент ю' = — бгас1Дх ) = — йгх — с = — (,>х' — ввгегр — с= ю — ввгЯР и после умножения скалярно на вектор рг с учетом (4.57) получим (ю ~ Р ) = (ю вега 1Р ) = О, о'гкуда 1юг, Рг) (яугае1Дх1), рг) (5.5) (1~ э г) ~д г Рг) Так как юз — юг = — Яхз — с+ Цх'+ с = — сг1хг — х') = = — ввэр, то с учетом ю =р имеем (ю ю)=(ю ввАР ю)=(ю ю) ввгЯР Р)=О ,й-~-1 ,й + й-~-~ ®Рй юй Н) (м,') ' й -~-! й 1.~ й (Црй~', .р') = О, (юйч1, юв) = О, 1 = 1, й, (5.6) Свь: Виеиллев Ф.П., а также: Биииии М., гПе~ити К.
поскольку при исчерпывающем спуске на первой итерации 1ю~, ю ) =О, а (Яр~, р ) = (евр, р ) = О в силу симметричности матрицы Ц и ф-ортогональности векторов р и р . Следовательно, при исчерпывающем спуске в пространстве Ж", п ) 2, антиградиенты ортогональны на первых трех итерациях. Продолжая описанную процедуру построения сопряженных векторов, с помощью метода математической индукции можно показать*, что на любой й-й итерации при к = 1, и — 1 5.2. МЕтОд Сопряженных напрапяеннй 223 и при этом зев=(ю~,р )/Яр,р ) и х~=х~ ~+тсвр . Таким образом, зта процедура за и итераций позволяет построить систему векторов р' Е Кп, 1 = 1, и, сопряженных относительно матрицы Я и в силу леммы 4.5 линейно независимых.
Анти- градиенты юв = — 8гас1у(хн '), и е И, в соответствии с (5.6) образуют ортогональную систему векторов. Так как в К" не может быть более и ненулевых ортогональных векторов, то один из антиградиентов ю ', Й = 1, и+1, с номером г' должен быть нулевым вектором, т.е. ю' = — 8гадДх' ') = 0„. Поэтому точка х* = х' ' минимума функции ~(х) будет найдена не более чем за и итераций. Пример 5.4. Описанную процедуру построения сопряженных векторов используем для поиска точки х* минимума функции Дхмхв) = бх~~ — 4х~хз+ 34+ 4ъ 5(х~ + 2хз) + 22 двух переменных, рассмотренной в примерах 5.1 и 5.3, приняв в качестве начальной точку хв = ( — 2, 1) .
На рис. 5.5 представлены две ите- О н, =Э7 рации поиска, причем первая из них полностью совпадает с первой р-'=у,р~+тн-' итерацией в примере 5.3, проведенной по методу наискорейшего хе х* спуска. На второй итерации исчерпывающий спуск из точки х = ( — 0,283, — 1,872) в направлении вектора р, сопряженного с вектором р, приводит в искомую точку "=( — '", — 2Д).
У Чтобы использовать метод сопряженных направлений для поиска минимума неквадратичной дифференцируемой функции, предварительно необходимо привести систему (5.6) к виду, не содержащему матрицу Ц. Это можно сделать, если в итерационном процессе х" =х '+яснр , .Й ЕИ, 2~4 л. ывто1дЫ пВВВОвО и втОвОвО пОвядкОв с выбором значения нй > О на каждой й-й итерации путем минимизации функции 'фй(н) =1(ж~ +нр ), н>О, (ю~~',ш') =О,. г=1,й. Такой способ построения сопряженных направлений спуска в литературе получил название метода сопряз1сенных ерадиентов. Используя последнее уравнение (5.6) при г = й, третье уравнение, а также равенство (4.57), числитель и знаменатель второго уравнения (5.6) можно представить в виде 1' й-ь1 й й й!1 й-ы) 1ю ю ю ) ~ йт1р Жй Мй 1юИ-1 ( — ~ ) нй Жй (5.7) Таким образом, вместо второго уравнения (5.6) имеем уй = = ~юй 11~2/ (юй, рй).
Это выражение можно преобразовать, если учесть первое уравнение (5.6), заменив в нем Й на Й вЂ” 1: ( й-~-1)2 ( й-~-1(2 (юй 7 рй — 1 + юй) у (юй рй — 1) + (юй)2 ' Но если и в (4.57) заменить й на к — 1, то получим (ю",. рй 1) = = О. Следовательно, ! й-11(2 Уй= 2, йбМ. (5.8) в основу построения сопряженных направлений р + = 7йр + + ю ~ положить свойство ортогонвльности антиградиентов (а значит, и градиентов) минимизируемой функции 225 от2. Метод сопряженных направлений Если преобразования в первом равенстве (5.7) не доводить до конца, то вместо (5.8) получим ( к<-1, ь ь-11) уй=,, 1сЕК (5.9) В случае дважды дифференцируемой целевой функции можно получить еще одно выражение для уя.
Так как матрица Гессе функции Ях, х) /2+1с, х) совпадает с матрицсй с„, то во втором равенстве (5.6) можно заменить Я матрицей Гессе Н(х~) неквадратичной целевой функции: ф( Ь) И ИД-1) (н1хь)ра ра) (5.10) Теперь с помощью одной из формул (5.8) (5.10) из первого равенства (5.6), записанного в виде р ~ = уьр +тп ' ., ЙЕ1Ч, р =тп, (5.11) фь(лс) =7'(х~ '+лср ), лс>0, йеИ.
(5.12) Это приводит к неизбежным погрешностям на каждой итерации, которые могут вызвать нарушение сходимости алгоритма. Чтобы ослабить влияние погрешностей, используют процедуру на любой а-й итерации можно найти вектор, определяющий направление спуска из точки х на (й+1)-й итерации. Для квадратичной функции результат вычислений по каждой из формул (5.8) (5.10) будет одинаковым, но для неквадратичной функции значения ув будут, вообще говоря, различными. Поэтому использование каждой из этих формул при минимизации неквадратичной функции 7(х) может привести к построению своей системы направлений спуска.
При этом в отличие от квадратичной функции точка минимума в общем случае не будет найдена за конечное число итераций. Более того, при выборе значения лев > 0 на каждой и-й итерации в рекуррентном соотношении хь = х~ + м;,р" приходится минимизировать функцию 226 б. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ „обновления" алгоритма., состояющую в том, что в (5.11) периодически через заданное число итераций полагают чь = О. Соответствующий номер итерации называют моментом обновления алеоритма, или рестартом.
Обычно при минимизации целевой функции в н" множество таких номеров имеет вид Хя = (и, 2п, ..., тп, ...), т Е И Использование в алгоритме рестартов позволяет избежать накопления вычисяительных погрешностей и уменьшить вероятность построения после каждых п итераций линейно зависимых направлений спуска, но приводит к росту общего числа итераций, необходимых для достижения заданной точности поиска.
Опишсм алгоритм минимизации диффсрспцнрусмой нсквадратичной целевой функции Т'(л). Выбираем параметр ез > 0 точности поиска и начальную точку л е н", в которой вычисляем антиградиент и>1 = — 8гас1 Т" (лс). Убедившись, что ~ш1~ > ез, формируем множество Хс моментов обновления алгоритма, полагаем Й = 1, принимаем р = ш и переходим к основной части алгоритма.
1. Минимизируя функцию фь(н) (5.12), находим вяз ~ение хь и точку ж~ = л~ + хьр . В втой точке вычисляем антиградиент ш~+1 = — 8гао 1" 1х") и проверяем выполнение неравенства ~ш + ~ ( сз. Если оно выполнено, то итерации прекращаем и полагаем л' = жь, Т(ж") — Т(ж ). В противном случае переходим к п. 2. 2. Если к Е Хс, то полагаем рвч1 = шь+1, й: = к+ 1 и возвращаемся к п. 1. В противном случае переходим к и.
3. 3. При помощи (5.8) или (5.9) вычисляем значение у~ и, используя (5.11), находим вектор р "1. Полагаем й:= й+1 и возвращаемся к п. 1. Пример 5.5. Используем описанный алгоритм для поиска минимума функции алмаз) = (л1~ — лз) + (л1 — 1), рассмотренной в примере 5.2. Зададим параметр точности поиска ез = 10 з и начальную точку лв = ( — 1, — 2),.в которой 11жс) = = 13. ох 3. Метод Ньютона Результаты вычислений, в которых параметр ую входящий в (5.11), определялся в соответствии с формулой (5.8), приведены в табл. 5А, а аналогичные результаты, в которых параметр ул определялся в соответствии с (5.9), — в табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
