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

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

f(x) = (х, Нх) + (b, х) + а

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

По определению, два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x, Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером пхп.

Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x[k]) в направление p[k], H-сопряженное с ранее найденными направлениями р, р, ..., р. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.

Направления р[k] вычисляют по формулам:

p[k] = -f’(x[k])+k-1p, k >= 1; p = -f’(x).

Величины k-1 выбираются так, чтобы направления p[k], р были H-сопряженными:

(p[k], Hp)= 0.

В результате для квадратичной функции

итерационный процесс минимизации имеет вид

x =x[k] +akp[k],

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

f(х[k] + аkр[k]) = f(x[k] + ар [k]).

Для квадратичной функции

Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.

1. В точке х вычисляется p = -f’(x).

2. На k-м шаге по приведенным выше формулам определяются шаг аk. и точка х.

3. Вычисляются величины f(x) и f’(x).

4. Если f’(x) = 0, то точка х является точкой минимума функции f(х). В противном случае определяется новое направление p из соотношения

и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+1)-й итерации процедуры 1-4 циклически повторяются с заменой х на х[п+1] , а вычисления заканчиваются при , где - заданное число. При этом применяют следующую модификацию метода:

x = x[k] +akp[k],

p[k] = -f’(x[k])+k-1p, k >= 1;

f(х[k] + akp[k]) = f(x[k] + ap[k];

Здесь I- множество индексов: I = {0, n, 2п, Зп, ...}, т. е. обновление метода происходит через каждые п шагов.

Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 1.19). Из заданной начальной точки х осуществляется спуск в направлении р = -f"(x). В точке х определяется вектор-градиент f"(x ). Поскольку х является точкой минимума функции в направлении р, то f’(х) ортогонален вектору р. Затем отыскивается вектор р , H-сопряженный к р . Далее отыскивается минимум функции вдоль направления р и т. д.

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

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

Численные методы безусловной оптимизации второго порядка, варианты алгоритмов метода Ньютона

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

Необходимым условием экстремума функции многих переменных f(x) в точке х* является равенство нулю ее градиента в этой точке:

Разложение f’(х) в окрестности точки х[k] в ряд Тейлора с точностью до членов первого порядка позволяет переписать предыдущее уравнение в виде

f"(x) f’(x[k]) + f"(x[k]) (х - х[k]) 0.

Здесь f"(x[k]) Н(х[k]) - матрица вторых производных (матрица Гессе) минимизируемой функции. Следовательно, итерационный процесс для построения последовательных приближений к решению задачи минимизации функции f(x) описывается выражением

x x[k] - H-1(x[k]) f’(x[k]) ,

где H-1(x[k]) - обратная матрица для матрицы Гессе, а H-1(x[k])f’(x[k]) р[k] - направление спуска.

Полученный метод минимизации называют методом Ньютона. Очевидно, что в данном методе величина шага вдоль направления р[k] полагается равной единице. Последовательность точек {х[k]}, получаемая в результате применения итерационного процесса, при определенных предположениях сходится к некоторой стационарной точке х* функции f(x). Если матрица Гессе Н(х*) положительно определена, точка х* будет точкой строгого локального минимума функции f(x). Последовательность x[k] сходится к точке х* только в том случае, когда матрица Гессе целевой функции положительно определена на каждой итерации.

Если функция f(x) является квадратичной, то, независимо от начального приближения х и степени овражности, с помощью метода Ньютона ее минимум находится за один шаг. Это объясняется тем, что направление спуска р[k] H-1(x[k])f’(x[k]) в любых точках х всегда совпадает с направлением в точку минимума х*. Если же функция f(x) не квадратичная, но выпуклая, метод Ньютона гарантирует ее монотонное убывание от итерации к итерации. При минимизации овражных функций скорость сходимости метода Ньютона более высока по сравнению с градиентными методами. В таком случае вектор р[k] не указывает направление в точку минимума функции f(x), однако имеет большую составляющую вдоль оси оврага и значительно ближе к направлению на минимум, чем антиградиент.

