Градиентные методы
1. Общие соображения и определения.
Наиболее распространенные и эффективные методы приближенного решения задачи безусловной оптимизации
f(x) ® min,
(1)
где f: Rm ® R, укладываются в следующую грубую схему. Начиная с некоторого x0 Î Rm, строится последовательность {xn} Ì Rm такая, что
f(xn+1) < f(xn)
(2)
при всех n Î N. Такие последовательности иногда называют релаксационными, а методы построения релаксационных последовательностей — итерационными методами или методами спуска. Последовательность, удовлетворяющую (2), строят в надежде, что уменьшая на каждом шаге (переходе от xn к xn+1) значение функции, мы приближаемся к минимуму (по крайней мере, локальному).
Мы будем говорить, что метод, начиная с данного x0 Î Rm,
а) условно сходится, если последовательность {xn} релаксационна и
f ¢(xn) ® Q при n ® ¥;
б) сходится, если
xn ® x* = argmin f(x) при n ® ¥;
в) линейно сходится (или сходится со скоростью геометрической прогрессии, или имеет первый порядок сходимости), если при некоторых C > 0 и q Î [0, 1)
||xn - x*|| £ Cqn;
(3)
г) сверхлинейно сходится, если для любого q Î (0, 1) и некоторого (зависящего от q) C выполнено неравенство (3);
д) квадратично сходится (или имеет второй порядок сходимости), если при некоторых C > 0 и q Î [0, 1) и всех n Î N
||xn - x*|| £ Cq2n.
Если эти свойства выполняются только для x0 достаточно близких к x*, то как всегда добавляется эпитет "локально".
2. Эвристические соображения, приводящие к градиентным методам.
Выше уже отмечалось, что если x не является точкой локального минимума функции f, то двигаясь из x в направлении, противоположном градиенту (еще говорят, в направлении антиградиента), мы можем локально уменьшить значение функции. Этот факт позволяет надеяться, что последовательность {xn}, рекуррентно определяемая формулой
xn+1 = xn - af ¢(xn),
(4)
где a - некоторое положительное число, будет релаксационной.
К этой же формуле приводит и следующее рассуждение. Пусть у нас есть некоторое приближение xn. Заменим в шаре B(xn, e) с центром в точке xn функцию f ее линейным (вернее, афинным) приближением:
f(x) » j(x) =(def) f(xn) + (f ¢(xn), x - xn)
(функция j аппроксимирует f в окрестности точки xn с точностью o(x - xn)). Разумеется, (линейная) безусловная задача j(x) ® min неразрешима, если f ¢(xn) ¹ Q (см. задачу 1.3). В окрестности же B(xn, e) функция j имеет точку минимума. Эту точку естественно взять за следующее приближение xn+1.
3. Градиентный метод с постоянным шагом.
В общем случае число a в формуле (4) может на каждом шаге (т. е. для каждого n) выбираться заново:
xn+1 = xn - anf ¢(xn).
(5)
Именно методы, задаваемые формулой (5), называются градентными. Если an = a при всех n, то получающийся метод называется градиентным методом с постоянным шагом (с шагом a.)
Поясним геометрическую суть градиентного метода. Для этого мы выберем способ изображения функции с помощью линий уровня. Линией уровня функции f (изолинией) называется любое множество вида {x Î Rm: f(x) = c}. Каждому значению c отвечает своя линия уровня (см. рис. 5).
Рис. 5.
З а д а ч а 3.4. Докажите, что касательная к линии уровня функции f: R2 ® R ортогональна к градиенту. Как обобщить это утверждение на многомерный случай?
Геометрическая интерпретация градиентного метода с постоянным шагом изображена на рис. 6. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в a раз".
Рис. 6.
4. Один пример исследования сходимости.
Изучим сходимость градиентного метода с постоянным шагом на примере функции
f(x) = |x|p,
где p > 1 (случай p £ 1 мы не рассматриваем, поскольку тогда функция f не будет гладкой, а мы такой случай не исследуем). Очевидно, задача (1) с такой функцией f имеет единственное решение x* = 0. Для этой функции приближения xn градиентного метода имеют вид:
xn+1 = xn - ap|xn|p-1sign xn.
(6)
Пределом этой последовательности может быть только 0. Действительно, если x** = limn®¥ xn ¹ 0, то, переходя к пределу в (6) при n ® ¥, получаем противоречащее предположению x** ¹ 0 равенство
x** = x** - ap|x**|p-1sign x**,
откуда x** = 0. Очевидно также, что если x0 = 0, то и xn = 0 при всех n.
Покажем, что если p < 2, то при любом шаге a > 0 и любом начальном приближении x0 (за исключением не более чем счетного числа точек) приближения (6) не являются сходящимися. Для этого заметим, что если 0 < |xn| < (2/ap)1/2(2-p), то
|xn+1| > |xn|.
(7)
Поэтому, если xn не обращается в нуль, то она не может сходиться к нулю и, следовательно, не может сходиться вообще.
З а д а ч а 3.5. Докажите.
Таким образом, осталось доказать (7). В силу (6)
|xn+1| = |xn - ap|xn|p-1 ·sign xn| = |xn|·| 1 -ap|xn|p-2·sign xn|.
Остается заметить, что если 0 < |xn| < (2/ap)1/(2-p), то, как нетрудно видеть, |1 - ap|xn|p-2·sign xn| > 1, что и требовалось.
5. Теорема об условной сходимости градиентного метода с постоянным шагом.
Пусть в задаче (1) функция f ограничена снизу, непрерывно дифференцируема и, более того, f ¢ удовлетворяет условию Липшица:
||f ¢(x) - f ¢(y)|| £ L ||x - y|| при всех x, y Î Rm.
Тогда при a Î (0, 2/L) градиентный метод с постоянным шагом условно сходится.
Д о к а з а т е л ь с т в о. Положим zn = -af ¢(xn) и обозначим f(xn + tzn) через j(t). Тогда, как легко видеть,
j¢(t) = (f ¢(xn + tzn), zn)
и поэтому по формуле Ньютона — Лейбница для функции j
f(xn+1) - f(xn) = f(xn + zn) - f(xn) = j(1) - j(0) =
=
ò
1
0
j¢(s) ds =
ò
1
0
(f ¢(xn+ szn), zn) ds.
Добавив и отняв (f ¢(xn), zn) = ò01(f ¢(xn), zn) dsи воспользовавшись неравенством (x, y) £ ||x|| · ||y||, получим
f(xn+1) - f(xn) = (f ¢(xn), zn) +
ò
1
0
(f ¢(xn + szn) - f ¢(xn), zn) ds £
£ (f ¢(xn), -af ¢(xn)) +
ò
1
0
||f ¢(xn + szn) - f ¢(xn)|| · ||zn|| ds.
Учитывая условие Липшица для f ¢, эту цепочку можно продолжить:
f(xn+1) - f(xn) £ -a||f ¢(xn)||2 + L ||zn||2
ò
1
0
s ds =
= - a||f ¢(xn)||2 +
La2
2
||f ¢(xn)||2 = -a||f ¢(xn)||2
æ
è
1 -
La
2
ö
ø
.
(8)
Поскольку 1 - La/2 > 0, последовательность {f(xn)} не возрастает и, следовательно, релаксационность {xn} доказана. А так как в силу условий теоремы f еще и ограничена снизу, последовательность {f(xn)} сходится. Поэтому, в частности, f(xn+1) - f(xn) ® 0 при n ® ¥. Отсюда и из (8) получаем
||f ¢(xn)||2 £ a-1
æ
è
1 –
La
2
ö
ø
–1
[f(xn) - f(xn+1)] ® 0 при n ® ¥.
6. Теорема о линейной сходимости градиентного метода с постоянным шагом.
Пусть выполнены условия теоремы 3.5 и, кроме того, f дважды непрерывно дифференцируема и сильно выпукла с константой l. Тогда при a Î (0, 2/L) градиентный метод с шагом a сходится со скоростью геометрической прогрессии со знаменателем q = max{|1 - al|, |1 - aL |}:
||xn - x*|| £ qn||x0 - x*||.
Д о к а з а т е л ь с т в о. Решение x* = argmin f(x) существует и единственно в силу теорем 2.9 и 2.10. Для функции F(x) = f ¢(x) воспользуемся аналогом формулы Ньютона — Лейбница
F(y) = F(x) +
ò
1
0
F ¢[x + s(y - x)](y- x) ds,
или, для x = x* и y = xn, учитывая, что f ¢(x*) = Q,
f ¢(xn) =
ò
1
0
f ¢¢[x* + s(xn - x*)](xn - x*) ds
(9)
(здесь мы, как и выше, воспользовались задачей 2.3). Далее, в силу утверждения (2.5) из п. 2.3 f ¢¢(x) £ L при всех x Î Rm. Кроме того (см. задачу 2.15), по условию f ¢¢(x) ³ l при тех же x. Поэтому, так как
l||h||2 £ (f ¢¢[x* + s(xn -x*)]h, h) £ L ||h||2,
выполнено неравенство
l||h||2 £
æ
è
æ
è
ò
1
0
f ¢¢[x* + s(xn -x*)] ds
ö
ø
h, h
ö
ø
£ L ||h||2.
(10)
Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный в силу симметричности f) оператор на Rm, обозначим его Ln. Неравенство (10) означает, что l £ Ln £ L. В силу (9) градиентный метод (4) записывается в виде
xn+1 = xn - aLn(xn - x*).
Но тогда
||xn+1 - xn|| = ||xn - x* -aLn(xn - x*)|| =
= ||(I - aLn)(xn - x*)|| £ ||I - aLn|| · ||xn - x*||.
Спектр s(I - aLn) оператора I - aLn состоит из чисел вида si = 1 -ali, где li Î s(Ln). В силу (10) и неравенства (2.3),
1 - al ³ si ³ 1 - aL,
и следовательно (см. неравенство (2.4))
||I - aLn|| £ max{|1 -al|, |1 - aL |} = q.
Таким образом,
||xn+1 - xn|| £ q||xn - x*||.
Из этого неравенства и задачи 3.1 вытекает утверждение теоремы.
7. Об оптимальном выборе шага.
Константа q, фигурирующая в теореме 3.7 и характеризующая скорость сходимости метода, зависит от шага a. Нетрудно видеть, что величина
q = q(a) = max{|1 - al|, |1 - aL |}
минимальна, если шаг a выбирается из условия |1 - al| = |1 - aL | (см. рис. 7), т. е. если a = a* = 2/(l+ L). При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной
q = q* =
L - l
L + l
.
Рис. 7.
Напомним (см. п. 2.3), что в качестве l и L могут выступать равномерные по x оценки сверху и снизу собственных значений оператора f ¢¢(x). Если l << L, то q* » 1 и метод сходится очень медленно. Геометрически случай l << L соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 8). Простейшим примером такой функции может служить функция на R2, задаваемая формулой
f(x1, x2) = lx21+ L x22с l << L.
Рис. 8.
Поведение итераций градиентного метода для этой функции изображено на рис. 8 — они, быстро спустившись на "дно оврага", затем медленно "зигзагообразно" приближаются к точке минимума. Число m = L/l (характеризующее, грубо говоря, разброс собственных значений оператора f ¢¢(x)) называют числом обусловленности функции f. Если m >> 1, то функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.
Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может привести к расходимости метода. Мы опишем сейчас два алгоритма автоматического выбора шага, позволяющие частично обойти указанные трудности.
8. Градиентный метод с дроблением шага.
В этом варианте градиентного метода величина шага an на каждой итерации выбирается из условия выполнения неравенства
f(xn+1) = f(xn - anf ¢(xn)) £ f(xn) - ean||f ¢(xn)||2,
(11)
где e Î (0, 1) — некоторая заранее выбранная константа. Условие (11) гарантирует (если, конечно, такие an удастся найти), что получающаяся последовательность будет релаксационной. Процедуру нахождения такого an обычно оформляют так. Выбирается число d Î (0, 1) и некоторый начальный шаг a0. Теперь для каждого n полагают an = a0 и делают шаг градиентного метода. Если с таким an условие (11) выполняется, то переходят к следующему n. Если же (11) не выполняется, то умножают an на d ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство (9) не будет выполняться. В условиях теоремы 3.5 эта процедура для каждого n за конечное число шагов приводит к нужному an.
9. Метод наискорейшего спуска.
Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки xn будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче L = {x Î Rm: x = xn - af ¢(xn); a ³ 0}:
an = argminaÎ[0, ¥)f(xn - af ¢(xn)).
(12)
Рис. 9.
Другими словами, an выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 9). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны. В самом деле, поскольку функция j: a ® f(xn - af ¢(xn)) достигает минимума при a = an, точка an является стационарной точкой функции j:
0 = j¢(an) =
d
da
f(xn - af ¢(xn))
ê
ê
a=an
=
= (f ¢(xn - anf ¢(xn)), -f ¢(xn)) = -(f ¢(xn+1), f ¢(xn)).
Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации (12). Такие задачи будут обсуждаться ниже. Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.
В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.