Метод градиентного спуска
Многомерная оптимизация
Задачи многомерной минимизации, естественно, сложнее задач одномерной минимизации.
С увеличением числа переменных увеличивается объём вычислений, усложняются алгоритмы расчёта.
Разработано много различных методов решения задач многомерной оптимизации, которые можно разбить на три основных класса:
- методы прямого поиска (нулевого порядка), использующие только значения целевой функции,
- методы первого порядка, использующие значения целевой функции, а также значения её первых производных,
- методы второго порядка, использующие значения целевой функции и значения её первых и вторых производных.
В отличие от методов первого и второго порядков, методы прямого поиска менее обоснованы, но более просты в реализации.
Релаксационная последовательность. Методы спуска
Универсального метода, оптимального для решения всех задач оптимизации, не существует.
Во всех численных методах решения задач минимизации строится последовательность точек {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) ||.