Методы оптимизации

Назад § 3. Градиентные методы Вперед

... нет такой воды, которая не стремилась бы [течь] вниз.

Мэн-цзы

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

3.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*, то как всегда добавляется эпитет "локально".

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

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

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

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

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

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

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

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

3.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.3. Покажите, что argminx О B(xn, e)f(x) задается формулой (4) с a = e/||f ў(x)||.

3.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 раз".

Гpадиентный метод с постоянным шагом
Рис. 6.

3.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, что и требовалось.

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

Если p = 2, т. е. f(x) = x2, то (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|,

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

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

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

3.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), zndsи воспользовавшись неравенством (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 ® Ґ. 

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

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

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

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

Заметим также, что описанный метод не различает точек локального и глобального минимумов. Поэтому для того, чтобы сделать заключение о сходимости xn к точке 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 = 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 вытекает утверждение теоремы.

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

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

Гpадиентный метод с постоянным шагом
Рис. 8.

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

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

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

В этом варианте градиентного метода величина шага 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.

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

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

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

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

Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки 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). Такие задачи будут обсуждаться ниже. Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.

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

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


an = 

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

З а д а ч а  3.12. Пусть l1, ..., lm собственные числа оператора A. Покажите, что градиентный метод для функции f(x) = (Ax, x)/2 + (b, x) + c с шагами a0 = 1/l1, a1 = 1/l2, ..., am-1 = 1/lm за m шагов дает точное решение: xm = x*.

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


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