Существенным недостатком метода Ньютона является зависимость сходимости для невыпуклых функций от начального приближения х. Если х находится достаточно далеко от точки минимума, то метод может расходиться, т. е. при проведении итерации каждая следующая точка будет более удаленной от точки минимума, чем предыдущая. Сходимость метода, независимо от начального приближения, обеспечивается выбором не только направления спуска р[k] H-1(x[k])f’(x[k]), но и величины шага а вдоль этого направления. Соответствующий алгоритм называют методом Ньютона с регулировкой шага. Итерационный процесс в таком случае определяется выражением

x x[k] - akH-1(x[k])f’(x[k]).

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

f(x[k] – ak H-1(x[k])f’(x[k]) (f(x[k] - aH-1(x[k])f’(x[k])).

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

Рис. 1.20. Геометрическая интерпретация метода Ньютона-Рафсона

Алгоритм метода Ньютона-Рафсона состоит в следующем. Часть действий выполняется до начала итерационного процесса. А именно необходимо получить вектор формул, составляющих градиент f’([x]) (т.е. вектор первых частных производных) и матрицу формул, составляющих матрицу Гессе H(x) (т.е. матрицу вторых частных производных). Далее в итерационном цикле в эти формулы подставляются значения компонент вектора х и эти массивы становятся массивами чисел.

1. В начальной точке х вычисляется вектор, определяющий направление спуска p - H-1(x)f’(). Тем самым задача многомерная сводится к задаче одномерной оптимизации.

2. На k-й итерации определяется шаг аk (по схеме, изображенной на рис. 1.20, для этого решается задача одномерной оптимизации) и точка х.

3. Вычисляется величина f(х).

4. Проверяются условия выхода из подпрограммы, реализующей данный алгоритм. Эти условия аналогичны условиям выхода из подпрограммы при методе наискорейшего спуска. Если эти условия выполняются, осуществляется прекращение вычислений. В противном случае вычисляется новое направление

р –H-1(x[k])f’([k])

и осуществляется переход к следующей итерации, т. е. на шаг 2.

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

В ряде случаев целесообразно комбинированное использование градиентных методов и метода Ньютона. В начале процесса минимизации, когда точка х находится далеко от точки экстремума х*, можно применять какой-либо вариант градиентных методов. Далее, при уменьшении скорости сходимости градиентного метода можно перейти к методу Ньютона. Или вследствие накопления ошибок в процессе счета матрица Гессе на некоторой итерации может оказаться отрицательно определенной или ее нельзя будет обратить. В таких случаях в подпрограммах оптимизации полагается H-1(x[k]) Е, где Е - единичная матрица. Итерация при этом осуществляется по методу наискорейшего спуска.

В другой модификации метода Ньютона, получившей название метод Левенберга - Маркардта (метод Ньютона с регулировкой матрицы) для обеспечения положительной определенности матрицы Гессе в точках последовательности используется регуляризация этой матрицы. В методе Левенберга - Маркардта точки строятся по закону: , где - последовательность положительных чисел, обеспечивающих положительную определенность матрицы . Обычно в качестве берется значение на порядок больше наибольшего элемента матрицы . Так в ряде стандартных программ полагается . Если, то , в противном случае Очевидно, что если , то метод Левенберга - Маркардта представляет собой метод Ньютона, а если велико, то поскольку при больших метод Левенберга - Маркардта близок к градиентному методу. Поэтому, подбирая значения параметра , можно добиться, чтобы метод Левенберга - Маркардта сходился

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

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

Алгоритм получается таким (модификация I):

А. Начальный шаг.

1) Находится градиент функции в произвольной точке ;

2) полагается ;

3) находится точка , доставляющая максимум функции на прямой ( – параметр).

Б. Общий шаг. Пусть уже найдены точки .

1) находится градиент функции в точке .

2) полагается

В. Останов алгоритма. Процесс обрывается в тот момент, когда градиент обратится в нуль, т. е. достигается максимум на всем пространстве .

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

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

Чтобы придать алгоритму более «конструктивную» форму, найдем формулу, определяющую точку максимума квадратичной формы на прямой .

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

где – градиент в точке . Максимизируя по , получим

и соответственно

. (16.16)

Таким образом, вычисление в пункте 3) алгоритма может быть осуществлено по формуле

