§ 3. Градиентные методы

В этом параграфе изучается класс так называемых градиентных методов приближенного решения задач оптимизации. Доказываются теоремы сходимости, описываются простейшие модификации.

3.1. Общие соображения и определения.

Наиболее распространенные и эффективные методы приближенного решения задачи безусловной оптимизации

f(x) ® min,

(1)

где f: R^m ® R, укладываются в следующую грубую схему. Начиная с некоторого x⁰ О R^m, строится последовательность {xⁿ} М R^m такая, что

f(xn+1) < f(xn)

(2)

при всех n О N. Такие последовательности иногда называют релаксационными, а методы построения релаксационных последовательностей — итерационными методами или методами спуска. Последовательность, удовлетворяющую (2), строят в надежде, что уменьшая на каждом шаге (переходе от xⁿ к xⁿ⁺¹) значение функции, мы приближаемся к минимуму (по крайней мере, локальному).

Мы будем говорить, что метод, начиная с данного x⁰ О R^m,

а) условно сходится, если последовательность {xⁿ} релаксационна и

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.

Если эти свойства выполняются только для x⁰ достаточно близких к x*, то как всегда добавляется эпитет "локально".

З а д а ч а  3.1*. Пусть при некотором q О [0, 1)

||xn+1 - x*|| Ј q||xn - x*||, n О N.

Докажите, что метод линейно сходится.

З а д а ч а  3.2*. Пусть при некотором C₁ > 0

||xn+1 - x*|| Ј C1||xn -x*||2, n О N

и ||x⁰ - x*|| достаточно мала. Докажите, что метод квадратично сходится.

Будем говорить, что на данной последовательности метод сходится с порядком p (или имеет p-ый порядок сходимости), если при некотором C

||xn+1 - x*|| Ј C||xn - x*||p.

3.2. Эвристические соображения, приводящие к градиентным методам.

Выше уже отмечалось, что если x не является точкой локального минимума функции f, то двигаясь из x в направлении, противоположном градиенту (еще говорят, в направлении антиградиента), мы можем локально уменьшить значение функции. Этот факт позволяет надеяться, что последовательность {xⁿ}, рекуррентно определяемая формулой

xn+1 = xn - af ў(xn),

(4)

где a - некоторое положительное число, будет релаксационной.

К этой же формуле приводит и следующее рассуждение. Пусть у нас есть некоторое приближение xⁿ. Заменим в шаре B(xⁿ, e) с центром в точке xⁿ функцию f ее линейным (вернее, афинным) приближением:

f(x) » j(x) =def f(xn) + (f ў(xn), x - xn)

(функция j аппроксимирует f в окрестности точки xⁿ с точностью o(x - xⁿ)). Разумеется, (линейная) безусловная задача j(x) ® min неразрешима, если f ў(xⁿ) № Q (см. задачу 1.3). В окрестности же B(xⁿ, e) функция j имеет точку минимума. Эту точку естественно взять за следующее приближение xⁿ⁺¹.

З а д а ч а  3.3. Покажите, что argminx О B(xn, e)f(x) задается формулой (4) с a = e/||f ў(x)||.

3.3. Градиентный метод с постоянным шагом.

В общем случае число a в формуле (4) может на каждом шаге (т. е. для каждого n) выбираться заново:

xn+1 = xn - anf ў(xn).

(5)

Именно методы, задаваемые формулой (5), называются градентными. Если aⁿ = a при всех n, то получающийся метод называется градиентным методом с постоянным шагом (с шагом a.)

Поясним геометрическую суть градиентного метода. Для этого мы выберем способ изображения функции с помощью линий уровня. Линией уровня функции f (изолинией) называется любое множество вида {x О R^m: f(x) = c}. Каждому значению c отвечает своя линия уровня (см. рис. 5).

Рис. 5.

З а д а ч а  3.4.  Докажите, что касательная к линии уровня функции f: R² ® R ортогональна к градиенту. Как обобщить это утверждение на многомерный случай?

Геометрическая интерпретация градиентного метода с постоянным шагом изображена на рис. 6. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в a раз".

Рис. 6.

3.4. Один пример исследования сходимости.

Изучим сходимость градиентного метода с постоянным шагом на примере функции

f(x) = |x|p,

где p > 1 (случай p Ј 1 мы не рассматриваем, поскольку тогда функция f не будет гладкой, а мы такой случай не исследуем). Очевидно, задача (1) с такой функцией f имеет единственное решение x* = 0. Для этой функции приближения xⁿ градиентного метода имеют вид:

xn+1 = xn - ap|xn|p-1sign xn.

