§ 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) → Θ при 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 – αf ′(xn),

(4)

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

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

f(x) ≈ φ(x) ≝ f(xn) + (f ′(xn), x – xn)

(функция φ аппроксимирует f в окрестности точки xⁿ с точностью o(x – xⁿ)). Разумеется, (линейная) безусловная задача φ(x) → min неразрешима, если f ′(xⁿ) ≠ Θ (см. задачу 1.3). В окрестности же B(xⁿ, ε) функция φ имеет точку минимума. Эту точку естественно взять за следующее приближение xⁿ⁺¹.

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

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

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

xn+1 = xn – αnf ′(xn).

(5)

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

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

Рис. 5.

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

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

Рис. 6.

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

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

f(x) = |x|p,

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

xn+1 = xn – αp|xn|p–1sign xn.

(6)

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

x** = x** – αp|x**|p–1sign  x**,

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

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

|xn+1| > |xn|.

(7)

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

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

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

|xn+1| = |xn – αp|xn|p–1 ·sign xn| = |xn|·| 1 –αp|xn|p–2·sign xn|.

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

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

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

|xn+1| = |xn|·|1 – 2α|.

Поэтому, если α ∈ (0, 1), то |1 – 2α| < 1, а следовательно,

|xn+1| = |1 – 2α|n+1·|x0| → 0 при n → ∞.

Если же α ≥ 1, то

|xn+1| ≥ |xn|,

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

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

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

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

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

||f ′(x) – f ′(y)|| ≤ Λ ||x – y|| при всех x, y ∈ Rm.

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

Д о к а з а т е л ь с т в о.  Положим zⁿ = –αf ′(xⁿ) и обозначим f(xⁿ + tzⁿ) через φ(t). Тогда, как легко видеть,

φ′(t) = (f ′(xn + tzn), zn)

и поэтому по формуле Ньютона — Лейбница для функции φ

f(xn+1) – f(xn) = f(xn + zn) – f(xn) = φ(1) – φ(0) =

=  ∫ 1 0 φ′(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), –αf ′(xn)) +  ∫ 1 0 ||f ′(xn + szn) – f ′(xn)|| · ||zn|| ds.

Учитывая условие Липшица для f ′, эту цепочку можно продолжить:

f(xn+1) – f(xn) ≤ –α||f ′(xn)||2 + Λ ||zn||2 ∫ 1 0 s ds = = – α||f ′(xn)||2 +  Λα2 2 ||f ′(xn)||2 = –α||f ′(xn)||2 ( 1 –  Λα 2 ) .

(8)

Поскольку 1 – Λα/2 > 0, последовательность {f(xⁿ)} не возрастает и, следовательно, релаксационность {xⁿ} доказана. А так как в силу условий теоремы f еще и ограничена снизу, последовательность {f(xⁿ)} сходится. Поэтому, в частности, f(xⁿ⁺¹) – f(xⁿ) → 0 при n → ∞. Отсюда и из (8) получаем

||f ′(xn)||2 ≤ α–1 ( 1 –  Λα 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 градиентный метод с шагом α ∈ (0, 1/2). Тогда, как легко видеть, если x⁰ > 0, то xⁿ → 0 при n → ∞. Точка же x = 0 не является локальным минимумом функции f.

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

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

Пусть выполнены условия теоремы 3.5 и, кроме того, f дважды непрерывно дифференцируема и сильно выпукла с константой λ. Тогда при α ∈ (0, 2/Λ) градиентный метод с шагом α сходится со скоростью геометрической прогрессии со знаменателем q = max{|1 – αλ|, |1 – αΛ |}:

||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*) = Θ,

f ′(xn) =  ∫ 1 0 f ′′[x* + s(xn – x*)](xn – x*) ds

(9)

(здесь мы, как и выше, воспользовались задачей 2.3). Далее, в силу утверждения (2.5) из п. 2.3 f ′′(x) ≤ Λ при всех x ∈ R^m. Кроме того (см. задачу 2.15), по условию f ′′(x) ≥ λ при тех же x. Поэтому, так как

λ||h||2 ≤ (f ′′[x* + s(xn –x*)]h, h) ≤ Λ ||h||2,

выполнено неравенство

λ||h||2 ≤  ( ( ∫ 1 0 f ′′[x* + s(xn –x*)] ds ) h, h )  ≤ Λ ||h||2.

(10)

Интеграл, стоящий в этом неравенстве, определяет линейный (симметричный в силу симметричности f) оператор на R^m, обозначим его Lⁿ. Неравенство (10) означает, что λ ≤ Lⁿ ≤ Λ. В силу (9) градиентный метод (4) записывается в виде

xn+1 = xn – αLn(xn – x*).

Но тогда

||xn+1 – xn|| = ||xn – x* –αLn(xn – x*)|| = = ||(I – αLn)(xn – x*)|| ≤ ||I – αLn|| · ||xn – x*||.

Спектр σ(I – αLⁿ) оператора I – αLⁿ состоит из чисел вида σ_i = 1 –αλ_i, где λ_i ∈ σ(Lⁿ). В силу (10) и неравенства (2.3),

1 – αλ ≥ σi ≥ 1 – αΛ,

и следовательно (см. неравенство (2.4))

||I – αLn|| ≤ max{|1 –αλ|, |1 – αΛ |} = q.

Таким образом,

||xn+1 – xn|| ≤ q||xn – x*||.

Из этого неравенства и задачи 3.1 вытекает утверждение теоремы.

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

Константа q, фигурирующая в теореме 3.7 и характеризующая скорость сходимости метода, зависит от шага α. Нетрудно видеть, что величина

q = q(α) = max{|1 – αλ|, |1 – αΛ |}

минимальна, если шаг α выбирается из условия |1 – αλ| = |1 – αΛ | (см. рис. 7), т. е. если α = α* = 2/(λ+ Λ). При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной

q = q* =  Λ – λ Λ + λ .

Рис. 7.

Напомним (см. п. 2.3), что в качестве λ и Λ могут выступать равномерные по x оценки сверху и снизу собственных значений оператора f ′′(x). Если λ << Λ, то q* ≈ 1 и метод сходится очень медленно. Геометрически случай λ << Λ соответствует функциям с сильно вытянутыми линиями уровня (см. рис. 8). Простейшим примером такой функции может служить функция на R², задаваемая формулой

f(x1, x2) = λx21+ Λ x22с λ << Λ.

Рис. 8.

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

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

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

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

f(xn+1) = f(xn – αnf ′(xn)) ≤ f(xn) – εαn||f ′(xn)||2,

(11)

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

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

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

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

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

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

αn = argminα∈[0, ∞)f(xn – αf ′(xn)).

(12)

Рис. 9.

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

0 = φ′(αn) =  d dα f(xn – αf ′(xn)) | α=αn =

= (f ′(xn – αnf ′(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, то шаг αⁿ метода наискорейшего спуска задается явной формулой

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

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

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

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