XIV Аттетков и др. Методы оптимизации (1081420), страница 32
Текст из файла (страница 32)
В противном случае переходим к п. 2. 2. Определяем точку хк = хв 1+ зсйиса и значение Т"(хк) целевой функции в этой точке. Если неравенство (5.1) (со = 1сс2) выполнено, то полагаем* зсь = зсо, .Й: = Й+ 1 и возвращаемся к п. 1. В противном случае переходим к п. 3. 3. Полагаем зсь: = пзсь и возвращаемся к п. 2. "Здесь и далее при описании азгоритмов используем символ присваивания:=, который указывает, что значение величины в правой части формулы нужно присвоить величине, записанной слева от него. Например, запись Й: = Й -с 1 означает увеличение номера итерации на единицу.
213 бп. Алгоритыы ыетода градиентного гнусна Пример 5.1. При помощи описанного алгоритма найдем решение задачи безусловной минимизации функции ~(хмх2) = = бх1~ — 4х1хз+Зхз~+4ъ~5(хз+2хо) +22 (см. пример 3.18). Выберем начальную точку хо = ( — 2., 1), при этом 1(хс) = 57. Кроме того, фиксируем ез = 0,01, аго = 0,1 и и = 0,5. Воспользуемся тем, что функция квадратичная и имеет положительно определенную матрицу с собственными значениями Л1 = 4 и Л„= 14. Поэтому выбранное значение хо = 0,1 Е (О, 2/Лз) обеспечивает (сильную) сходимость метода градиентного спуска с постоянным па всех итерациях значением ага = = тго (см.
4.4). При этом в соответствии с (4.53) справедлива оценка )х — х )<( — ) )х — х'(, ЙЕИ, 12 и последовательность 1х ) сходится к искомой точке х' ЕК со скоростью геометрической прогрессии, Рис. 5.1 имеющей знаменатель д = 5/12. На рис.
5.1 представлена траектория поиска точки х* = = ( — Л, — 2Л) минимума этой функции, а в табл. 5.1 приведены результаты вычислений (отмстим, что ~/5 — 2,2361 с точностью 5-10 а). Характерной особенностью процесса поиска в данном случае является то, что на первых итераниях спуск в направлении антиградиента приводит к существенному убыванию значения минимизируемой функции по сравнению с ее значением в начальной точке х". Затем темп убывания значений функции замедляется.
Эта особенность, уже отмеченная ранее (см. 4.3), снижает эффективность используемого алгоритма на завершающей стадии поиска (для выполнения условия ~юа~ < ез потребовалось 15 итераций). ф 214 5. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ Таблица 5.1 Х(х") ~8 1У( ')~ Рассмотрим еще один пример реализации описанного алгоритма, иллк>стрирующий влияние выбранного значения Р Е Е (О, 1) коэффициента дробления шага на количество итераций, обеспечивающих достижение заданной точности поиска точки х* минимума целевой функции Т(х). Пример 5.2. Рассмотрим задачу минимизации функции ~(хмара) = (х21 — хз) + (х1 — 1), выбрав начальную точку х~ = = ( — 1, — 2), в которой Т" (хо) = 13, и параметры ез = 10 з, лая = 1. Результаты поиска точки минимума х* = (1, 1) рассматриваемой функции при различных значениях коэффициента дробления шага и е (О, 1) (приближенное значение точки минимума, значение функции в этой точке и количество итераций Х) приведены в табл.
5.2. Траектории поиска точки минимума в 0 1 2 3 4 6 7 8 9 10 11 12 13 14 Рй 16 ( — 2,000, 1,.000) ( — 1,047, — 0,594) ( — 0,923, — 2,446) ( — 1,688, — 3,136) ( — 1,811, — 3,719) ( — 2,020, — 4,001) ( — 2,091, — 4,197) ( — 2.,155, — 4,304) ( — 2,185, — 4,372) ( — 2,206, — 4,412) ( — 2.,218, — 4,436) ( — 2,225, -4,450) ( — 2,230, — 4,459) ( — 2,232, — 4,464) ( — 2,234., — 4,467) (-2,235, — 4,469) ( — 2,.235, — 4,470) 57,000 7,150 — 15,976 -23,772 — 26,494 — 27,460 — 27,806 — 27,930 — 27,975 — 27,991 — 27,997 — 27,999 — 28,000 — 28,000 — 28,000 — 28,000 — 28,000 37,148 18 553 10,309 5 953 3,508 2,087 1,248 0,747 0,448 0,269 0,1Я 0,097 0,058 0,035 0.,021 0,013 0,008 215 Ы.
Алгоритмы негода градиентного спуска Таблииа 5.8 каждом варианте показаны на рис. 5.2 и 5.3 (в табл. 5.2 даны ссылки на соответствующий каждой траектории рисунок). Из результатов поиска видно., что значение и существенно влияет на необходимое количество итераций, обеспечивающих поиск точки ж* минимума рассматриваемой функции с заданной точностью. Наименьшее количество итераций соответствует выбору значения и на отрезке ~О,ог., 0,8]. Рис.
5.2 217 йй. Алгоритыы метала градиентного спуска Отметим, что на практике значение тгя на и-й итерации выбирают так, чтобы выполнялось неравенство 7'(х~ 1) — )'(х") > > О. Это равносильно выполнению неравенства (5.1) при ш = О. На рис. 5.3, г показан именно этот вариант алгоритма градиентного спуска при ггв = 1 и о = 0,5. уЕ Эффективность алгоритма, использующего спуск в направлении антиградиента, можно несколько повысить., если значение тгь на каждой Й-й итерации выбирать путем минимизации функции фи(м) = У(хй 1 + тгьов), тг > О, (5.2) т.е. применить метод наискорейшего спуска. Напомним, что для строго выпуклой функции ~(х) это равносильно процедуре исчерпывающего спуска, но в общем случае значение и, соответствующее наименьшему значению функции фе(тг), не совпадает со значением, получаемым при помощи исчерпывающего спуска (см.
замечание 4.2). Отметим, что поиск минимума функции фь(тг) может оказаться довольно трудоемкой самостоятельной задачей, требующей применения методов одномерной минимизации (см. 2), но для сильно выпуклой квадратичной целевой фйнкиии значение лгь определено однозначно формулой (4.55). Выбор значения тгь как при помощи исчерпывающего спуска, так и методом наискорейшего спуска гарантирует сходимость последовательности (юь) к нулю (см. замечание 4.3). Поэтому в качестве условия прекращения итераций и при этом варианте выбора значения тгь целесообразно использовать неравенство ~ш~~ ( ез.
Опишем алгоритм наискорейшего спуска в случао произвольной дифференцируемой целевой функции ~(х), х Е Б'.". Предварительно выберем начальную точку хв и параметр точности поиска ез, положим Й = 1 и перейдем к основной части алгоритма. 1. В точке хь 1, найденной на (Й вЂ” 1)-й итерации (в точке хв на первой итерации), находим значение ~(х ) целевой функ- 218 б.
МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ ции и ее антиградиент ы~ = — 8та01(.в~ 1). При выполнении неравенства ~ш ~ ( ез дальнейшие итерации прекращаем и полагаем щ* — а ~, Т ( в*) — Т (ть 1) . В противном случае переходим к п.2. 2. Минимизируя функцию фь(ж) (5.2), находим значение хь и точку ж = х +чьи~", полагаем Й:= 1+1 и возвращаемся к п.1. Пример 5.3. Применим рассмотренный алгоритм к поиску минимума той же квадратичной функции, что и в примере 5.1, приняв ше = ( — 2, 1) и ез = 0,01.
Так как эта функция явля- ется сильно выпуклой (см. прио мер 3.18), то значения чь выби- раем в соответствии с (4.55). В О х табл. 5.3 приведены результаты Ф вычислений, а на рис. 5.4 иллюз стрируется процесс поиска точки ж* = ( — А/5, -2Я) минимума этой функции и выполнение условия (4.45) ортогональности направлений спуска на двух следующих друг за другом итерациях. При том же значении ез = 0,01 Рис. 5.4 параметра точности для завершения вычислений в данном примере потребовалось на две итерации меньше, чем в примере 5.1. 1Р Примеры 5.1 и 5.3 показывают, что алгоритм метода наискорейшего спуска в случае квадратичной функции не дает заметного выигрыша по количеству итераций по сравнению с алгоритмом, использующим метод дробления шага.
Минимизация же неквадратичной функции при сопоставимом количестве итераций, необходимых для достижения заданной точности при помощи этих алгоритмов, может потребовать существенно большего общего объема вычислений по методу наискорейшего 219 5.2.
Метод сопряженных направлений Таблица ос.З (6гас17(.в )( спуска вследствие поиска на каждой итерации минимума функции фа(н) (5.2). Поэтому необходимое количество итераций еще не является критерием эффективности того или иного алгоритма. 5.2. Метод сопряженных направлений Среди методов первого порядка поиска минимума целевой функции 1(х), х Е К", особое место занимает метод сопряэсенных направлений, основанный на свойствах век; споров, сопряженных относительно некоторой квадратной матрицы (см. 4.5).
Этот метод по сравнению с методом наискорейшего спуска требует, как правило, заметно меньшего количества итераций для достижения той же точности поиска при сопоставимом объеме вычислений на каждой итерации. Различие в способах построения системы сопряженных векторов, 0 1 2 3 4 5 6 7 8 10 11 12 13 (-2,000, 1,000) ( — 0,283, — 1,872) ( — 2,173, — 3,001) (-1,711, — 3.,773) ( — 2,219, — 4,077) (-2,095, -4,284) ( — 2,231, — 4,366) ( — 2,198, — 4,422) ( — 2,235, — 4,444) (-2,226, -4.,459) ( — 2,236, — 4,464) ( — 2,233, — 4,468) ( — 2,236, — 4,470) ( — 2,235, — 4,471) 57,000 — ' Р54 — 21.,860 -26.,350 — 27,556 — 27,881 — 27,968 — 27,991 — 27,998 — 27.,999 — 28,000 — 28,000 — 28,000 — 28,000 0,090 0,145 0,090 0,145 0,090 0,145 0,090 0,145 0,090 0,145 0,.090 0,145 0,090 37,.148 15,182 9,.985 4,081 2.,684 1,097 0,721 0,295 0,194 0,079 0,052 0,021 0,.014 0,006 220 оч МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ определяющих сопряженные поправ,ления спускоч порождает несколько алгоритмов метода сопряженных направлений.
Сначала рассмотрим алгоритм, предназначенный для поиска точки х* минимума сильно выпуклой на выпуклоле множестве К" квадратичной функции вида (3.37) 1 1'(х) = — (чих, х) + (с, х), х Е К", (5.3) где (з — положительно определенная матрица порядка п, а с Е К" заданный вектор. Напомним, что эта функция имеет единственную точку х* = — б1 с, в которой она достигает наименьшего значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