(6)

Пределом этой последовательности может быть только 0. Действительно, если x** = lim_n®Ґ xⁿ № 0, то, переходя к пределу в (6) при n ® Ґ, получаем противоречащее предположению x** № 0 равенство

x** = x** - ap|x**|p-1sign  x**,

откуда x** = 0. Очевидно также, что если x⁰ = 0, то и xⁿ = 0 при всех n.

Покажем, что если p < 2, то при любом шаге a > 0 и любом начальном приближении x⁰ (за исключением не более чем счетного числа точек) приближения (6) не являются сходящимися. Для этого заметим, что если 0 < |xⁿ| < (2/ap)^1/2(2-p), то

|xn+1| > |xn|.

(7)

Поэтому, если xⁿ не обращается в нуль, то она не может сходиться к нулю и, следовательно, не может сходиться вообще.

З а д а ч а  3.5. Докажите.

Таким образом, осталось доказать (7). В силу (6)

|xn+1| = |xn - ap|xn|p-1 ·sign xn| = |xn|·| 1 -ap|xn|p-2·sign xn|.

Остается заметить, что если 0 < |xⁿ| < (2/ap)^1/(2-p), то, как нетрудно видеть, |1 - ap|xⁿ|^p-2·sign  xⁿ| > 1, что и требовалось.

З а д а ч а  3.6.  Покажите, что число начальных точек x⁰, для которых xⁿ обращается в нуль при некотором n (и следовательно, при всех бóльших), не более чем счетно.

Если p = 2, т. е. f(x) = x², то (6) переписывается в виде

|xn+1| = |xn|·|1 - 2a|.

Поэтому, если a О (0, 1), то |1 - 2a| < 1, а следовательно,

|xn+1| = |1 - 2a|n+1·|x0| ® 0 при n ® Ґ.

Если же a і 1, то

|xn+1| і |xn|,

и последовательность {xⁿ}, начинающаяся из ненулевой начальной точки, расходится.

З а д а ч а  3.7.  Докажите, что если p > 2, то градиентный метод (6) сходится при ap|x⁰|^p-2 < 2 и расходится при ap|x⁰|^p-2 і 2 для любых начальных точек, за исключением может быть счетного множества.

Таким образом, есть функции, для которых градиентный метод не сходится даже при сколь угодно малом шаге a и есть функции, для которых он сходится только при достаточно малых шагах. В следующих пунктах мы приведем ряд теорем о сходимости градиентного метода.

3.5. Теорема об условной сходимости градиентного метода с постоянным шагом.

Пусть в задаче (1) функция f ограничена снизу, непрерывно дифференцируема и, более того, f ў удовлетворяет условию Липшица:

||f ў(x) - f ў(y)|| Ј L ||x - y|| при всех x, y О Rm.

Тогда при a О (0, 2/L) градиентный метод с постоянным шагом условно сходится.

Д о к а з а т е л ь с т в о.  Положим zⁿ = -af ў(xⁿ) и обозначим f(xⁿ + tzⁿ) через 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(xⁿ)} не возрастает и, следовательно, релаксационность {xⁿ} доказана. А так как в силу условий теоремы f еще и ограничена снизу, последовательность {f(xⁿ)} сходится. Поэтому, в частности, f(xⁿ⁺¹) - f(xⁿ) ® 0 при n ® Ґ. Отсюда и из (8) получаем

||f ў(xn)||2 Ј a-1 ж и 1 –  La 2 ц ш –1 [f(xn) - f(xn+1)] ® 0 при n ® Ґ.

3.6. Замечания о сходимости.

Подчеркнем, что теорема 3.5 не гарантирует сходимости метода, но лишь его условную сходимость, причем, локальную. Например, для функции f(x) = (1 + x²)^-1 на R последовательность {xⁿ} градиентного метода с постоянным шагом, начинающаяся с произвольного x⁰ стремится к Ґ.

З а д а ч а  3.8. Докажите.

Поскольку в теореме 3.5 градиент непрерывен, любая предельная точка последовательности {xⁿ} является стационарной. Однако эта точка вовсе не обязана быть точкой минимума, даже локального. Например, рассмотрим для функции f(x) = x²sign x градиентный метод с шагом a О (0, 1/2). Тогда, как легко видеть, если x⁰ > 0, то xⁿ ® 0 при n ® Ґ. Точка же x = 0 не является локальным минимумом функции f.

Заметим также, что описанный метод не различает точек локального и глобального минимумов. Поэтому для того, чтобы сделать заключение о сходимости xⁿ к точке x* = argmin f(x) приходится налагать дополнительные ограничения, гарантирующие, в частности, существование и единственность решения задачи (1). Один вариант таких ограничений описывается ниже.

