ВУЗ:
Составители:
Рубрика:
133
Оптимизировать целевую функцию можно также при помощи метода гра-
диентного спуска. Поясним сущность данного метода физически.
Некоторые природные явления сходны с решением задач оптимизации.
Например, стекание воды с берега котлована на дно. Если принять, что его бе-
рега «унимодальны», то есть они гладкие и не содержат локальных углублений
или выступов, то тогда вода устремится вниз в направлении наибольшей кру-
тизны берега в каждой точке. Выражаясь математически, направление наиско-
рейшего спуска соответствует направлению наибольшего убывания функции.
Из курса высшей математики известно, что направление наибольшего воз-
растания функции двух переменных u = f(x, y) характеризуется ее градиентом
21
e
y
u
e
x
u
ugrad
rr
r
∂
∂
+
∂
∂
= ,
где
1
е
r
,
2
е
r
– единичные векторы (орты) в направлении координатных осей.
Следовательно, направление, противоположное градиентному, укажет
путь, ведущий вниз вдоль наиболее крутой линии спуска.
Идея метода градиентного спуска состоит в следующем.
Выбираем некоторую начальную точку и вычисляем в ней градиент рас-
сматриваемой функции. Делаем шаг в направлении, обратном градиентному. В
результате приходим в точку, значение функции в которой обычно меньше
первоначального. Если это условие не выполнено, то есть значение функции не
изменилось или даже возросло, то нужно уменьшить шаг.
В новой точке процедуру повторяем: вычисляем градиент и снова делаем
шаг в обратном к нему направлении. Процесс продолжается до получения наи-
меньшего значения целевой функции. Момент окончания поиска наступает то-
гда, когда движение из полученной точки с любым шагом приводит к возраста-
нию значения целевой функции. Если в какой-либо точке внутри области
grad = 0, то минимум целевой функции в ней достигнут.
В данном методе требуется вычислять на каждом шаге оптимизации гра-
диент целевой функции f(x
1
, x
2
, …, x
n
):
.
x
f
...,,
x
f
,
x
f
fgrad
n21
∂
∂
∂
∂
∂
∂
=
r
При этом формулы для частных производных можно получить в явном ви-
де лишь тогда, когда целевая функция задана аналитически. В противном слу-
чае эти производные могут быть вычислены с помощью численного дифферен-
цирования:
( ) ( )
[ ]
.n...,,2,1i,x..,,x...,,xfx...,,xx...,,xf
x
1
x
f
ni1nii1
ii
=−∆+
∆
≈
∂
∂
Страницы
- « первая
- ‹ предыдущая
- …
- 133
- 134
- 135
- 136
- 137
- …
- следующая ›
- последняя »
