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

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

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

 

Выполнил

Студент группы МОС-22

Кравченко Александр

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

В этом варианте градиентного метода величина шага αn на каждой итерации выбирается изусловия выполнения неравенства

<table cellpadding=«0» ">

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}:

<table cellpadding=«0» ">

an= argminaÎ[0, ¥)f(xn -af ¢(xn)).

<img src="/cache/referats/21653/image002.jpg" v:shapes="_x0000_i1026">
Рис. 1

Другими словами, anвыбирается так, чтобыследующая итерация была точкой минимума функции fна луче L (см. рис.1 ).Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, что в этом методенаправления соседних шагов ортогональны. В самом деле, поскольку функция j: a®f(xn -af ¢(xn))достигает минимума при a= an, точка anявляется стационарнойточкой функции j:

<table cellpadding=«0» ">


0 = j¢(an) = 

d

da


f(xn - af ¢(xn))

ê
ê



a=an

=

<table cellpadding=«0» ">

= (f ¢(xn -anf ¢(xn)), -f ¢(xn)) = -(f ¢(xn+1), f ¢(xn)).

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

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

еще рефераты
Еще работы по математике