Градиентные методы оптимизации. Метод наискорейшего спуска.
Опубликовано: 12.10.2017
Метод градиентного спуска.
Направление наискорейшего спуска соответствует направлению наибольшего убывания функции. Известно, что направление наибольшего возрастания функции двух переменных u = f(x, у) характеризуется ее градиентом:
Лекция 18: Многомерная оптимизация (часть 1)
где e1, е2 — единичные векторы (орты) в направлении координатных осей. Следовательно, направление, противоположное градиентному, укажет направление наибольшего убывания функции. Методы, основанные на выборе пути оптимизации с помощью градиента, называются градиентными.
Р.В. Шамин. Теория оптимизации - лекция № 02
Идея метода градиентного спуска состоит в следующем. Выбираем некоторую начальную точку
вычисляем в ней градиент рассматриваемой функции. Делаем шаг в направлении, обратном градиентному:
Процесс продолжается до получения наименьшего значения целевой функции. Строго говоря, момент окончания поиска наступит тогда, когда движение из полученной точки с любым шагом приводит к возрастанию значения целевой функции. Если минимум функции достигается внутри рассматриваемой области, то в этой точке градиент равен нулю, что также может служить сигналом об окончании процесса оптимизации.
Метод градиентного спуска обладает тем же недостатком, что и метод покоординатного спуска: при наличии оврагов на поверхности сходимость метода очень медленная.
В описанном методе требуется вычислять на каждом шаге оптимизации градиент целевой функции f(х):
Формулы для частных производных можно получить в явном виде лишь в том случае, когда целевая функция задана аналитически. В противном случае эти производные вычисляются с помощью численного дифференцирования: