Градиентный метод с дроблением шага и метод наискорейшего спуска
Семинарская работа
Градиентный метод с дроблением шага и метод
наискорейшего спуска
Выполнил
Студент группы МОС-22
Градиентный метод с дроблением шага.
В этом варианте
градиентного метода величина шага αn на каждой итерации
выбирается из условия выполнения неравенства
f(xn+1) = f(xn
- anf ¢(xn)) £ f(xn) - ean||f ¢(xn)||2,
|
где e Î (0, 1) —
некоторая заранее выбранная константа. Условие гарантирует (если, конечно,
такие an удастся найти), что получающаяся последовательность
будет релаксационной. Процедуру
нахождения такого an обычно оформляют
так.
Выбирается число d Î (0, 1) и
некоторый начальный шаг a0. Теперь для
каждого n полагают an = a0 и делают шаг
градиентного метода. Если с таким an условие
выполняется, то переходят к следующему n. Если же условие не
выполняется, то умножают an на d ("дробят
шаг") и повторяют эту процедуру до тех пор пока равенство
f ¢(xn) =
|
ò
|
1
0
|
f ¢¢[x* + s(xn - x*)](xn - x*) ds
|
не будет
выполняться. В условиях теоремы об условной
сходимости градиентного метода с постоянным шагом эта процедура для каждого n
за конечное число шагов приводит к нужному an.
Можно показать,
что в условиях теоремы (о линейной
сходимости градиентного метода с постоянным щагом) градиентный метод с дроблением шага
линейно сходится. Описанный
алгоритм избавляет нас от проблемы выбора a на каждом шаге,
заменяя ее на проблему выбора параметров e, d и a0, к которым
градиентный метод менее чувствителен. При этом, разумеется, объем вычислений
возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не
очень сильно, поскольку в большинстве задач основные вычислительные затраты
ложатся на вычисление градиента.
Метод наискорейшего спуска.
Этот вариант
градиентного метода основывается на выборе шага из следующего соображения. Из
точки xn будем двигаться в направлении антиградиента до тех пор
пока не достигнем минимума функции f на этом направлении, т. е. на
луче L = {x Î Rm: x
= xn - af ¢(xn);
a ³ 0}:
an = argminaÎ[0, ¥)f(xn - af ¢(xn)).
Другими словами, an выбирается так,
чтобы следующая итерация была точкой минимума функции f на луче L
(см. рис.1 ). Такой вариант
градиентного метода называется методом наискорейшего спуска. Заметим, что в
этом методе направления соседних шагов ортогональны. В самом деле, поскольку
функция 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)).
|
Метод наискорейшего спуска
требует решения на каждом шаге задачи одномерной оптимизации. Практика
показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.
В общей ситуации,
тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не
выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
Похожие работы на - Градиентный метод с дроблением шага и метод наискорейшего спуска
|