Метод наискорейшего спуска

Суть данного метода заключается в том, что с помощью упомянутого ранее метода покоординатного спуска осуществляется поиск из заданной точки в направлении, параллельном одной из осей, до точки минимума в данном направлении. Затем поиск производится в направлении, параллельном другой оси, и т.д. Направления, конечно, фиксированы. Кажется разумным попытаться модифицировать этот метод таким образом, чтобы на каждом этапе поиск точки минимума производился вдоль "наилучшего" направления. Не ясно, какое направление является "наилучшим", но известно, что направление градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление является направлением наискорейшего убывания функции. Это свойство может быть обосновано следующим образом.
Предположим, что осуществляется перемещение из точки x в следующую точку х + hd, где d - некоторое направление, a h - шаг некоторой длины. Следовательно, перемещение производится из точки (x1, х2, ..., хn) в точку (x1 + zx1, x2 + zх2, ..., хn + zхn), где
(1.1)
a dj - косинусы направления d, такие, что

(1.2)

Изменение значений функции определяется соотношениями

(1.3)

с точностью до первого порядка zxi, причем частные производные вычисляются в точке x. Как следует выбрать направления di, удовлетворяющие уравнению (1.2), чтобы получить наибольшее значение изменения функции df? Здесь возникает задача максимизации с ограничением. Применим метод множителей Лагранжа, с помощью которого определим функцию

Величина df, удовлетворяющая ограничению (1.2), достигает максимума, когда функция

достигает максимума. Ее производная
(1.5)

Следовательно,
(1.6)

Тогда di ~ df/dxi и направление d параллельно направлению V/(x) в точке х.

Таким образом, наибольшее локальное возрастание функции для заданного малого шага h имеет место, когда d есть направление Vf(x) или g(х). Поэтому направлением наискорейшего спуска является направление

(1.7)

В более простом виде уравнение (1.3) можно записать так:

где - угол между векторами Vf(x) и dx. Для заданной величины dx мы минимизируем df, выбирая , чтобы направление dx совпадало с направлением -Vf(x).

Замечание. Направление градиента перпендикулярно в любой точке линии постоянного уровня, поскольку вдоль этой линии функция постоянна. Таким образом, если (d1, d2, ..., dn) - малый шаг вдоль линии уровня, то

и, следовательно,
(1.8)

Рис. 11.1.
В методе наискорейшего спуска желательно использовать рассмотренное свойство направления градиента. Поэтому, если мы находимся в точке xi на некотором шаге процесса оптимизации, то поиск минимума функции осуществляется вдоль направления -Vf(xj). Данный метод является итерационным. На шаге i точка минимума аппроксимируется точкой xi. Следующей аппроксимацией является точка
(1.9)

где - значение , минимизирующее функцию
(1.10)
Значение может быть найдено с помощью одного из методов одномерного поиска. Блок-схема метода наискорейшего спуска приведена на рис. 11.2.

Powered by Drupal - Design by artinet