Безусловная оптимизация. Метод сопряженных градиентов

Метод сопряженных градиентов (в англ. литературе «conjugate gradient method») - это итерационный численный метод (первого порядка) решения оптимизационных задач, который позволяет определить экстремум (минимум или максимум) целевой функции:

 - это значения аргумента функции (управляемые параметры) на вещественной области.

В соответствии с рассматриваемым методом экстремум (максимум или минимум) целевой функции определяют в направлении наиболее быстрого возрастания (убывания) функции, т.е. в направлении градиента (антиградиента) функции. Градиентом функции  в точке  называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам:

где i, j,…, n - единичные векторы, параллельные координатным осям.

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

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

где знак «+» используется для поиска максимума функции, а знак «-» используется для поиска минимума функции.

 - единичный вектор сопряженных направлений, который определяется по формуле:

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

В качестве первого способа рассматривают определение весового коэффициента по формуле Флетчера-Ривса (Fletcher–Reeves):

- модуль градиента определяет скорость возрастания или убывания функции в направлении градиента или антиградиента соответственно.

В качестве второго способа рассматривают определение весового коэффициента по формуле Полака–Райбера (Polak-Ribiere):

В соответствии с представленными  выражениями новое сопряженное направление получается сложением градиента (антиградиента) в точке поворота и предыдущего направления движения, умноженного на коэффициент. Таким образом, метод сопряженных градиентов формирует направление поиска к оптимальному значению используя информацию о поиске полученную на предыдущих этапах спуска. Следует отметить, что сопряженные направления P[0], P[1], ..., P[k-1] вычисляют с помощью формулы Флетчера-Ривса, которая позволяет построить сопряженные векторы относительно некоторой симметрической матрицы для произвольно заданной функции.

Траектория спуска в методе сопряженных градиентов (поиск минимума) (simenergy.ru)

Рис.1. Траектория спуска в методе сопряженных градиентов (поиск минимума)

Геометрический смысл метода сопряженных градиентов состоит в следующем: из заданной начальной точки х[0] осуществляется спуск в направлении р[0] (градиента или антиградиента) в новую точку х[1], в которой определяется вектор-градиент функции. Поскольку х[1] является точкой минимума функции в направлении р[0], то вектор-градиент функции в точке х[1] ортогонален вектору р[0]. Затем определяется вектор р[1] который ортогонален относительно некоторой симметрической матрицы вектору р[0]. В результате осуществляется спуск вдоль найденного направления в новую точку х[2].

Траектория движения к точке экстремума при использовании метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная) (simenergy.ru)

Рис.2. Траектория движения к точке экстремума при использовании метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная).

Следует отметить, что через каждые n + 1 шагов необходимо выполнять рестарт алгоритмической процедуры (n – размерность пространства поиска). Рестарт алгоритмической процедуры необходим, чтобы забыть последнее направление поиска и стартовать алгоритм заново в направлении скорейшего спуска.

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

Другими словами, величину шага  определяют при решении данного уравнения:

Поиск оптимального решения завершается в случае, когда на итерационном шаге расчета (несколько критериев):

- траектория поиска остается в малой окрестности текущей точки поиска:

- приращение целевой функции не меняется:

- градиент целевой функции в точке локального минимума обращается в нуль:

Метод сопряженных градиентов является методом первого порядка, но при этом обладает квадратичной скоростью сходимости, как Ньютоновские методы расчета. Метод градиента вместе с его многочисленными модификациями является распространенным и эффективным методом поиска оптимума исследуемых объектов. Недостатком градиентного поиска (так же и рассмотренных выше методов) является то, что при его использовании можно обнаружить только локальный экстремум функции. Для отыскания других локальных экстремумов необходимо производить поиск из других начальных точек.

Методика расчета

• 1 шаг: Определение аналитические выражения (в символьном виде) для вычисления градиента функции 

• 2 шаг: Задаем начальное приближение 

 

Далее выполняется итерационный процесс.

• 3 шаг: Определяется необходимость рестарта алгоритмической процедуры для обнуления последнего направления поиска. В результате рестарта  поиск осуществляется заново в направлении скорейшего спуска.

• 4 шаг: Вычисление координат единичного вектора  по формуле, полученной на шаге 1, и определение координат новой точки при движении по направлению единичного вектора как функция от шага расчета.

Вычисление весового коэффициента и единичного вектора сопряженных направлений на текущем шаге расчета (формула Флетчера-Ривса):

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

- для последующих шагов расчета  весовой коэффициент и единичный вектор сопряженных направлений вычисляются по следующим соотношениям:

• 5 шаг: определяем шаг расчета из условия поиска экстремума для следующей функции  (решения задачи одномерной оптимизации).

• 6 шаг: Определяем новые значения аргументов функции после выполнения k-го шага расчета:

где знак «+» используется для поиска максимума функции, а знак «-» используется для поиска минимума функции;

• 7 шаг: проверяем критерии останова итерационного процесса. Вычислительный процесс заканчивается, когда будет достигнута точка, в которой оценка градиента будет равна нулю (коэффициенты функции отклика становятся незначимыми). В противном случае возвращаемся к шагу 3 и продолжаем итерационный расчет.

Для того, чтобы добавить Ваш комментарий к статье, пожалуйста, зарегистрируйтесь на сайте.