Градиентный метод с дроблением шага и метод наискорейшего спуска

Загрузить архив:
Файл: ref-21653.zip (11kb [zip], Скачиваний: 293) скачать

Семинарская работа

Градиентный метод с дроблением шага и метод наискорейшего спуска

Выполнил

Студент группы МОС-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)).


Рис. 1

Другими словами, an выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. ). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, что в этом методе направления соседних шагов ортогональны. В самом деле, поскольку функция 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)).

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

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