Метод сопряженных градиентов — математический аппарат.

Метод сопряженных градиентов — математический аппарат

Термин “метод сопряженных градиентов” – один из примеров того, как бессмысленные словосочетания, став привычными, воспринимаются сами собой разумеющимися и не вызывают никакого недоумения. Дело в том, что, за исключением частного и не представляющего практического интереса случая, градиенты не являются сопряженными, а сопряженные направления не имеют ничего общего с градиентами. Название метода отражает тот факт, что данный метод отыскания безусловного экстремума сочетает в себе понятия градиента целевой функции и сопряженных направлений.

Несколько слов об обозначениях, используемых далее.

Скалярное произведение двух векторов записывается $x^Ty$ и представляет сумму скаляров: $sum_^n, x_i,y_i$. Заметим, что $x^Ty = y^Tx$. Если x и y ортогональны, то $x^Ty = 0$. В общем, выражения, которые преобразуются к матрице 1х1, такие как $x^Ty$ и $x^TA_x$, рассматриваются как скалярные величины.

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

где x – неизвестный вектор, b – известный вектор, а A – известная, квадратная, симметричная, положительно–определенная матрица. Решение этой системы эквивалентно нахождению минимума соответствующей квадратичной формы.
Квадратичная форма – это просто скаляр, квадратичная функция некого вектора x следующего вида:

Наличие такой связи между матрицей линейного преобразования A и скалярной функцией f(x) дает возможность проиллюстрировать некоторые формулы линейной алгебры интуитивно понятными рисунками. Например, матрица А называется положительно-определенной, если для любого ненулевого вектора x справедливо следующее:

На рисунке 1 изображено как выглядят квадратичные формы соответственно для положительно-определенной матрицы (а), отрицательно-определенной матрицы (b), положительно-неопределенной матрицы (с), неопределенной матрицы (d).

То есть, если матрица А – положительно-определенная, то вместо того, чтобы решать систему уравнений 1, можно найти минимум ее квадратичной функции. Причем, метод сопряженных градиентов сделает это за n или менее шагов, где n – размерность неизвестного вектора x. Так как любая гладкая функция в окрестностях точки своего минимума хорошо аппроксимируется квадратичной, этот же метод можно применить для минимизации и неквадратичных функций. При этом метод перестает быть конечным, а становится итеративным.

Рассмотрение метода сопряженных градиентов целесообразно начать с рассмотрения более простого метода поиска экстремума функции – метода наискорейшего спуска. На рисунке 2 изображена траектория движения в точку минимума методом наискорейшего спуска. Суть этого метода:

в начальной точке x(0) вычисляется градиент, и движение осуществляется в направлении антиградиента до тех пор, пока уменьшается целевая функция;
в точке, где функция перестает уменьшаться, опять вычисляется градиент, и спуск продолжается в новом направлении;
процесс повторяется до достижения точки минимума.

В данном случае каждое новое направление движения ортогонально предыдущему. Не существует ли более разумного способа выбора нового направления движения? Существует, и он называется метод сопряженных направлений. А метод сопряженных градиентов как раз относится к группе методов сопряженных направлений. На рисунке 3 изображена траектория движения в точку минимума при использовании метода сопряженных градиентов.

Определение сопряженности формулируется следующим образом: два вектора x и y называют А-сопряженными (или сопряженными по отношению к матрице А) или А–ортогональными, если скалярное произведение x и Ay равно нулю, то есть:

Сопряженность можно считать обобщением понятия ортогональности. Действительно, когда матрица А – единичная матрица, в соответствии с равенством 4, векторы x и y – ортогональны. Можно и иначе продемонстрировать взаимосвязь понятий ортогональности и сопряженности: мысленно растяните рисунок 3 таким образом, чтобы линии равного уровня из эллипсов превратились в окружности, при этом сопряженные направления станут просто ортогональными.

Остается выяснить, каким образом вычислять сопряженные направления. Один из возможных способов – использовать методы линейной алгебры, в частности, процесс ортогонализации Грамма–Шмидта. Но для этого необходимо знать матрицу А, поэтому для большинства задач (например, обучение многослойных нейросетей) этот метод не годится. К счастью, существуют другие, итеративные способы вычисления сопряженного направления, самый известный – формула Флетчера-Ривса:

Формула 5 означает, что новое сопряженное направление получается сложением антиградиента в точке поворота и предыдущего направления движения, умноженного на коэффициент, вычисленный по формуле 6. Направления, вычисленные по формуле 5, оказываются сопряженными, если минимизируемая функция задана в форме 2. То есть для квадратичных функций метод сопряженных градиентов находит минимум за n шагов (n – размерность пространства поиска). Для функций общего вида алгоритм перестает быть конечным и становится итеративным. При этом, Флетчер и Ривс предлагают возобновлять алгоритмическую процедуру через каждые n + 1 шагов.

