XIV Аттетков и др. Методы оптимизации (1081420), страница 28
Текст из файла (страница 28)
На рис. 4.3 изображены итерации исчерпывающего спуска в случае К~. Так как при использовании наискорейшего спуска значение функции сд(м) = 9 (х . + ню ) в точке ее наименьшего значе- 187 4.3. Метод градиентного спуска ния не превышает величины ) (а ) при исчерпывающем спуске, то неравенство (4.44) будет выполнено и в этом случае, что гарантирует сходимость последовательности (ю 1 к нулю.
ф Нетрудно проверить, что при минимизации функций ~а~ д Е (О, 1), и ~х~з У', й > О, .для которых нарушено условие (4.41), при любом выборе начальной точки исчерпывающий спуск приводит в точку наименьшего значения за одну итерацию. Это указывает на то, что исчерпывающий спуск может дать положительный результат при минимизации тех функций, к которым не применим метод градиентного спуска с ос = сопя$.
Исчерпывающий спуск сходится к стационарной точке т Е Хо функции )(а), непрерывно дифференцируемой на выпуклом множестве й З Хо, если множество Хо = 1 в Е К": Па) ~ У(ж ) ) ограничено. Однако за расширение класса функций по сравнению с рассмотренным в теореме 4.6 приходится расплачиваться заметным усложнением алгоритма, так как теперь на каждой итерации необходимо решать достаточно трудоемкую задачу одномерной оптимизации при поиске точки а и соответствующего значения тсь.
Выполнение условия (4.44) можно обеспечить более простым путем. 1. В точке ж~ ' определяем направление шь = — ягас1 )'(а~ 1) спуска, вычисляем производную (8гас1~(х '), ао ) = — 'уш ~ по этому направлению (если ~аоа( = О, то жь 1 — искомая стационарная точка), полагаем ыь = жо, где чсо > О .. некоторое произвольное значение, одинаковое на всех итерациях, и переходим к п.2. 2. Находим с помощью (4.43) точку ш" = жа '+.нсьаоа, вычисляем значение )'(х") и переходим к п. 3. 3.
Проверяем выполнение неравенства* 1".(а ) < ~(х ' ) — ыа~ао ~ < ~(х ) — ыха~ао ~~, Сыл Пшеничный Б.Н., Данилин Ю.М. 188 4. '1ИСЛЕННЫЕ Ъ|ЕТОДЫ БЕЗУСЛОВНОЙ Л1ИНИМИЗАЦИИ где и Е (О, 1). Если оно не выполнено, то уменьшаем значение хь (например, вдвое) и возвращаемся к п.
2,. а в противном случае на к-й итерации фиксируем использованное в п.2 значение иь и найденную точку ш". Такой способ подбора значения иь получил название метода дробления шаеа. На рис. 4.4 показаны итерации с использованием этого метода в случае плоскости. Рис. 4.4 Несмотря на возможность расширения класса дифференцируемых функций, для которых метод градиентного спуска позволяет искать стационарные точки, оценку скорости сходимости этого метода к точке минимума удается установить лишь для более узкого класса функций. Пусть множество Хе = = (ж Е К": ~(х) < ~(ж~) ) ограничено. Тогда существует стаци- 189 4.3. Метод градиентного спуска онарная точка х'", в которой дифференцируемая функциями(х) достигает наименьшего значения ~(х*) (см.
замечание 4.1). Теорема 4.7. Пусть дифференцируемая в К" функция 1 (х) достигает своего наименьшего зна аения 1(х') в точке х*. Если множество Хо = (х Е К": 1 (х) < Дх~) 1 ограничено и для любой точки х выполнено неравенство ~ягас11(х)~~ > оо(1(х) — 1(х')), (4.46) где оо > О, то для релаксационной последовательности 1х~), построенной при помощи (4.43) и (4.44) и сходящейся к точке х', справедливы оценки где С > О и о Е (О, 1). м Так как при построении последовательности (х ) на каждой й-й итерации выполнено неравенство (4.44), то с учетом (4.46) имеем ~(х ) — 1(х ) >солар.ас11(х )~ >юо~бгас1~(х )~ > > (У( ' ') — У( *)) > (2'( ' ') — У( *)), или ~(хь) - ~(х") < (1 - " .)(йх'-') - ~(х")) Отсюда, выбирая значене по > О так, чтобы д = (1 — севов), получаем первое неравенство в (4.47).
Используя зто неравенство, а также неравенства (4.43), (4.44) и учитывая, что релаксационная последовательность 1х 1 удовлетворяет условию 1(х ) — 1(х ) < 1(х ) — 1(х*), находим Я-! 2 и' а я-1~2 2~ ня12( я-~)р < ь(2( а-1) )( я)) < соа 2 2 < — ~(1(х ) — 1(х*)) < — ~о фх ) — 1(х*)), соо соо 190 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ где хв — наибольшее из значений параметра хя !со значения кв на каждой к-й итерации начинают при необходимости дробление шага спуска). В результате имеем — С 7 С вЂ” Л ~х ' — х '~ < С!д , С! = кв юо Тогда для любого т ) 1с получим т — 1 т — ! !7З игла ~ - — "~<~ ~ ' ' — '~<С,~ у'~'=С,', гг= Ь г=ь 1 — й По условию теоремы последовательность 1хт) сходится к точке х*. Поэтому из последнего неравенства, обозначая С = Сг , приходим при т — ! оо ко второй оценке в (4.47).
!ь 1 — гга ' Отметим, что условию (4.46) удовлетворяет, в частности, сильно выпуклая дифференцируемая функция (см. теорему 3.18). Кроме того, этому условию удовлетворяет любая квадратичная функция с положительно определенной матрицей, поскольку она также является сильно выпуклой функцией (см. пример 3.13). 4.4.
Минимизация квадратичной функции В теории численных методов многомерной оптимизации большое внимание уделено поиску минимума квадратичных функций. Применение численных методов к решению задачи оптимизации, в которой целевая функция является квадратичной, представляет интерес по нескольким причинам. Во-первых, эта задача имеет решение в аналитическом виде (см. 3.6), которое можно использовать в качестве эталона при оценке погрешности численного метода и при сравнении различных методов между собой. Во-вторых, квадратичная функция служит своеобразным испытательным полигоном, 191 4.4. Минимизация квадратичкой функции Г(я) = — фя, я) + (с,. я), я Е Б'.", 1 (4.48) где Я симметрическая матрица порядка п, а с Е 2" заданный вектор.
Пусть Я положительно определенная матрица, на котором можно проверить работоспособность численного метода (если метод малопригоден для минимизации квадратичной функции, то, скорее всего, он будет неработоспособен, когда целевая функция является более сложной). Наконец, при представлении в окрестности некоторой точки произвольной дважды дифференцируемой функции формулой Тейлора можно ограничиться членами второго порядка, т.е. аппроксимировать эту функцию квадратичной. Тогда зада 4у минимизации исходной функции удается свести к последовательности задач для аппроксимирующих квадратичных функций. Такой подход особенно эффективен применительно к функциям, имеющим в окрестности искомой то"пги минимума положителы1о определенную матрицу Гессе и поэтому достаточно хорошо аппроксимируемым сильно выпуклой квадратичной функцией.
Некоторые алгоритмы, разработанные с учетом свойств квадратичных функций, позволяют найти точку минимума за конечное чиьло итераций. Особое место в теории многомерной оптимизации занимают задачи безусловной минимизации выпуклых квадратичных функций двух переменных, или двумерные задачи безусловной минимизации. Изучение идей конструирования вычислительных алгоритмов на примере решения задач двумерной минимизации позволяет наглядно, с помощью геометрических построений на плоскости, представить отличительные черты каждого метода, выявить их вычислительные свойства, обсудить достоинства и недостатки, .а также на основе результатов вычислительного эксперимента получить представление о сравнительных характеристиках различных методов.
В общем случае квадратичная целевая функция имеет вид (см. 1.5) 192 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ имеющая обратную матрицу Я '. Тогда функция Г(я) является сильно еыпуклой и достигает наименьшего значения в точке я' = — Я 1с (см. 3.6)., причем г"(я*) = — (с, Я 1с). Для упрощения выкладок далее будем рассматривать в качестве целевой функции положительно определенную квадратичную форму 1 )'(х) = — (Ях, х). х б 2" (4.49) х = х~+ н1ю~ = х~ — к1Ях~ = (1„— н1Я)х~, (4.50) где 1„единичная матрица порядка и. Из (4.50) можно сделать важный вывод, в значительной степени определяющий стратегию построения эффективных численных методов безусловной минимизации: можно достичь точки х* наименьшего значения квадратичной функции (4.49) за одну итерацию, если ха один из собственных векторов у', 1 = 1,п,, матрицы Я.
Тогда при выборе к1 = 1/Л ., где Л, ) 0 собственное значение этой матрицы, соответствующее собственному вектору уз, из (4.50), согласно определению собственных значений и собственных векторов матрицы [1Ъ'), получим х = [1„— — Я)у~ = — — Яу~ — Л у.) =О =х*. Л ) Л, которую можно получить из (4.48) параллельным переносом прямоугольной системы координат [1Ъ').
Функция (4.49) не- отрицательна при всех х и достигает наименьшего значения 0 в единственной точке х* = О. Для минимизации функции (4.49) используем метод еро; диентноео спуска. Найдем в произвольной начальной точке хе ф х* градиент 8гас1 )'(х ) = ~1х" этой функции и выберем на первой итерации (к = 1) в ка ~естве направления спуска анти- градиент и' = — 8гад~(хо) = — ~хе. Тогда в соответствии с (4.43) для следующей точки получим 4.4.минимизация квадратичной функции 193 В двумерном случае графиком функции 1(х) = — (Цх, х) 2 х~ является эллиптический параболоид, а ее линиями уровня— подобные эллипсы с общим центром (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