.

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

Рассмотрим систему векторов , коллинеарных соответственно векторам (т. е. при некоторых действительных ). Для векторов и сохраняется условие -ортогональности

При . (16.17)

Кроме того, из (16.11) следует, что

При . (16.18)

Наконец, остается в силе соотношение типа (16.9)

. (16.19)

Умножая правую и левую части (16.19) на и учитывая (16.17) и (16.18), получим при

откуда при . При получим

. (16.20)

Соотношение (16.20) определяет с точностью до произвольного множителя через и ц. При выводе (16.20) использовались лишь соотношения (16.17), (16.18), (16.19). Поэтому процесс построения векторов может рассматриваться как процесс -ортогонализации векторов .

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

А. Начальный шаг, такой же как и в модификации I.

Б. Пусть уже найдены точка и направление .

1) Находится градиент функции в точке ;

2) полагается

,

; (16.21)

3) находится точка , доставляющая условный максимум на прямой

по формуле

. (16.22)

Формулы (16.21) и (16.22) могут быть преобразованы. Так, полагая

имеем из (16.22)

,

откуда получаем, применяя (16.12),

. (16.23)

С другой стороны, поскольку

из (16.21) имеем

и, таким образом,

Наконец, из (16.21), (16.23) и (16.24) получаем

.

Таким образом, формулы (16.21) и (16.22) могут быть записаны в виде

,

. (16.26)

Совпадение результатов действия по формулам (16.21) и (16.22), с одной стороны, и (16.25), (16.26), с другой, может служить критерием правильности вычислений.

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

При этом пункт 1) алгоритма может быть выполнен без изменений, пункт 2) должен выполняться по формуле (16.25), поскольку в эту формулу не входит явно матрица , а пункт 3), нахождение условного максимума на прямой, может быть выполнен одним из известных способов, например, методом Фибоначчи. Применение метода сопряженных градиентов дает обычно значительно более быструю сходимость к максимуму по сравнению с методами наискорейшего спуска, Гаусса – Зайделя и др.

4. Что будет, если применить метод сопряженных градиентов для максимизации квадратичной формы с положительно полуопределенной формой ?

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

,

где все и некоторые из . При этом функция имеет максимум, если выполнено условие: когда , то и . Легко видеть, что максимум в этом случае достигается на целом гиперпространстве. А именно, пусть, например, при , меняющемся от 1 до , , а при , меняющемся от до , и . Тогда максимум достигается в точках с координатами при и с произвольными значениями при . Они образуют гиперпространство размерности .

Если же при некоторых , a , то функция не имеет максимума и возрастает неограниченно. В самом деле, пусть, например, и ; тогда, если положить при и устремить к , то, очевидно, и будет возрастать до бесконечности.

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

В исходной системе координат функция имеет вид

,

причем матрица вырождена и имеет ранг . При этом, как и раньше, обращение градиента в нуль есть критерий достижения максимума, а ортогональность градиента гиперпространству – критерий условного экстремума на гиперпространстве.

Рассмотрим применение метода сопряженных градиентов в форме II в этом случае. Здесь приходится изменить условие остановки, т. е. теперь возможно, что при вычислении длины шага

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

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

Следовательно, останов обязательно произойдет при .

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

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

Скалярное произведение двух векторов записывается $x^Ty$ и представляет сумму скаляров: $\sum_{i=1}^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 следующего вида:

$f\,(x) = (\frac{1}{2})\,x^TA_x\,-\,b^Tx\,+\,c$, (2)

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

$x^TA_x\,>\,0$, (3)

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

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

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

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

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

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

$x^TA_y\,=\,0$, (4)

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

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

$d_{(i+1)} = d_{(i+1)}\,+\,\beta_{(i+1)}\,d_i$ , (5)

$\beta_{(i+1)} = \frac{r_{(i+1)}^T}{r_{i}^T}\,\frac{r_{(i+1)}}{r_{(i)}}$, (6)

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

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

$\beta_{(i+1)} = \frac{r_{(i+1)}^T\,(r_{(i+1)}\,-\,r_{(i)})}{r_{i}^T\,r_{(i)}}$, (7)

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