3.7. Теорема о линейной сходимости градиентного метода с постоянным шагом.

Пусть выполнены условия теоремы 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 = xⁿ, учитывая, что 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 О R^m. Кроме того (см. задачу 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) оператор на R^m, обозначим его Lⁿ. Неравенство (10) означает, что l Ј Lⁿ Ј 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 - aLⁿ) оператора I - aLⁿ состоит из чисел вида s_i = 1 -al_i, где l_i О s(Lⁿ). В силу (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 вытекает утверждение теоремы.

3.8. Об оптимальном выборе шага.

Константа 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). Простейшим примером такой функции может служить функция на R², задаваемая формулой

f(x1, x2) = lx21+ L x22с l << L.

Рис. 8.

Поведение итераций градиентного метода для этой функции изображено на рис. 8 — они, быстро спустившись на "дно оврага", затем медленно "зигзагообразно" приближаются к точке минимума. Число m = L/l (характеризующее, грубо говоря, разброс собственных значений оператора f ўў(x)) называют числом обусловленности функции f. Если m >> 1, то функции называют плохо обусловленными или овражными. Для таких функций градиентный метод сходится медленно.

Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может привести к расходимости метода. Мы опишем сейчас два алгоритма автоматического выбора шага, позволяющие частично обойти указанные трудности.

3.9. Градиентный метод с дроблением шага.

В этом варианте градиентного метода величина шага aⁿ на каждой итерации выбирается из условия выполнения неравенства

f(xn+1) = f(xn - anf ў(xn)) Ј f(xn) - ean||f ў(xn)||2,

(11)

где e О (0, 1) — некоторая заранее выбранная константа. Условие (11) гарантирует (если, конечно, такие aⁿ удастся найти), что получающаяся последовательность будет релаксационной. Процедуру нахождения такого aⁿ обычно оформляют так. Выбирается число d О (0, 1) и некоторый начальный шаг a⁰. Теперь для каждого n полагают aⁿ = a⁰ и делают шаг градиентного метода. Если с таким aⁿ условие (11) выполняется, то переходят к следующему n. Если же (11) не выполняется, то умножают aⁿ на d ("дробят шаг") и повторяют эту процедуру до тех пор пока неравенство (9) не будет выполняться. В условиях теоремы 3.5 эта процедура для каждого n за конечное число шагов приводит к нужному aⁿ.

З а д а ч а  3.9. Докажите (воспользуйтесь неравенством (8)).

З а д а ч а  3.10. Сходится ли градиентный метод с дроблением шага для функции f(x) = |x|^p при p О (1, 2)?

Можно показать, что в условиях теоремы 3.7 градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора a на каждом шаге, заменяя ее на проблему выбора параметров e, d и a⁰, к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.

3.10. Метод наискорейшего спуска.

Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки xⁿ будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче L = {x О R^m: x = xⁿ - af ў(xⁿ); a і 0}:

an = argminaО[0, Ґ)f(xn - af ў(xn)).

(12)

Рис. 9.

Другими словами, aⁿ выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис. 9). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, кстати, что в этом методе направления соседних шагов ортогональны. В самом деле, поскольку функция j: a ® f(xⁿ - af ў(xⁿ)) достигает минимума при a = aⁿ, точка aⁿ является стационарной точкой функции j:

0 = jў(an) =  d da f(xn - af ў(xn)) к к a=an =

= (f ў(xn - anf ў(xn)), -f ў(xn)) = -(f ў(xn+1), f ў(xn)).

Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации (12). Такие задачи будут обсуждаться ниже. Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.

В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.

З а д а ч а  3.11. Докажите, что если f(x) = (Ax, x)/2 + (b, x) + c, где A — симметричный оператор в R^m, а b, c О R^m, то шаг aⁿ метода наискорейшего спуска задается явной формулой

an =  ||Axn + b||2 (A2xn + Ab, Axn + b) .

З а д а ч а  3.12. Пусть l¹, ..., l^m — собственные числа оператора A. Покажите, что градиентный метод для функции f(x) = (Ax, x)/2 + (b, x) + c с шагами a⁰ = 1/l¹, a¹ = 1/l², ..., a^m-1 = 1/l^m за m шагов дает точное решение: x^m = x*.

Мы еще вернемся к модификациям градиентного метода после изучения класса ньютоновских методов.

File based on translation from T_EX by T_TH, version 3.05.
Created 6 Jun 2002, 11: 23.