Метод градиентного спуска

Положим в (3.48) на каждом шаге р ^k = -f ¢(x ^k). Если f ¢(x ^k) ¹ 0, то условие (3.36) очевидно выполнено, т.е. направление вектора р ^k явля­ется направлением убывания функции f(х), причем в малой окрестно­сти точки x ^k направление р ^k обеспечивает наискорейшее убывание этой функции. Поэтому можно найти такое a _k > 0, что будет обеспе­чено выполнение условия (3.49).

Приведем алгоритм одного из вариантов метода градиентного спуска.

Шаг 0. Задать параметр точности e > 0, начальный шаг a> 0, подобрать х Î E _n. Вычислить f(х).

Шаг 1. Найти f '(x) и проверить условие достижения точности:

|| f '(x)|| < e. Если оно выполнено, вычисления завершить, полагая х^* = х, f^*=f(х). Иначе — перейти к шагу 2.

Шаг 2. Найти y=x-a f '(x) и f(у). Если f(у) < f(х), то положить x =у, f(х) = f(у) и перейти к шагу 1, иначе — перейти к шагу 3.

Шаг 3. Положить a=a/2 и перейти к шагу 2.

Замечание. Вблизи стационарной точки функции f (x) величина || f '(x)|| становится малой. Это может приводить к замедлению сходимости последовательности {х ^k }. Поэтому иногда в (3.48) полагают p ^k = - f '(x ^k)/ || f ' (x ^k)||, т.е. вместо - f '(x ^k) используют вектор единичной длины того же направления.

Приведем теоретическое обоснование сходимости градиентного метода с постоянным шагом a _k º a;

x ^{k+ 1}= x ^k -a f '(x ^k) (3.50)

и получим оценку скорости сходимости при минимизации выпуклой вадратичной функции f(х)= <Ах, х>+<b, x >+ с.

Теорема 3.10. Пусть симметрическaя мaтрицa A квaдрaтичной функции f(х) положительно определенa, l и L — ее нaимень­шее и нaибольшее собственные знaчения (0 < l £ L). Тогдa при любых a Î (0; 2/L) и х⁰ Î E_n итерaционнaя последовaтельность (3.50) сходится к единственной точке глобaльного минимумa функции f(х) линейно (со скоростью геометрической прогресcии (см. рaзд. 3.4)):

||(x ^k – x^*)|| £ q ^k ||(x⁰ – x^*)||, (3.51)

где q = max {|1 - a l |, |1 - a L |}.

Так как матрица A положительно определена, функция f(х) cильно выпукла и, следовательно, точка х^* существует и единственна. Градиент f '(x) в этой точке обращается в нуль, т.е. f ' (x^*) = А x^*+b=0. Для точки х ^k имеем: f ' (x ^k) = Аx ^k +b= Аx ^k +b - А x^*- b = А(x ^k -x^*). Оценим норму разности

||(x ^k - x^*)|| = ||x ^k - af'(x ^k-1) - x^*|| = ||x ^k-1 - x^* - a A (x ^k-1 - x^*)|| = || (E - a A)(x ^k-1 - x^*)||.

По свойству норм (3,6) имеем:

||x ^k - x^*|| £ || E - a A ||×||x ^k-1 - x^*||. (3.52)

Оценка сверху для нормы матрицы (3,7) дает:

|| E - a A || £ q = max { |1- a l |, |1- aL| }. (3.53)

Зависимость q(a) представлена на рис. 3.14, из которого видно, что при a Î(0; 2/ L ) величина q < 1. Кроме того, из неравенств (3.51) и (3.53) получаем: ||x ^k - x^*|| £ q ||x ^k-1 - x^*||, т.е. ||x ^k - x^*|| £ q ^k ||x⁰ - x^*||.

Из рис. 3.14 видно, что вели­чина q принимает минимальное значение q^*=(L - l)/(L + l) при a =a^* =2/(L + l). Поэтому от соотношения между L и l суще­ственно зависит число итераций градиентного метода при мини­мизации выпуклой квадратичной функции. Проиллюстрируем это на примере квадратичной функ­ции двух переменных.

При L = l > 0 точка минимума f(х) находится за один шаг.

Пример 3.9. Решить задачу f(x) =x²₁ +х²₂ ® min градиентным методом из начальной точки х⁰ = (1,1), положив a =a^*.

В данном случае матрица A квадратичной функции . Очевидно, l = L = 2. Поэтому a^* = 2/(L + l) = 1/2 и х¹ = х⁰ - f '(х⁰) = (0,0). Легко проверить, что х⁰ = х¹.

При l = L линии уровня целевой функции f(x) — это концентриче­ские окружности, поэтому направление антиградиента указывает на центр этих окружностей, т.е. на точку глобального минимума f(х).

Если L >> l > 0, то линиями уровня являются эллипсы, полуоси ко­торых сильно различаются. Поэтому направление антиградиента в не­которой точке может сильно отличаться от направления к точке гло­бального минимума.

Пример 3.10. Из начальной точки х⁰=(1, 1) выполнить несколько итераций поиска точки минимума функции f(х) = x²₁ + 100х²₂ градиентным методом, полагая a =a^*.

Собственные значения матрицы A этой квадратичной функции равны: l = 2, L = 200. Линиями уровня f (x) являются эллипсы, сильно вытянутые вдоль oси Ox ₁. Поэтому в точке х⁰ направление вектора антиградиента – f ' (х⁰) = (- 2, - 200) сильно отличается от направления к точке глобального минимума х^*-х⁰ = (-1,-1). Положив в формуле (3.50) a =a^*2/(l+ L)=1/101, получим с учетом выражения для градиента f '(x)=(2x₁, 200x₂) следующий закон изменения координат точек минимизирующей последовательности: x₁ ^{k +1} = x ^k ₁×99/101; x₂ ^{k +1}= -x₂ ^k ×99/101. Отсюда видно, что последовательность {х ^k } сходится к точке глобального минимума медленно и траектория сходимости имеет ярко выраженный зигзагообразный характер.

В курсе линейной алгебры для симметрической положительно оп­ределенной матрицы вводится число обусловленности матрицы m = L /l — отношение наибольшего к наименьшему собственному значению. В задаче минимизации произвольной (не обязательно квадра­тичной) сильно выпуклой функции f(х) эта величина для матрицы ее вторых производных (гессиана) характеризует степень вытянутости линий (поверхностей) уровня f(х)=с. Очевидно, что всегда m ³ 1. Если m велико, то линии (поверхности) уровня сильно вытянуты и говорят, то функция имеет овражный характер, т.е. резко меняется по одним управлениям и слабо — по другим, В подобных случаях задачу минимизации называют плохо обусловленной (см. пример 3.10). Если же m близко к единице, то линии (поверхности) уровня близки к окружностям (сферам) и задача минимизации является хорошо обусловлен­ной (см. пример 3.9).