Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

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

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

Пусть f(x)=f(x1,x1,...xn) —дифференцируемая функция, заданная на Rn, а х(q) = (x1(q),x2(q),...,xn(q)) — некоторая текущая точка. Оговоримся, что каких-либо общих рекомендаций, касающихся выбора исходной точки (или, как еще говорят, начального приближения) х(0), не существует, однако по возможности она должна находиться близко от искомого оптимального плана х*. Как уже говорилось выше, если х(q) — нестационарная точка (т. е. |f(x(q))|>0), то при движении в направлении f(x(q)) функция f(х) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продолжалось до тех пор, пока возрастание не прекратится. Для этого выразим зависимость значения f(x) от шагового множителя λ > 0. полагая х = х(q) + λf(x(q))

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

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

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

Если считать, что следующая точка х(q+1) соответствует оптимальному значению λ=, то в ней должно выполняться условие dφ()/dλ = 0, и следует находить из условия f(x(q+1)) f(x(q))=0 или

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

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