XIV Аттетков и др. Методы оптимизации (1081420), страница 29
Текст из файла (страница 29)
4.5). Метод гради- О 1 ентного спуска в этом случае может привести в точку (О, 0) наименьшего значения за одну итерацию лишь при выборе на- Рис. 4.5 чальной точки на одной из осей эллипсов: в этом случае радиус-вектор точки является собственным вектором положительно определенной матрицы Ц второго порядка. При одинаковых зна ~ениях собственных значений матрицы Я графиком функции 1'(х) будет параболоид вращения, а линиями уровня этой функции окружности.
Здесь радиус-вектор любой точки хв у'= х* является собственным, а точка наименьшего значения достигается за одну итерацию при любом выборе начальной точки хв. Последняя геометрическая иллюстрация подсказывает, казалось бы, простой с теоретической точки зрения путь повышения эффективности метода градиентного спуска в случае произвольной положительно определенной матрицы (4.
Для этого сначала поворотом системы координат квадратичную форму (4.49) нужно привести к каноническому виду, а затем изменением масштабов по осям новой системы координат, базисом которой будет система собственных векторов матрицы Я, обеспечить равенство всех диагональных элементов преобразованной матрицы. После ортогонального преобразования функция (4.49) в новой системе координат с осями ОС., у = 1, н, примет вид 194 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ а после изменения масштабов путем замены с =,„/Л ~, т' =1, и, получим в 12(0 ~Х~ ~2 ~ ь — (~1~ ~ ~п)~ 1=1 т.е. квадратичную форму 22(~) = (2 1„1,) с единичной матрицей 1„порядка п.
Минимизация функции 12(~) методом градиентного спуска реализуется за один шаг (и = 1), но это упрощение не оправдывает большой трудоемкости решения задачи на собственные зна тения матрицы 0 (особенно в случае достаточно высокого порядка и). Тем не менее такой прием полезно использовать, если график исходной квадратичной функции имеет так называемую овраэ1сную стпрунтпуру, когда убывание функции по одному или нескольким направлениям существенно больше, чем по остальным. В двумерном случае график такой функции в окрестности точки минимума напоминает овраг с крутыми склонами и пологим дном, а линии уровня оказываются сильно вытянутыми (рис.
4.6). В этом случае преобразование, состоящее в изменении масштабов переменных и называемое мастатпабированисм, превращает график минимизируемой квадратичной функции двух переменных в параболоид вращения, а линии уровня в окружности. Рис. 4.6 195 4.4. Минимизация квадратичной функции :в =ж +тс4в =а — ирао4(в ) = ' — иО~" ' = (4п — втО)а ', Й Е Ы (4.51) Последовательность (х~1 будет сходиться к точке х' = О, .если линейный оператор у = (1„— атС1)а является сжимаюп1им отаображением, для чего достаточно выполнения неравенства ~~1„— асф~ = д(вт) < 1. Это условие зависит от выбора нормы линейного оператора (нормы матрицы).
В К" часто используют спектральную норму матрицы. Для этой нормы имеем [1Ч) ~!1„— ата = шах(11 — втЛ1~, ~1 — втЛ„4) = Ч(вт), где Лм ˄— — наименьшее и наибольшее собственные значения матрицы б1 соответственно. Таким образом., при выборе значения вт нужно обеспечить одновременное выполнение неравенств )1 — иЛ1! < 1 и (1 — втЛ„) < < 1. Ксли выбрать ж Е (О., 2/Лп) в соответствии со вторым неравенством, то первое неравенство также будет выполнено, поскольку О < Л1 < Лп. Для сжимающего отображения верна оценка )жа — х*) < 14~уса —,и'( ~ц. Поэтому для уменьшения количе- чЮ ства итераций, обеспечивающих 1 заданную точность, желательно выбрать значение и так, чтобы знаменатель с4(вт) геометрической прогрессии был наименьшим.
На рис. 4.7 показаны зависимости !1 — атЛ1), )1 — атЛ„! и,1 ',1 1, а(вт) от и при Л1 < Л„. Ясно, что наименыпее значение у(ас) соот- Рис. 4.7 Вернемся к случаю поиска минимума квадратичной функ- 1 ции 1 (ж) = — (ь4ж, а) с произвольным выбором начальной точки 2 и используем вариант метода градиентного спуска с постоянным значением ать = вт = сопв1 на всех итерациях. Тогда в соответствии с (4.40) на й-й итерации получим 196 4.
численные метОДы БезУслОВнОЙ минимизлЦии Л„, - Л, с(О) -1 =«е+ ' (4. 52) где сЯ) = Л„/Л1 — — число обусловленности ми1п11ицы Ц. Для единичной матрицы 1и все собственные значения одинаковы и равны единице, так что с(1и) = 1 и д, = О. Это говорит о том, что, как уже было отмечено, точка х* достигается за одну итерацию при лк1бом выборе начальной точки хв. Если же Я плохо обусловлена, т.е. сЯ)» 1, то значение е1„мало отличается от единицы и поэтому последовательность 1х"1 сходится медленно.
Покажем, что оценку )х~ — х*) < дь)х — х*( = ( " ) (х~ — х*(, й Е И, (4.53) Ли+ Л1 нельзя улучшить. Для этого достаточно привести пример, в котором эта оценка окажется точной. Положим хо = х'+у +у", где у1 и р" -- единичные собственные векторы матрицы Я, отвечающие собственным значениям Л1 и Л„. Тогда с учетом 14.51) имеем хв — х' = (1„— хЯНх~ ' — х*), откуда, используя свойства собственных векторов ~111), получаем е ~ ц О)1'( О ~) ц д)Й1 1+ и) = 11 — нЛ1) у +(1 — нЛ„)~р".
Следовательно, о *р /х~ — х'!~ = ((1 — нЛ1)~~+ 11 — мЛ„)~~), (4,54) 2 поскольку с учетом ортонормированности собственных векторов ~хв — х*(2 = ~р'+у" ~2 =2. Правая часть соотношения (4.54) ветствует равенству )1 — хЛ1( = (1 — хЛ ), из которого при Л1 < Л„заклк1чаем, что 1 — нЛ1 = — 11 — нЛ„). В результате 2 2 приходим к оптимальным значениям н, = < — и л +л„л„ 197 4ив Миниыивация квадратичной функции при и=и„= принимает значение дзь~жо — а ~з что при- 2 2к О *з -~- Л водит к точному равенству в (4.53). На рис.
4.8 приведена графическая иллюстрация процесса сходимости метода градиентного спуска в плоскости к точке минимума ж* = О для квадратичной функции 7'(ж) = х~~+ + 10хз ~при использовании (4.51) и различных значениях яя на рис. 4.8, а и= 0,01, на рис. 4.8, 5 тс= 0,09. Рис. 4.8 Отметим, что собственные значения для соответствующей квадратичной формы Яж, а) = т1~+ 10яз зравны Л1 = 2 и Лз = 20. Поэтому условием сходимости метода градиентного спуска с постоянным значением яс = сопвс является выбор дт Е (О, 2/Лз) = = (О, 0,1).
Если тс ) 0,1, то последовательность ~ю") не является релаксационной. При использовании (4.51) это приводит к расходимости метода или к его „зацикливанию". 11а рис. 4.9 представлена графическая иллюстрация этих ситуаций; а „зацикливание" при х = 0,10 и б — — расходимость при и = 0.,11. Рис. 4.9 198 4. численные Е4етОЛы БезУслОВИОЙ минимизАЦии Для пояснения полученных результатов подробнее рассмотрим первые три итерации, выполненные в соответствии с (4.51) и с выбором на 4альной точки хе = (1, 2): 40 ' 2 — 40х 2 — 4х 2 1 2 1 — 4х+4х 2 40 — 800х ' 2 — 80х+ 800хз з 2 — 8х+ 8х2 20 — 1600х+ 16000х~ 1 — бх+ 12х — 8х' з з 2 — 120х+ 2400хз — 16000хз Отстода при х = 0,10 получаем 0,8 2 0.,64 з 0512 т.е.
для й = 1,2, 3 имеем ~х~~~ = 2 --. эффект,.зацикливания" метода. При х = 0,11 находим — 2,3636 ' 2,7934 — 3,3013 Д~') = 56,479 < Д~з) = 78,404 < Д~з) = 109,213, что свидетельствует о тенденции к расходимости метода. На- конец, при х = 0,09 имеем -1,6364 ' 1,3388 -1,0954 1(х') = 27,446 > Дх~) =18.373 > 1"(хз) = 12,299, т.е.
можно ожидать, что последовательность 1х ) является релаксационной, .а метод градиентного спуска сходится. 199 4.6. Сопряясеиные напранленил спуска Рис. 4.10 Отметим, что применение исчерпывающего спуска при минимизации рассматриваемой функции приводит к аналогичным результатам (рис. 4.10). Покажем, что в общем случае целевой 1 функции Дх) = — 1сгх, х), х Е 1~", метод наискорейшего спуска на каждой й-й итерации и исчерпывающий спуск эквивалентны, т.е. точка х при спуске из произвольной точки х~ 1 ф О по направлению антиградиента ао~ = — 9гас1~(х~ 1) = — Ях~ у= О„ будет одна и та же.
Для доказательства этого сначала вычислим градиент функции в точке х = х + асею: ргас11 (х~) = ~хь = ~1хь ~ + хЯаоь = — аоу+ аеЯяоь. Умножим это равенство скалярно на вектор ю" и учтем условие (4.45) исчерпыва1ощего спуска. В результате получим (9гаЬ ~(х~), ш~) = — (ю~, аоа) + асаЯло~, ш~) = О. Отсюда находим единственное значение (аоа а) ~ я~а ась = ' = „, ЙЕИ. (4.55) 4.5. Сопряженные направления спуска Продолжим рассмотрение методов минимизации на примере квадратичной формы (4.49).
Обратимся к более общему рекуррентному соотношению (4.20), записав его в виде х~ =х~ '+асар, ЙЕИ, (4.50) 200 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ где ня > О, к Е И; р Е К" -- вектор, определяющий направление сиуска на й-й итерации; нь(р~( — щаг спуска. Пусть снова выбрана произвольная начальная точка х С ж",. в которой для функции (4.49) имеем аннгиерадиент го = — Егас1~(х ) = — Ох~. Для первой итерации (1е = 1) в соответствии с (4.56) запишем х1 = хо + н1р1. Отсюда видно, что точки х* = 0 минимума квадратичной формы (4.49) можно достичь из произвольной точки хо за одну итерацию (т.е. х1 = х*). если выбрать н1р' = = — х" = Я 1го'.
При этом направление спуска, вообще говоря, не совпадает с направлением антиградиента (совпадение имеет место, например, в случае единичной матрицы Ц). 1 Отметим, что для функции 1(х) = — (Ях, х) матрица Гессе Н постоянна и совпадает с матрицей С4. Поэтому при н1р го = — Я цгаг1~(х ) можно написать х' = х + игр' = х" + Я 'го' = х" — Н ' ига<1 Т" 1х ). Это равенство представляет собой запись первой итерации метода Ньютона решения системы уравнений ягад ~(х) = О, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
