Доклад по математическому моделированию
На тему “Градиентныеметоды”
Студента группы ЭФП-21
Мельникова Олега
Курск 2004 год
1.Общие сведения.
Наиболее распространенные и эффективные методы приближенногорешения задачи безусловной оптимизации
f(x) ®min,
(1)
где f: Rm ®R, укладываются в следующую схему. Начиная с некоторого x0ÎRm,строится последовательность {xn} ÌRm такая, что
f(xn+1)
(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.
Выше ужеотмечалось, что если 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. В окрестности же B(xn,e)функция jимеет точку минимума. Эту точку естественно взять за следующее приближение xn+1.
2. Градиентный метод с постояннымшагом.
В общем случае число aв формуле (4)может на каждом шаге (т. е. для каждого n)выбираться заново:
xn+1= xn -anf ¢(xn).
(5)
Именно методы, задаваемые формулой (5),называются градентными. Если an= aпри всех n, то получающийся метод называется градиентным методом спостоянным шагом (с шагом a.)
Поясним геометрическую суть градиентного метода. Для этоговыберем способ изображения функции с помощью линий уровня. Линией уровня функции f (изолинией)называется любое множество вида {x ÎRm: f(x) = c}. Каждому значению cотвечает своя линия уровня (см. рис. 1).
Рис. 1.
Геометрическая интерпретация градиентного метода с постояннымшагом изображена на рис. 2.На каждом шаге сдвигаемся по вектору антиградиента, «уменьшенному в aраз».
Рис. 2.
Изучим сходимость градиентногометода с постоянным шагом на примере функции
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 0 и любом начальном приближении x0(за исключением не более чем счетного числа точек) приближения (6)не являются сходящимися. Для этого заметим, что если 0
|xn+1| > |xn|.
(7)
Поэтому, если xnне обращается в нуль, то она не может сходиться к нулю и, следовательно, неможет сходиться вообще.
Таким образом, осталось доказать (7).В силу (6)
|xn+1| = |xn -ap|xn|p-1·sign xn| = |xn|·| 1 -ap|xn|p-2·sign xn|.
Остается заметить, что если 0 1, что и требовалосьдоказать.
Если p = 2, т. е. f(x) = x2,то (6)имеет вид
|xn+1| = |xn|·|1 -2a|.
Поэтому, если aÎ(0, 1), то |1 -2a|
|xn+1| = |1 -2a|n+1·|x0| ®0 при n ®¥.
Если же a³1, то
|xn+1| ³|xn|,
и последовательность {xn},начинающаяся из ненулевой начальной точки, расходится.
Таким образом, есть функции, для которых градиентный метод несходится даже при сколь угодно малом шаге aи есть функции, длякоторых он сходится только при достаточно малых шагах. В следующих пунктахрассмотрим ряд теорем о сходимости градиентного метода.
3.Теорема об условной сходимости градиентного метода с постоянным шагом.
Пусть в задаче (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
sds =
= -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 ®¥.
Подчеркнем, что теоремане гарантирует сходимостиметода, но лишь его условнуюсходимость, причем, локальную.