Можно привести еще одну формулу для определения сопряженного направления, формула Полака–Райбера (Polak-Ribiere):

Метод Флетчера-Ривса сходится, если начальная точка достаточно близка к требуемому минимуму, тогда как метод Полака-Райбера может в редких случаях бесконечно циклиться . Однако последний часто сходится быстрее первого метода. К счастью, сходимость метода Полака-Райбера может быть гарантирована выбором $beta = max $. Это эквивалентно рестарту алгорима по условию $beta leq 0$. Рестарт алгоритмической процедуры необходим, чтобы забыть последнее направление поиска и стартовать алгоритм заново в направлении скорейшего спуска.

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

₍₀₎

Осуществляется спуск в вычисленном направлении пока функция уменьшается, иными словами, поиск a_(i), который минимизирует

Переход в точку, найденную в предыдущем пункте

Вычисление антиградиента в этой точке

Вычисления по формуле 6 или 7. Чтобы осуществить рестарт алгоритма, то есть забыть последнее направление поиска и стартовать алгоритм заново в направлении скорейшего спуска, для формулы Флетчера–Ривса присваивается 0 через каждые n + 1 шагов, для формулы Полака-Райбера – $beta_ <(i+1)>= max ,,0>$

Читать еще: Лучшие игры гта на андроид. GTA-подобные игры

Вычисление нового сопряженного направления

Из приведенного алгоритма следует, что на шаге 2 осуществляется одномерная минимизация функции. Для этого, в частности, можно воспользоваться методом Фибоначчи, методом золотого сечения или методом бисекций. Более быструю сходимость обеспечивает метод Ньютона–Рафсона, но для этого необходимо иметь возможность вычисления матрицы Гессе. В последнем случае, переменная, по которой осуществляется оптимизация, вычисляется на каждом шаге итерации по формуле:

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

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

В заключение приведем один из возможных алгоритмов программной реализации метода сопряженных градиентов. Сопряженность в данном случае вычисляется по формуле Флетчера–Ривса, а для одномерной оптимизации используется один из вышеперечисленных методов. По мнению некоторых авторитетных специалистов скорость сходимости алгоритма мало зависит от оптимизационной формулы, применяемой на шаге 2 приведенного выше алгоритма, поэтому можно рекомендовать, например, метод золотого сечения, который не требует вычисления производных.

Вариант метода сопряженных направлений, использующий формулу Флетчера-Ривса для расчета сопряженных направлений.

r := -f'(x) // антиградиент целевой функции

d := r // начальное направление спуска совпадает с антиградиентом

Sigma_new : = r T * r // квадрат модуля антиградиента

// Цикл поиска (выход по счетчику или ошибке)
while i Eps 2 * Sigma
begin
j : = 0
Sigma_d : = d T * d

// Цикл одномерной минимизации (спуск по направлению d)
repeat
a : =
x : = x + a
j : = j + 1
until (j >= j_max) or (a 2 * Sigma_d 2 )

r : = -f'(x) // антиградиент целевой функции в новой точке
Sigma_old : = Sigma_new
Sigma_new : = r T * r
beta : = Sigma_new / Sigma_old
d : = r + beta * d // Вычисление сопряженного направления
k : = k + 1

