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

Многомерная оптимизация

Задачи многомерной минимизации, естественно, сложнее задач одномерной минимизации.

С увеличением числа переменных увеличивается объём вычислений, усложняются алгоритмы расчёта.

Разработано много различных методов решения задач многомерной оптимизации, которые можно разбить на три основных класса:

- методы прямого поиска (нулевого порядка), использующие только значения целевой функции,

- методы первого порядка, использующие значения целевой функции, а также значения её первых производных,

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

В отличие от методов первого и второго порядков, методы прямого поиска менее обоснованы, но более просты в реализации.

Релаксационная последовательность. Методы спуска

Универсального метода, оптимального для решения всех задач оптимизации, не существует.

Во всех численных методах решения задач минимизации строится последовательность точек {xk}, удовлетворяющая условию

f(x k+1) ≤ f(x k) , k = 0, 1, 2, … (1)

Последовательность, удовлетворяющая условию (1), называется релаксационной, а методы, позволяющие строить такие последовательности, называют методами спуска.

Обычно алгоритм построения релаксационной последовательности в этих методах задаётся рекуррентным равенством:

x k+1= x k + β k ∙ p k, (2)

где:

p k – вектор, задающий направление поиска из точки x k,

β k – величина шага.

Алгоритмы спуска различаются способами определения β k и p k .

Метод исчерпывающего спуска

Если в (2) величина шага β k выбирается путём решения задачи одномерной минимизации по β значения функции f(x k + β ∙ p k), то такой метод называется методом исчерпывающего спуска.

При использовании метода исчерпывающего спуска для определения шага β k используется

важное свойство этого метода (вытекающее из правила дифференцирования сложной функции):

(∇f(x k+1) , p k) = 0, (3)

смысл которого состоит в том, что на очередном шаге либо достигнута стационарная точка, в которой ∇f(x k+1) = 0, либо градиент в точке x k+1 перпендикулярен вектору p k.

Условием окончания расчёта может быть выполнение какого- либо из неравенств

| f(x k+1) - f(x k) | < ε , || ∇f(xk)|| < ε, ρ (x k+1, x k) < ε

где ε - заданная погрешность.

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

Направление вектора pk называется направлением убывания функции f(x0), если при достаточно малых значениях β выполняется неравенство

f(x k + β k ∙ p k) < f(x k ) (4)

Градиентом ∇f(x) непрерывно дифференцируемой функции n переменных f(x) называется вектор, элементами которого являются частные производные первого порядка

{∂f(x)/∂x1, ∂f(x)/∂x2, …, ∂f(x)/∂xn}.

Градиент указывает направление наискорейшего возрастания функции в данной точке. Отсюда вытекает, что неравенство (4) будет выполнено, если вектор p k удовлетворяет условию

(∇f(xk) , pk) < 0, (5)

Этому условию, очевидно, удовлетворяет вектор антиградиента

p k = -∇f(xk) (6)

при условии, что ∇f(xk) ≠ 0 (т.е. задача минимизации не решена).

Замечание. Вблизи точки минимума длина вектора – градиента становится малой, что может привести к замедлению сходимости метода. По этой причине вместо вектора антиградиента (6) можно использовать единичный вектор с таким же направлением

pk = -∇f(xk) / || ∇f(xk) ||.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

+ 87 = 90