1. Вычисляется антиградиент в произвольной точке x (0) .
   

   $d_{(0)} = r_{(0)} = -\,f"(x_{(0)})$

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

   $f\,(x_{(i)}\,+\,a_{(i)}\,d_{(i)})$

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

   $x_{(i+1)} = x_{(i)}\,+\,a_{(i)}\,d_{(i)}$

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

   $r_{(i+1)} = -\,f"(x_{(i+1)})$

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

   $d_{(i+1)} = r_{(i+1)}\,+\,\beta_{(i+1)}\,d_{(i)}$

7. Переход на пункт 2.

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

$$a = -\,\frac{{f"}^T\,(x)\,d}{d^T\,f""(x)\,d}$$

$f""(x)\,= \begin{pmatrix} \frac{\partial^2\,f}{\partial x_1\,\partial x_1}&\frac{\partial^2\,f}{\partial x_1\,\partial x_2}&\cdots&\frac{\partial^2\,f}{\partial x_1\,\partial x_n}& \\ \frac{\partial^2\,f}{\partial x_2\,\partial x_1}&\frac{\partial^2\,f}{\partial x_2\,\partial x_2}& \cdots&\frac{\partial^2\,f}{\partial x_2\,\partial x_n}& \\ \vdots&\vdots&\ddots&\vdots &\\ \frac{\partial^2\,f}{\partial x_n\,\partial x_1}& \frac{\partial^2\,f}{\partial x_n\,\partial x_2}&\cdots&\frac{\partial^2\,f}{\partial x_n\,\partial x_n} \end{pmatrix}$
Матрица Гессе

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

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

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

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

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

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

Sigma 0: = Sigma new

// Цикл поиска (выход по счетчику или ошибке)
while i < i max and Sigma new > Eps 2 * Sigma 0
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 <= Eps 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 <= 0) then // Рестарт алгоритма
begin
d: = r
k: = 0
end

I: = i + 1
end

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

Литература

• Н.Н.Моисеев, Ю.П.Иванилов, Е.М.Столярова "Методы оптимизации", М. Наука, 1978
• А.Фиакко, Г.Мак-Кормик "Нелинейное программирование", М. Мир, 1972
• У.И.Зангвилл "Нелинейное программирование", М. Советское радио, 1973
• Jonathan Richard Shewchuk "Second order gradients methods", School of Computer Science Carnegie Mellon University Pittsburg, 1994

Далее будет изложен метод сопряженных градиентов, относящейся к группе методов сопряженных направлений. Этот метод как и метод градиентного спуска, является методом первого порядка т. е. Использует информацию только первой производной минимизируемой функции.

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

Два вектора x и y называют Н - сопряженными (или сопряженными по отношению к матрице Н) или Н - ортогональными, если

(x, H·y) = 0. (9)

f (x) = a + (x,b) + ½ (x, H·x). (10)

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

Чтобы воспользоваться этим методом минимизации квадратичной функции (10) нужно знать n - взаимно сопряженных направлений S 0 , S 1 ,…,S n-1 . Эффективность таких направлений – самостоятельная проблема. Существует много взаимно сопряженных направлений S 0 , S 1 ,…,S n-1 и способов их построения. Ниже излагается метод сопряженных градиентов Флетчера - Ривса, в котором выбор Н - сопряженных направлений осуществляется совместно с одномерной минимизацией f (х) по α..

Метод Флетчера – Ривса.

Этот метод использует последовательность направлений поиска, каждая из которых является линейной комбинацией антиградиента в текущей точке и предыдущего направления спуска. Метод изменяется к квадратичной целевой функции f (x) = a + (x,b) + ½ (x, H·x).

При минимизации ее методом Флетчера - Ривса векторы S k вычисляются по формулам

S 0 = – f " (x 0), S k = – f "(x k) + β k-1 ·S k-1 , при k ≥ 1.

Величины β k-1 выбираются так, чтобы направления S k , S k-1 были Н – сопряженными.

Точка х k-1 ,определяется в результате минимизации функции f (х) в направлении S k , исходящем из точки x k , т.е.

х k+1 = x k + α k ·S k , где α k доставляет минимум по α k функции f (x k , α ·S k).

Итак, предлагаемая процедура минимизации функции f (x) выглядит следующим образом. В заданной точке x 0 вычисляется антиградиент

S 0 = – f " (x 0). Осуществляется одномерная минимизация в этом направлении и определяется точка x 1 . В точке x 1 сново вычисляется антиградиент – f " (x 1). Так как эта точка доставляет минимум функции f (x) вдоль направления S 0 = – f " (x 0), вектор f " (x 1) ортогонален f " (x 0). Затем по известному значению f " (x 1) по формуле (11) вычисляется вектор S 1 , который за счет выбора β 0 будет Н – сопряженным к S 0 . Далее отыскивается минимум функции f (х) вдоль направления S 1 и т.д.

шаг 4:

Это и есть окончательный вид алгоритма Флетчера-Ривса.

Как было замечено ранее, он найдет минимум квадратичной функции не более чем за n шагов.

Минимизация неквадратичной целевой функции.

Метод Флетчера-Ривса может применятся для минимизации и неквадратичных функций. Он является методом первого порядка и в тоже время скорость его сходимости квадратична. Разумеется, если целевая функция не квадратична, метод уже не будет конечным. Поэтому после (n+1)-й итерации процедура повторяется с заменой x 0 на x n +1 , а счет заканчивается при ||f "(x k+1)|| £ ε, где ε – заданное число. При минимизации неквадратичных функций обычно применяется следующая модификация метода Флетчера-Ривса.

Схема алгоритма для неквадратичных целевых функций.

Здесь I – множество индексов, I = {0, n, 2n, 3n, …}. Значения k, для которых β k = 0, называют моментами обновления метода. Таким образом, обновление метода происходит через каждые n шагов.

Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме Метод сопряженных градиентов:

1. 26. Отыскание экстремумов функций многих переменных. метод сопряженных градиентов, метод переменных направлений, метод переменной метрики.

В предыдущих подразделах рассматривались методы Коши и Ньютона. Отмечалось, что метод Коши эффективен при поиске на значительных расстояниях от точки минимума х* и плохо «работает» в окрестности этой точки, тогда как метод Ньютона не отличается высокой надежностью при поиске х* из удаленной точки, однако оказывается весьма эффективным в тех случаях, когда x (k) находится вблизи точки минимума. В этом и последующих подраз­делах рассматриваются методы, которые обладают положительны­ми свойствами методов Коши и Ньютона и основаны на вычислении значений только первых производных. Таким образом, эти методы, с одной стороны, отличаются высокой надежностью при поиске х* из удаленной точки х* и, с другой стороны, быстро сходятся в окрестности точки минимума.

Методы, позволяющие получать решения задач с квадратичными целевыми функциями приблизительно за N шагов при условии использования недесятичных дробей, будем называть квадратично сходящимися. Среди таких методов можно выделить класс алгоритмов, в основе которых лежит построение сопряженных направлений. Выше было сформулировано условие сопряженности для системы направлений s (k) , k = 1, 2, 3,…, r ≤ N, и симметрической матрицы С порядка N N. Была также установлена связь между построением указанных направлений и преобразованием произвольной квадратичной функции к виду суммы полных

1) Задачи такого типа возникают, например, в регрессионном анализе - Прим. перев.

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

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

