Общая схема градиентного спуска

Лабораторная работа № 7

Тема: Методы минимизации функции многих переменной

Рассматриваемые вопросы:

- задачи многомерной оптимизации

- градиентные методы

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

1. Постановка задачи многомерной оптимизации

Задача многомерной безусловной оптимизации формулируется в виде:

min f(x),

xÎX

где x={x⁽¹⁾, x⁽²⁾,…, x⁽ⁿ⁾} – точка в n-мерном пространстве X=IRⁿ, то есть целевая функция f(x)=f(x⁽¹⁾,…,f(x⁽ⁿ⁾) – функция n аргументов.

Будем рассматривать задачу оптимизации на примере задачи минимизации. Численные методы отыскания минимума, как правило, состоят в построении последовательности точек {x_k}, удовлетворяющих условию f(x₀)>f(x₁)>…>f(x_n)>…. Методы построения таких последовательностей называются методами спуска. В этих методах точки последовательности {x_k} вычисляются по формуле:

х_k+1 = x_k + a_kp_k, k=0,1,2,…,

где p_k – направление спуска, a_k – длина шага в этом направлении.

Различные методы спуска отличаются друг от друга способами выбора направления спуска p_k и длины шага a_k вдоль этого направления. Алгоритмы безусловной минимизации принято делить на классы, в зависимости от максимального порядка производных минимизируемой функции, вычисление которых предполагается. Так, методы, использующие только значения самой целевой функции, относят к методам нулевого порядка (иногда их называют также методами прямого поиска); если, кроме того, требуется вычисление первых производных минимизируемой функции, то мы имеем дело с методами первого порядка; если же дополнительно используются вторые производные, то это методы второго порядка и т. д.

2. Градиентные методы

Общая схема градиентного спуска

Как известно, градиент функции в некоторой точке x_k направлен в сторону наискорейшего локального возрастания функции и перпендикулярен линии уровня (поверхность постоянного значения функции f(x), проходящей через точку x_k). Вектор, противоположный градиенту , называется антиградиентом, который направлен в сторону наискорейшего убывания функции f(x). Выбирая в качестве направления спуска p_k антиградиент - в точке x_k, мы приходим к итерационному процессу вида:

x_k+1 = x_k - a_k f’(x_k), a_k>0, k=0,1,2,….

Все итерационные процессы, в которых направление движения на каждом шаге совпадает с антиградиентом функции, называются градиентными методами. Они отличаются друг от друга только способом выбора шага a_k. Существует много различных способов выбора a_k, но наиболее распространены: метод с постоянным шагом, метод с дроблением шага и метод наискорейшего спуска.

Поиск по сайту: