В предыдущих подразделах рассматривались методы Коши и Ньютона. Отмечалось, что метод Коши эффективен при поиске на значительных расстояниях от точки минимума х* и плохо «работает» в окрестности этой точки, тогда как метод Ньютона не отличается высокой надежностью при поиске х* из удаленной точки, однако оказывается весьма эффективным в тех случаях, когда 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f (x )

		f (xk ) = f(x0 ) + ∑ α i Api .
		i= 1
	обе части	этого равенства скалярно на p k		учитывая
исчерпывающего спуска по направлению p k :(f (x k ), p k ) = 0			и A −ортогональность
векторов, получаем
		(f (x 0 ),p k )+ α k (Ap k ,p k )= 0.
		A положительно определена,	квадратичная
(Ap k , p k ) > 0 и для величины шагаα k получаем выражение (5.17).
	Последовательный исчерпывающий спуск			A –ортогональным

направлениям (5.16) приводит к точке минимума квадратичной формы не более чем за n шагов.

□ Доказать самостоятельно. Предположить, что существуют u k ≠ α k , и

получить, что они совпадают. ■

Вопрос о нахождении базиса из A –ортогональных векторов в пространствеE n

решается неоднозначно. В качестве такого базиса можно, например, взять ортогональный базис из собственных векторов матрицы A . Однако их поиск приn > 2 представляет собой самостоятельную и довольно сложную задачу.

и без предварительного построения векторов p 1 , ..., p n , последовательно находя их в процессе минимизации, как это было сделано выше в примере с минимизацией функции двух переменных. И в этом случае для квадратичной функции с положительно определенной матрицейA для нахождения минимума достаточно конечное число шагов. Если не является квадратичной функцией или

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

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

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

При использовании методов градиентного и наискорейшего спуска в итерационной процедуре

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

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

направлению p k . Далее,		после вычисления очередной точки x k + 1 ,					k = 0, 1, ..., новое
направление поиска p k + 1		находится по формуле, отличной от антиградиента:
	pk + 1 = − f(xk + 1 ) + β k pk ,			k = 0, 1, ...,
где коэффициенты		выбираются так, чтобы при минимизации квадратичной
функции f (x ) с	положительно определенной					матрицей	A получалась
последовательность	A −ортогональных			векторов		p 0 ,p 1 , ....	Из условия
(Ap k + 1 ,p k )= 0имеем:
		β k=	(A f (x k + 1 ),p k )
			(Ap k ,p k )

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

для квадратичной функции шаг исчерпывающего спуска по направлению p k равен

α k = −	(f (x k ),p k )
	(Ap k ,p k )
Утверждение . Итерационный процесс			(5.19)−(5.22) минимизации

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

f (x )

A дает точки	x 0 , ...,x k	и векторы p 0 , ..., p k такие, что если				f (x i )≠ 0при
0 ≤i	то векторы		p 0 , ...,		A −ортогональны,		градиенты
f (x 0 ), ...,f (x i )	взаимно ортогональны.
Так как направления				являются A −ортогональными,

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

С учетом взаимной ортогональности градиентов f (x i ) и условий

исчерпывающего спуска по направлениям p k можно упростить выражения (5.21) и

(5.22) для α k

и β k . В результате получим,

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

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

x k+ 1

X k +α k

p k ,k = 0, 1, ...;

x0 En ,

p0 = − f(x0 ) ,

f (x k + α k p k )= minf (x k

+ αp k ),

k = 0, 1, ...,

α> 0

p k+ 1

= − f (x k + 1 ) +β k

p k ,k = 0, 1, ...,

β k=

f (xk + 1 )

k = 1, 2, ...

f (xk )

Следует отметить, что выражение для коэффициента β k не содержит в явном виде матрицуA квадратичной формы. Поэтому метод сопряженных градиентов может применяться для минимизации неквадратичных функций.

Итерационный процесс (5.23)−(5.26) может не приводить к точке минимума неквадратичной функции за конечное число итераций. Более того, точное

определение α k из условия (5.22) возможно лишь в редких случаях, а вектораp k

на образуют, вообще говоря, A −ортогональную систему относительно какой-либо матрицыA . Поэтому реализация каждой итерации метода будет сопровождаться неизбежными погрешностями. Эти погрешности, накапливаясь, могут привести к