f(x) = q(x) = C x + b = g(x) (3.60)

Обозначение g(x) введено здесь для удобства записи формулы. Таким образом,

g (x (0)) = C x (0) + b ,

g (x (1)) = C x (1) + b .

Запишем изменение градиента при переходе от точки х (0) к точке х (1) :

g(x) = g (x (1)) – g (x (0)) = C (x (1) - x (0)), (3.61)

g(x) = C x

Равенство (3.61) выражает свойство квадратичных функций, которое будет использовано ниже.

В 1952 г. Эстенс и Штифель предложили эффективный итерационный алгоритм для решения систем линейных уравнений, который по существу представлял собой метод сопряженных градиентов. Они рассматривали левые части линейных уравнений как компоненты градиента квадратичной функции и решали задачу минимизации этой функции. Позже Флетчер и Ривс обосновали квадратичную сходимость метода и обобщили его для случая неквадратичных функций. Фрид и Метцлер продемонстрировали (допустив, однако, некоторые неточности) возможности использования метода для решения линейных систем с разреженной матрицей коэффициентов. (Определение разреженной матрицы см. в приложении А.) Они подчеркнули простоту реализации метода по сравнению с другими, более общими алгоритмами, что является особенно важной характеристикой с позиций нашего изложения.

Рассмотрение метода будем проводить в предположении, что "целевая функция является квадратичной:

