Составители:
покоординатного спуска следует также отнести возможность использования простых алгоритмов одномерной
оптимизации. Блок-схема метода покоординатного спуска представлена на Рисунке 9.5
Рисунок 9.5 Блок-схема метода покоординатного спуска
3.3 Метод градиентного спуска. В природе мы нередко наблюдаем явления, сходные с решением
задачи на нахождение минимума. К ним относится, в частности, стекание воды с берега котлована на дно.
Упростим ситуацию, считая, что берега котлована «унимодальны», т. е. они гладкие и не содержат локальных
углублений или выступов. Тогда вода устремится вниз в направлении наибольшей крутизны берега в каждой
точке.
Переходя на математический язык, заключаем, что направление наискорейшего спуска соответствует направ-
лению наибольшего убывания функции. Из курса математики известно, что направление наибольшего
возрастания функции двух переменных u = f(x, у) характеризуется ее градиентом
,
21
e
y
u
e
x
u
ugrad
∂
∂
+
∂
∂
=
где e
1
, е
2
— единичные векторы (орты) в направлении координатных осей. Следовательно, направление,
противоположное градиентному, укажет путь, ведущий вниз вдоль наиболее крутой линии. Методы,
основанные на выборе пути оптимизации с помощью градиента, называются градиентными.
Идея метода градиентного спуска состоит в следующем. Выбираем некоторую начальную точку и вычисляем
в ней градиент рассматриваемой функции. Делаем шаг в направлении, обратном градиентному. В результате
приходим в точку, значение функции в которой обычно меньше первоначального. Если это условие не
выполнено, т. е. значение функции не изменилось либо даже возросло, то нужно уменьшить шаг. В новой
точке процедуру повторяем: вычисляем градиент и снова делаем шаг в обратном к нему направлении.
Процесс продолжается до получения наименьшего значения целевой функции. Момент окончания поиска
наступит тогда, когда движение из полученной точки с любым шагом приводит к возрастанию значения
целевой функции. Строго говоря, если минимум функции достигается внутри рассматриваемой области, то в
этой точке градиент равен нулю, что также может служить сигналом об окончании процесса оптимизации.
В описанном методе требуется вычислять на каждом шаге оптимизации градиент целевой функции f(x
1
, x
2
, …,
x
n
):
Страницы
- « первая
- ‹ предыдущая
- …
- 135
- 136
- 137
- 138
- 139
- …
- следующая ›
- последняя »