тому, что векторы p k перестанут указывать направление убывания функции и

сходимость метода может нарушаться. Поэтому в методе сопряженных градиентов применяется практический прием − через каждые N шагов производят обновление метода, полагаяβ m N = 0, m = 1, 2, ... . Номераm N называют моментами

обновления метода, или рестарта . Часто полагаютN = n − размерности пространстваE n . ЕслиN = 1 , то получается частный случай метода сопряженных градиентов − метод наискорейшего спуска.

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

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

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

функции f (x ) = 4 x 2 + 3 x 2 − 4 x x

из начальной точки x 0 = (0, 0) T .

□ Итерация 1.

Шаг 1. Положим ε = 0,01,

= (0, 0)T ,

и найдем f (x 0 ) = (1, 0) T . Перейдем к

Шаг 2. Положим k = 0,

= − f (x 0 ) = (− 1, 0) T . Перейдем к шагу 3.

f (x0

+ α p 0 )→ min.Получим

α 0 = 1/ 8 . – Здесь применили формулуα 0 = −

(f (x 0 ),p 0 )

(Ax 0 + b ,p 0 )

Перейдем

(Ap 0 ,p 0 )

(Ap 0 ,p 0 )

Шаг 4. Найдем

x 1= x 0

+ α 0 p 0 = (− 1/ 8,

и f (x 1 ) = (0, 1/ 2) T . Точность не

достигнута, прейдем к шагу 5.

Шаг 5. Условие k + 1 = n не выполняется (нет рестарта), перейдем к шагу 6.

Шаг 6. Найдем коэффициент β 0 = 1/ 4 и новое направление спуска

p 1 = − f (x 1 ) + β 0 p 0 = (− 1/ 4, − 1/ 2) T . Перейдем к следующей итерации.

Поскольку x 1 , f (x 1 ) иp 1

= − f (x 1 ) +β 0

уже вычислены на итерации 1, то

итерацию 2 начинаем с шага 3.

Итерация 2.

Шаг 3. Решим задачу одномерной минимизации

f (x 1 + α p 1 ) → min . Получим

α = 1/ 4 . Перейдем к шагу 4.

Шаг 4. Найдем x 2

X 1 +α 1

p 1 = (− 3 /16,− 1/ 8)T и f (x 2 )= (0, 0)T − задача решена

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

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

Два вектора 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. Отыскание экстремумов функций многих переменных. метод сопряженных градиентов, метод переменных направлений, метод переменной метрики.

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

f(x 1 ,x 2) =

Метод отыскания минимума функции Метод сопряженных градиентов Метод Флетчера–Ривза Метод Миля-Кентрелла Метод Поллака-Рибьера Метод Ньютона Метод наискорейшего спуска
Начиная из точки ( ; ) . Точность ξ = .
Количество итераций 1 2 3

Решение оформляется в формате Word .

Правила ввода функций :

Например, x 1 2 +x 1 x 2 , записываем как x1^2+x1*x2

Формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции.
Определение . Два n -мерных вектора х и у называют сопряженными по отношению к матрице A (или A-сопряженными), если скалярное произведение (x, Aу) = 0 . Здесь A - симметрическая положительно определенная матрица размером n х n .

Схема алгоритма метода сопряженных градиентов

Положить k=0.
Ш. 1 Пусть x 0 - начальная точка; ,
d 0 =-g 0 ; k=0.
Ш. 2 Определить x k +1 =x k +λ k d k , где
.
Затем d k+1 =-g k+1 +β k d k ,
,
β k находится из условия d k +1 Ad k =0 (сопряжены относительно матрицы A).
Ш. 3 Положить k=k+1 → Ш. 2.
Критерий останова одномерного поиска вдоль каждого из направлений d k записывается в виде: .
Значения выбираются таким образом, чтобы направление d k было A-сопряжено со всеми построенными ранее направлениями.

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

Стратегия метода Флетчера-Ривса состоит в построении последовательности точек {x k }, k=0, 1, 2, ... таких, что f(x k +1) < f(x k), k=0, 1, 2, ...
Точки последовательности {x k } вычисляются по правилу:
x k +1 =x k -t k d k , k = 0, 1, 2,…
d k = ▽f(x k) + b k -1 ▽f(x k -1)

Величина шага выбирается из условия минимума функции f(х) по t в направлении движения, т. е. в результате решения задачи одномерной минимизации:
f(x k -t k d k) → min (t k >0)
В случае квадратичной функции f(x)= (х, Нх) + (b, х) + а направления d k , d k -1 будут H-сопряженными, т.е. (d k , Hd k -1)=0
При этом в точках последовательности {x k } градиенты функции f(x) взаимно перпендикулярны, т.е. (▽f(x k +1),▽f(x k))=0, k =0, 1, 2…
При минимизации неквадратичных функций метод Флетчера-Ривса не является конечным. Для неквадратичных функций используется следующая модификация метод Флетчера-Ривса (метод Полака-Рибьера), когда величина b k -1 вычисляется следующим образом:

Здесь I- множество индексов: I = {0, n, 2n, 3n, ...}, т. е. метод Полака-Рибьера предусматривает использование итерации наискорейшего градиентного спуска через каждые n шагов с заменой x 0 на x n +1 .
Построение последовательности{x k } заканчивается в точке, для которой |▽f(x k)|<ε.
Геометрический смысл метода сопряженных градиентов состоит в следующем. Из заданной начальной точки x 0 осуществляется спуск в направлении d 0 = ▽f(x 0).В точке x 1 определяется вектор-градиент ▽f(x 1).Поскольку x 1 является точкой минимума функции в направлении d 0 , то▽f(x 1) ортогонален вектору d 0 . Затем отыскивается вектор d 1 , H-сопряженный к d 0 . Далее отыскивается минимум функции вдоль направления d 1 и т. д.

Алгоритм метода Флетчера-Ривса

Начальный этап.
Задать x 0 , ε > 0.
Найти градиент функции в произвольной точке
k=0.
Основной этап
Шаг 1. Вычислить ▽f(x k)
Шаг 2. Проверить выполнение критерия останова |▽f(x k)|< ε
а) если критерий выполнен, расчет окончен,x * =x k
б) если критерий не выполнен, то перейти к шагу 3, если k=0, иначе к шагу 4.
Шаг 3. Определить d 0 = ▽f(x 0)
Шаг 4. Определить или в случае неквадратичной функции
Шаг 5. Определить d k = ▽f(x k) + b k -1 ▽f(x k -1)
Шаг 6. Вычислить величину шага t k из условия f(x k - t k d k) → min (t k >0)
Шаг 7. Вычислить x k+1 =x k -t k d k
Шаг 8. Положить k= k +1 и перейти к шагу 1.

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