f(x) = q(x) = a + b T x + ½ x T C x ,

аитерации проводятся по формуле (3.42), т.е.

x = x + α s(x ) .

Направления поиска на каждой итерации определяются с помощью следующих формул:

s (k) = – g (k) + (3.62)

s (0) = –g (0) , (3.63)

где g (k) = f (x ). Так как после определения системы направлений проводится последовательный поиск вдоль каждого из направлений, полезно напомнить, что в качестве критерия окончания одномерного поиска обычно используется условие

f (x ) T s (k) = 0 (3.64)

Значения , i = 1, 2, 3,...,k - 1 ,выбираются таким образом, чтобы направление s (k) было С -сопряжено со всеми построенными ранее направлениями поиска. Рассмотрим первое направление

s (1) = –g (1) + γ (0) s (0) = –g (1) –γ (0) g (0)

и наложим условие его сопряженности с s (0)

s (1)T C s (0) = 0,

откуда T C s (0) = 0.

На начальной итерации

s (0) = ;

следовательно,

T C = 0

Используя свойство квадратичных функций (3.61), получаем

T g = 0, (3.65)

γ (0) = – ( g T g (1))/( g T g (0)). (3.66)

Из уравнения (3.65) следует, что

g (1)T g (1) + γ (0) g (0)T g (1) – g (1) T g (0) – γ (0) g (0)T g (0) = 0.

При соответствующем выборе α (0) и с учетом формулы (3.64) имеем

g (1) T g (0) = 0.

Таким образом,

s (2) = –g (2) + γ (0) s (0) + γ (1) s (1) .

и выберем γ (0) γ (1) таким образом, чтобы выполнялись условия

s (2) T C s (0) = 0 и s (2) C s (1) = 0,

т. е. условия С -сопряженности направления s (2) с направлениями s (0) и s (1) . С помощью формул (3.61) и (3.64) можно показать (это предоставляется читателю в качестве упражнения), что здесь γ (0) = 0, а в общем случае γ ( i ) = 0, i = 0, 1, 2,...,k-2, при любом значении k. Отсюда следует, что общая формула для направлений поиска может быть записана в виде, предложенном Флетчером и Ривсом:

s (k ) = –g (k ) + s (3.68)

Если f(x) - квадратичная функция, для нахождения точки минимума требуется определить N -1 таких направлений и провести N поисков вдоль прямой (при отсутствии ошибок округления). Если же функция f(х) не является квадратичной, количество направлений и соответствующих поисков возрастает.

Некоторые исследователи на основе опыта проведения вычислительных экспериментов предлагают после реализации каждой серии из N или N + 1 шагов возвращаться к начальной итерации алгоритма, положив s(x) = -g(x). Это предложение остается предметом для изучения, поскольку при минимизации функций общего вида в ряде случаев влечет за собой замедление сходимости. С другой стороны, циклические переходы к начальной итерации повы­шают надежность алгоритма, так как вероятность построения линейно зависимых направлений уменьшается. Если полученное на­правление оказывается линейной комбинацией одного или нескольких полученных ранее направлений, то метод может не привести к получению решения, поскольку поиск в соответствующем подпространстве R N уже проводился. Однако следует отметить, что на практике такие ситуации встречаются достаточно редко. Метод оказывается весьма эффективным при решении практических задач, характеризуется простотой однопараметрической вычислительной схемы и небольшим объемом памяти ЭВМ, необходимым для проведения поиска. Относительно невысокий уровень требований к объему памяти ЭВМ делает метод Флетчера - Ривса (ФР) и его модификации особенно полезным при решении задач большой размерности.

Пример 3.9. Метод Флетчера - Ривса

