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

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

Градиентные методы решения задач безусловной оптимизации

Градиентные методы решения задач безусловной оптимизации. Ведущее место среди прямых методов решения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационарных точек дифференцируемой функции. Напомним, что стационарной называется точка, в которой f(x)=0 и которая в соответствии с необходимым условием оптимальности является «подозрительной» на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество точек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.

Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х(1) перемещаться в направлении вектора f(x(1)), то функция f будет возрастать, по крайней мере, в некоторой окрестности х(1). Следовательно, для точки х(2) = х(1)f(x(1)), (λ>0), лежащей в такой окрестности, справедливо неравенство f(x(1))≤ f(x(2)). Продолжая этот процесс, мы постепенно будем приближаться к точке некоторого локального максимума (см. рис. 2.1).

Однако как только определяется направление движения, сразу же встает вопрос о том, как далеко следует двигаться в этом направлении или, другими словами, возникает проблема выбора шага λ в рекуррентной формулe

задающей последовательность точек, стремящихся к точке максимума.

В зависимости от способа ее решения различают различные варианты градиентного метода. Остановимся на наиболее известных из них.