Теорема 1. Если квадратичная функция f(x) = (х, Нх) + (b, х) + а с неотрицательно определенной матрицей Н достигает своего минимального значения на R n , то метод Флетчера-Ривса обеспечивает отыскание точки минимума не более чем за n шагов.
Теорема 2. Пусть функция f(x) дифференцируема и ограничена снизу на R m , а ее градиент удовлетворяет условию Липшица . Тогда при произвольной начальной точке для метода Полака-Рибьера имеем
Теорема 2 гарантирует сходимость последовательности {x k } к стационарной точке x * , где ▽f(x *)=0. Поэтому найденная точка x * нуждается в дополнительном исследовании для ее классификации. Метод Полака-Рибьера гарантирует сходимость последовательности {x k } к точке минимума только для сильно выпуклых функций.
Оценка скорости сходимости получена только для сильно выпуклых функций , в этом случае последовательность {x k } сходится к точке минимума функции f(x) со скоростью: |x k+n – x*| ≤ C|x k – x*|, k = {0, n, 2, …}

Пример . Найти минимум функции методом сопряженных градиентов: f(X) = 2x 1 2 +2x 2 2 +2x 1 x 2 +20x 1 +10x 2 +10 .
Решение. В качестве направления поиска выберем вектор градиент в текущей точке:

- t 0 - 0.1786

20 10

= + 0.0459 - t 1 - 0.4667 Так как матрица Гессе является положительно определенной, то функция f(X) строго выпукла и, следовательно, в стационарной точке достигает глобальный минимум .