ВУЗ:
Составители:
68
недостаток – медленная сходимость. Поэтому его часто используют на
начальном этапе решения задачи, переходя затем к более сложным, но и
более быстрым методам.
4.3. Градиентные методы. Метод наискорейшего спуска
Алгоритмы оптимизации, использующие для поиска минимума не
только значения целевой функции, но и значения ее градиента составляют
основу так называемых градиентных методов. Напомним, что вектор
градиента
n
x
f
x
f
x
f
fgradf
∂
∂
++
∂
∂
+
∂
∂
==∇ ...
21
перпендикулярен линии (поверхности) уровня и направлен в сторону
возрастания функции. Направление градиента в рассматриваемой точке
есть направление наибольшего возрастания функции.
Один из градиентных методов, носящий название метода
градиентного спуска, основан на смещении на постоянный шаг в
направлении, противоположном направлению градиента, с последующим
вычислением значения целевой функции в полученной точке. Если это
значение оказывается меньше предыдущего, то вычисляется градиент в
новой точке, и все действия повторяются. При этом величина шага может
быть увеличена. Если же значение целевой функции возрастает или не
изменяется, то шаг смещения из предыдущей точки уменьшается, и все
вычисления повторяются. Итерации продолжаются до тех пор, пока
расстояние между точками, полученными на двух последовательных
итерациях, не снизится до заданной величины, либо не будет достигнута
заданная близость значений целевой функции:
ε
≤−
+++
)...,,,()...,,,(
)()(
2
)(
1
)1()1(
2
)1(
1
i
n
iii
n
ii
xxxfxxxf . (4.3)
Если компоненты вектора градиента не удается определить
аналитическим способом, то можно найти их приближенные значения в
рассматриваемой точке, аппроксимируя производные центральными
разностями:
∆
∆−−∆+
=
∂
∂
2
)...,,...,,,()...,,...,,,(
2121 nknk
k
xxxxfxxxxf
x
f
,
где малое приращение переменной
k
x .
Вариантом градиентного спуска является алгоритм, реализованный в
методе наискорейшего спуска. В этом алгоритме градиент вычисляется
далеко не в каждой точке траектории спуска, а лишь там, где достигнут
Страницы
- « первая
- ‹ предыдущая
- …
- 66
- 67
- 68
- 69
- 70
- …
- следующая ›
- последняя »