Найти точку минимума функции

f(x) = 4x + 3x – 4x x + x

если x = T .

Шаг 1. f(x) = T ,

s (0) = – f (x (0)) = – T .

Шаг 2.Поиск вдоль прямой:

x = x – α f (x (0)) → α = ⅛,

x = T – ⅛ T = [– ⅛, 0] T

Шаг 3.k = 1.

s (1) = – T – [¼, 1] T = [– ¼, ½] T .

Шаг 4.Поиск вдоль прямой:

x = x + α s (1) → α = ¼,

x = [– ⅛, 0] T – ¼ [¼, ½] T = [– , ] T ,

f (x (2)) = T .

Таким образом, x = х*. Решение получено в результате проведения двух одномерных поисков, поскольку целевая функция квадратичная, а ошибки округления отсутствуют.

Миль и Кентрелл обобщили подход Флетчера и Ривса, предложив формулу

x = x + α {– f (x (k )) + γ s (x )} (3.69)

где α и γ - параметры, значения которых определяются на каждой итерации. Этот метод, известный как градиентный метод с памятью ,очень эффективен по числу необходимых для решения задачи итераций, но требует большего количества вычислений зна­чений функции и компонент градиента, чем метод Флетчера - Ривса. Поэтому алгоритм Миля и Кентрелла оказывается полезным лишь в тех случаях, когда оценивание значений целевой функции и компонент градиента не связано с какими-либо трудностями.

Напомним, что рассмотрение метода Флетчера - Ривса прово­дилось в предположении квадратичности целевой функции и отсутствия ошибок округления в процессе поиска вдоль прямой. Од­нако при реализации ряда методов сопряженные направления определяются без учета одного из указанных предположений (или даже обоих предположений). Среди таких методов наибольшего внима­ния, по-видимому, заслуживает метод, разработанный Ползком и Рибьером в 1969 г. Метод основан на точной процедуре проведения поиска вдоль прямой и на более общем предположении об аппроксимации целевой функции. При этом

γ = , (3.70)

где, как и прежде,

g (x )= g (x ) – g (x ). (3.71)

Если α - параметр, значение которого определяется в результате поиска вдоль прямой, и γ - параметр, значение которого вычисляется по формуле (3.70), то метод сопряженных градиентов Полака - Рибьера реализуется с помощью следующих соотношений:

x = x + α s (x ),

s (x ) = – f (x ) + γ s (x ). (3.72)

Легко видеть, что единственное различие между методами Полака - Рибьера и Флетчера - Ривса заключается в способах выбора параметра γ.

Известны и другие подобные методы, которые также основаны на проведении точных вычислений при одномерном поиске и на более общей (чем квадратичная) аппроксимации целевой функции (см., например, ). Краудер и Вульф в 1972 г., а затем Пауэлл доказали, что методы сопряженных градиентов обладают линейной скоростью сходимости при отсутствии периодического возврата к начальной итерации. Указанные возвраты осуществляются в соответствии со специальной процедурой, которая прерывает процесс построения векторов направлений поиска, а далее вычисления продолжаются по аналогии с построением s (x (0)). Выше отмечалось, что по ряду причин наличие процедуры возврата к начальной итерации повышает устойчивость работы алгоритма, так как позволяет избежать построения линейно зависимых векторов направлений поиска. Пауэлл доказал, что метод Полака - Рибьера также характеризуется линейной скоростью сходимости при отсутствии возвратов к начальной итерации, однако имеет несомненное преимущество перед методом Флетчера - Ривса при решении задач с целевыми функциями общего вида и обладает менее высокой чувствительностью к ошибкам округления при проведении одномерных поисков.

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

| g (x ) T g (x ) | ≥ 0.2 ||g (x )|| . (3.73)

