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

Название метода можно было бы понимать буквально, если бы речь шла о минимизации целевой функции. Тем не менее, по тра­диции такое название используется и при решении задачи на максимум.

Пусть f(x) = f(x_l,x_l,...x_n) — дифференцируемая функция, заданная на Rⁿ, а — некоторая текущая точка. Оговоримся, что каких-либо общих рекомендаций, каса­ющихся выбора исходной точки (или, как еще говорят, началь­ного приближения) x⁽⁰⁾, не существует, однако по возможно­сти она должна находиться близко от искомого оптимального плана х^*. Как уже говорилось выше, если x^(q) — нестационарная точка (т. е. ), то при движении в направлении функция f(x) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продол­жалось до тех пор, пока возрастание не прекратится. Для этого выразим зависимость значения f(x) от шагового множителя l > 0, полагая

(2.9)

или, в координатной форме,

(2.10)

Чтобы добиться наибольшего из возможных значений f при движении по направлению , нужно выбрать такое значе­ние , которое максимизирует функцию . Для вычисления , используется необходимое условие экстре­мума . Заметим, что если для любого l >0 , то функция f(x) не ограничена сверху (т. е. не име­ет максимума). В противном случае, на основе (2.10) получаем

(2.11)

что, в свою очередь, дает

(2.12)

Если считать, что следующая точка соответствует оп­тимальному значению , то в ней должно выполняться условие , и следует находить из условия или

(2.13)

Условие (2.13) означает равенство нулю скалярного про­изведения градиентов функции f точках х^(q+1) и х^(q) Гео­метрически оно может быть интерпретировано как перпендикулярность векторов градиентов функции f в указанных точ­ках, что и показано на рис. 2.2. Продолжая геометрическую интерпретацию метода наискорейшего спуска, отметим, что в точке х^(q+1) вектор , будучи градиентом, перпендику­лярен линии уровня, проходящей через данную точку. Стало быть, вектор является касательным к этой линии. Итак, движение в направлении градиента следует продолжать до тех пор, пока он пересекает линии уровня оп­тимизируемой функции.

После того как точка х^(q+1) найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение коор­динат точек, рассматриваемых на последовательных итераци­ях. Одновременно с этим координаты вектора должны быть близки к нулю.