Семинарскаяработа
Градиентныйметод с дроблением шага и метод наискорейшего спуска
Выполнил
Студент группы МОС-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 (см. рис.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)).
Методнаискорейшего спуска требует решения на каждом шаге задачиодномерной оптимизации. Практика показывает, что этот метод часто требуетменьшего числа операций, чем градиентный методс постоянным шагом.
В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не вышескорости сходимости градиентного метода с постоянным (оптимальным) шагом.