Он продемонстрировал, что стратегию Била, дополненную услови­ем (3.73), можно успешно применять как вместе с формулой Флет­чера - Ривса, так и с формулой Полака - Рибьера, и провел ряд вычислительных экспериментов, результаты которых подтверж­дают превосходство метода Полака - Рибьера (с возвратом). Шэнно исследовал влияние ошибок округления при проведе­нии поисков вдоль прямой и различных стратегий возврата на эффективность методов сопряженных градиентов. Он показал, что стратегия Била (с использованием соответствующей двухпараметрической формулы), дополненная предложенным Пауэллом усло­вием возврата, приводит к существенному уменьшению требуемой точности одномерного поиска и, следовательно, к значительному повышению эффективности полной вычислительной схемы метода сопряженных градиентов. Шэнно также представил численные ре­зультаты, которые указывают на преимущество метода Полака - Рибьера с использованием процедур возврата и округления при поисках вдоль прямой. В работе продемонстрирована ведущая роль методов сопряженных градиентов при решении задач нелиней­ного программирования большой размерности.

Квазиньютоновские методы

Эти методы подобны методам, рассмотренным в подразд. 3.3.5, поскольку также основаны на свойствах квадратичных функций. В соответствии с изложенными выше методами поиск решения осуществляется по системе сопряженных направлений, тогда как квазиньютоновские методы обладают положительными чертами метода Ньютона, однако используют только первые производные. Во всех методах указанного класса построение векторов направлений поиска осуществляется с помощью формулы (3.42), в которой s (x (k))записывается в виде

s (x ) = –A f (x ), (3.74)

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

x = C g . (3.75)

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

Для аппроксимации матрицы, обратной матрице Гессе, воспользуемся следующим рекуррентным соотношением:

A = A + A (3.76)

где A - корректирующая матрица. Матрица A будет использоваться в формулах (3.74) и (3.42). Задача заключается в том, чтобы построить матрицу A таким образом, чтобы последовательность А (0) , А (1) , А (2) ,...,A (k +1) давала приближение к Н -1 = f (x *) -1 ; при этом для получения решения х* требуется один дополнительный поиск вдоль прямой, если f(x) - квадратичная функция. Как неоднократно подчеркивалось выше, имеются определенные основания полагать, что метод, обеспечивающий нахождение оптимумов квадратичных функций, может привести к успеху при решении задач с нелинейными целевыми функциями общего вида.

Вернемся к важному свойству квадратичных функций (3.75) и предположим, что матрица С -1 аппроксимируется по формуле

С -1 = βA , (3.77)

где р - скалярная величина. Наиболее предпочтительным является приближение, удовлетворяющее (3.75), т. е.

x = A g . (3.78)

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

x = x – x , (3.79)

g = g (x ) – g (x ). (3.80)

С другой стороны, можно потребовать, чтобы новое приближение удовлетворяло формуле (3.75):

x = βA g . (3.81)

Подставляя выражение (3.76) в (3.81), получаем

A g = x – A g . (3.82)

С помощью непосредственной подстановки можно убедиться, что матрица

A = – (3.83)

является решением этого уравнения. Здесь у и z - произвольные векторы, т. е. формула (3.83) определяет некоторое семейство решений. Если положить

y = x и z =A g , (3.84)

то получим формулу, реализующую известный и широко приме­няемый метод Дэвидона - Флетчера - Пауэлла (ДФП) :

A = A + – . (3.85)

Можно показать, что эта рекуррентная формула сохраняет свойства симметрии и положительной определенности матриц. Поэтому если А (0) симметрическая положительно определенная матрица,то матрицы А (1) , А (2) , ... также оказываются симметрическими и положительно определенными при отсутствии ошибок округления; обычно удобно выбирать А (0) = I .

Первая вариация f(x) равна

f(x) = f (x ) x . (3.86)

Используя формулы (3.42) и (3.74), получаем

f(x) = f (x ) α A f (x ), (3.87)

f(x) = – α f (x ) A f (x ), (3.88)

и неравенство f (x (k +1) ) < f (x k ) выполняется при любых значениях α > 0, если A - положительно определенная матрица. Таким образом, алгоритм обеспечивает убывание целевой функции при переходе от итерации к итерации. Метод Дэвидона - Флетчера - Пауэлла в течение ряда лет продолжает оставаться наиболее широко используемым градиентным методом. Он отличается устойчивостью и успешно применяется при решении самых различных задач, возникающих на практике. Основным недостатком методов такого типа является необходимость хранить в памяти ЭВМ матрицу А порядка N N.