if (k = n) or (r T * d

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

Метод сопряжённых градиентов

Материал из MachineLearning.

Содержание

Введение

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

Постановка задачи оптимизации

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

Если , то задача оптимизации называется безусловной (unconstrained). Если , то задача оптимизации называется условной (constrained).

Метод сопряжённых градиентов для квадратичного функционала

Изложение метода

Рассмотрим следующую задачу оптимизации:

Здесь – симметричная положительно определённая матрица размера . Такая задача оптимизации называется квадратичной. Заметим, что . Условие экстремума функции эквивалентно системе Функция достигает своей нижней грани в единственной точке , определяемой уравнением . Таким образом, данная задача оптимизации сводится к решению системы линейных уравнений
Идея метода сопряжённых градиентов состоит в следующем:
Пусть – базис в . Тогда для любой точки вектор раскладывается по базису Таким образом, представимо в виде

Каждое следующее приближение вычисляется по формуле:

Определение. Два вектора и называются сопряжёнными относительно симметричной матрицы B, если

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

Базисные вектора вычисляются по формулам:

Коэффициенты выбираются так, чтобы векторы и были сопряжёнными относительно А.

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

Анализ метода

Для метода сопряжённых градиентов справедлива следующая теорема:
Теорема Пусть , где – симметричная положительно определённая матрица размера . Тогда метод сопряжённых градиентов сходится не более чем за шагов и справедливы следующие соотношения:

Сходимость метода

Если все вычисления точные, и исходные данные точны то метод сходится к решению системы не более чем за итераций, где – размерность системы. Более тонкий анализ показывает, что число итераций не превышает , где – число различных собственных значений матрицы A. Для оценки скорости сходимости верна следующая (довольно грубая) оценка:

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

Вычислительная сложность

На каждой итерации метода выполняется операций. Такое количество операций требуется для вычисления произведения – это самая трудоёмкая процедура на каждой итерации. Отальные вычисления требуют O(n) операций. Суммарная вычислительная сложность метода не превышает – так как число итераций не больше n.

Читать еще: Ребра свинные. Свиные ребрышки – рецепты самых сочных и ароматных блюд

Численный пример

Применим метод сопряжённых градиентов для решения системы , где

C помощью метода сопряжённых градиентов решение этой системы получается за две итерации. Собственные числа матрицы – 5, 5, -5 – среди них два различных, поэтому, согласно теоретической оценке число итераций не могло превышать двух

Заключение

Метод сопряжённых градиентов – один из наиболее эффективных методов решения СЛАУ с положительно определённой матрицей. Метод гарантирует сходимость за конечное число шагов, а нужная точность может быть достигнута значительно раньше. Основная проблема заключается в том, что из-за накопления погрешностей может нарушаться ортогональность базисных веторов , что ухудшает сходимость

Метод сопряжённых градиентов в общем случае

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

– непрерывно дифференцируемая в функция. Чтобы модифицировать метод сопряжённых градиентов для решения этой задачи необходимо получить для формулы, в которые не входит матрица А:

можно вычислять по одной из трёх формул:

– Метод Флетчера – Ривса (Fletcher–Reeves method)
– Метод Полака – Райбера (Polak–Ribi`ere method)

Если функция – квадратичная и строго выпуклая, то все три формулы дают одинаковый результат. Если – произвольная функция, то каждой из формул cоответствует своя модификация метода сопряжённых градиентов. Третья формула используется редко, так как она требует, чтобы функция и вычисления гессиана функции на каждом шаге метода.

Анализ метода

Если функция – не квадратичная, метод сопряжённых градиентов может и не сходиться за конечное число шагов. Кроме того, точное вычисление на каждом шаге возможно только в редких случаях. Поэтому накопление погрешностей приводит к тому, что вектора перестают указывать направление убывания функции . Тогда на каком-то шаге полагают . Совокупность всех номеров , при которых принимается , обозначим за . Номера называются моментами обновления метода. На практике часто выбирают , где – размерность пространства.

Сходимость метода

Для метода Флетчера – Ривса существует теорема о сходимости, накладывающая не слишком жёсткие условия на минимизируемую функцию :
Теорема.
Пусть и выполняются следующие условия:

удовлетворяет строгим условиям Вольфа:
2. где
Множество ограничено
Производная удовлетворяет условию Липшица с константой в некоторой окрестности

множества M: .
Тогда

Для метода Полака-Райбера доказана сходимость в предположении, что – строго выпуклая функция. В общем случае доказать сходимость метода Полака – Райбера невозможно. Напоротив, верна следующая теорема:
Теорема.
Предположим, что в методе Полака-Райбера значения на каждом шаге вычисляются точно. Тогда существует функция , и начальное приближение , такие что 0, forall k = 0, 1, 2, . quad ||f(x_k)|| > delta” alt= “exists delta > 0, forall k = 0, 1, 2, . quad ||f(x_k)|| > delta” />.

Тем не менее, на практике метод Полака-Райбера работает лучше.
Наиболее распространённые критерии останова на практике: Норма градиента становится меньше некоторого порога
Значение функции в течении m последовательных итераций почти не изменилось

Вычислительная сложность

На каждой итерации методов Полака-Райбера или Флетчера-Ривса по одному разу вычисляются функция и её градиент , решается задача одномерной оптимизации . Таким образом, сложность одного шага метода сопряжённых градиентов имеет тот же порядок, что и сложность шага метода скорейшего спуска. На практике метод сопряжённых градиентов показывает лучшую скорость сходимости.

Числовой пример

Будем искать методом сопряжённых градиентов минимум функции . Минимум этой функции равен 1 и достигается в точке (5, 4). Сравним на примере этой функции методы Полака-Райбера и Флетчера-Ривса. Итерации в обоих методах прекращаются, когда на текущем шаге квадрат нормы градиента становится меньше $\vareps$ . Для выбора используется метод золотого сечения

Заключение

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

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

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

Читать еще: Правление царя соломона. Царь Соломон: биография, приход к власти, символика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источники:

http://basegroup.ru/community/articles/conjugate

http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%81%D0%BE%D0%BF%D1%80%D1%8F%D0%B6%D1%91%D0%BD%D0%BD%D1%8B%D1%85_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BE%D0%B2

http://simenergy.ru/math-analysis/solution-methods/90-conjugate-gradient

Метод сопряженных градиентов — математический аппарат.