Лекция: МЕТОД ГРАДИЕНТНОГО СПУСКА

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

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

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

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

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

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

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

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

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

xk+1= xk-af '(xk) (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) и х0Î En итерaционнaя последовaтельность (3.50) сходится к единственной точке глобaльного минимумa функции f(х) линейно (со скоростью геометрической прогресcии (см. рaзд. 3.4)):

||(xk – x*)|| £ qk ||(x0– x*)||, (3.51)

где q= max {|1 — al|, |1 — aL|}.

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

||(xk — x*)|| = ||xk — af'(xk-1) — x*|| = ||xk-1 — x* — aA(xk-1 — x* )|| = || (E — aA)(xk-1 — x* )||.

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

||xk — x*|| £ ||E — aA||×||xk-1 — x*||. (3.52)

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

||E — aA|| £ q = max { |1- al|, |1- aL| }. (3.53)

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

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

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

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

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

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

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

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

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

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