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

⇐ ПредыдущаяСтр 6 из 7Следующая ⇒

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

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

¹⁾Задачи такого типа возникают, например, в регрессионном анализе — Прим. перев.

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

Пусть в пространстве управляемых переменных заданы две произвольные несовпадающие точки x⁽⁰⁾ и x⁽¹⁾. Градиент квадратичной функции равен

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

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

g(x⁽⁰⁾) = C x⁽⁰⁾ + b,

g(x⁽¹⁾) = C x⁽¹⁾ + b.

Запишем изменение градиента при переходе от точки х⁽⁰⁾ к точке х⁽¹⁾:

g(x) = g(x⁽¹⁾) – g(x⁽⁰⁾) = C (x⁽¹⁾ - x⁽⁰⁾), (3.61)

g(x) = C x

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

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

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

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⁽⁰⁾ = –g⁽⁰⁾, (3.63)

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

f (x )^Ts⁽^k⁾ = 0 (3.64)

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

s⁽¹⁾ = –g⁽¹⁾ + γ ⁽⁰⁾s⁽⁰⁾ = –g⁽¹⁾ –γ ⁽⁰⁾g⁽⁰⁾

и наложим условие его сопряженности с s⁽⁰⁾

s^(1)T C s⁽⁰⁾ = 0,

откуда [g⁽¹⁾ + γ ⁽⁰⁾g⁽⁰⁾]^T C s⁽⁰⁾ = 0.

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

s⁽⁰⁾ = ;

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

[g⁽¹⁾ + γ ⁽⁰⁾g⁽⁰⁾]^T C [ ] = 0

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

[g⁽¹⁾ + γ ⁽⁰⁾g⁽⁰⁾]^T g = 0, (3.65)

Откуда

γ ⁽⁰⁾ = – ( g^T g⁽¹⁾)/( g^T g⁽⁰⁾). (3.66)

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

g^(1)Tg⁽¹⁾ + γ ⁽⁰⁾g^(0)Tg⁽¹⁾ – g^{(1) T}g⁽⁰⁾ – γ ⁽⁰⁾g^(0)Tg⁽⁰⁾ = 0.

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

g^{(1) T}g⁽⁰⁾ = 0.

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

γ ⁽⁰⁾ = . (3.67)

Далее определим следующее направление поиска

s⁽²⁾ = –g⁽²⁾ + γ ⁽⁰⁾s⁽⁰⁾ + γ ⁽¹⁾s⁽¹⁾.

и выберем γ ⁽⁰⁾ γ ⁽¹⁾ таким образом, чтобы выполнялись условия

s⁽²⁾^T C s⁽⁰⁾ = 0 и s⁽²⁾ C s⁽¹⁾ = 0,

т. е. условия С -сопряженности направления s⁽²⁾ с направлениями s⁽⁰⁾ и s⁽¹⁾. С помощью формул (3.61) и (3.64) можно показать (это предоставляется читателю в качестве упражнения), что здесь γ ⁽⁰⁾ = 0, а в общем случае γ ⁽ⁱ⁾ = 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 = [0, 0]^T.

Решение.

Шаг 1. f(x) = [8x -4x +1, 6x -4x ]^T,

s⁽⁰⁾ = – f(x⁽⁰⁾) = – [1, 0]^T.

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

x = x –α f(x⁽⁰⁾) → α = ⅛,

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

Шаг 3.k = 1.

s⁽¹⁾ = – [0, ½ ]^T – [¼, 1] [1, 0]^T = [–¼, ½ ]^T.

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

x = x + α s⁽¹⁾ → α = ¼,

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

f(x⁽²⁾) = [0, 0]^T.

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

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

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

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

Напомним, что рассмотрение метода Флетчера — Ривса проводилось в предположении квадратичности целевой функции и отсутствия ошибок округления в процессе поиска вдоль прямой. Однако при реализации ряда методов сопряженные направления определяются без учета одного из указанных предположений (или даже обоих предположений). Среди таких методов наибольшего внимания, по-видимому, заслуживает метод, разработанный Ползком и Рибьером [32] в 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)

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

Известны и другие подобные методы, которые также основаны на проведении точных вычислений при одномерном поиске и на более общей (чем квадратичная) аппроксимации целевой функции (см., например, [33, 34, 35]). Краудер и Вульф [36] в 1972 г., а затем Пауэлл [37] доказали, что методы сопряженных градиентов обладают линейной скоростью сходимости при отсутствии периодического возврата к начальной итерации. Указанные возвраты осуществляются в соответствии со специальной процедурой, которая прерывает процесс построения векторов направлений поиска, а далее вычисления продолжаются по аналогии с построением s(x⁽⁰⁾). Выше отмечалось, что по ряду причин наличие процедуры возврата к начальной итерации повышает устойчивость работы алгоритма, так как позволяет избежать построения линейно зависимых векторов направлений поиска. Пауэлл [38] доказал, что метод Полака — Рибьера также характеризуется линейной скоростью сходимости при отсутствии возвратов к начальной итерации, однако имеет несомненное преимущество перед методом Флетчера — Ривса при решении задач с целевыми функциями общего вида и обладает менее высокой чувствительностью к ошибкам округления при проведении одномерных поисков.

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

| g(x )^Tg(x ) | ≥ 0.2 ||g(x )|| . (3.73)

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

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

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

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

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

x = C g. (3.75)

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

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

A = A + A (3.76)

где A — корректирующая матрица. Матрица A будет использоваться в формулах (3.74) и (3.42). Задача заключается в том, чтобы построить матрицу A таким образом, чтобы последовательность А ⁽⁰⁾, А ⁽¹⁾, А ⁽²⁾,..., A ⁽^k⁺¹⁾ давала приближение к Н ^-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)

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

A = A + – . (3.85)

Можно показать, что эта рекуррентная формула сохраняет свойства симметрии и положительной определенности матриц. Поэтому если А ⁽⁰⁾ симметрическая положительно определенная матрица, то матрицы А ⁽¹⁾, А ⁽²⁾, ... также оказываются симметрическими и положительно определенными при отсутствии ошибок округления; обычно удобно выбирать А ⁽⁰⁾ = 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⁺¹⁾) < f(x^k) выполняется при любых значениях α > 0, если A — положительно определенная матрица. Таким образом, алгоритм обеспечивает убывание целевой функции при переходе от итерации к итерации. Метод Дэвидона — Флетчера — Пауэлла в течение ряда лет продолжает оставаться наиболее широко используемым градиентным методом. Он отличается устойчивостью и успешно применяется при решении самых различных задач, возникающих на практике. Основным недостатком методов такого типа является необходимость хранить в памяти ЭВМ матрицу А порядка N N.

Пример 3.10. Метод Дэвидона — Флетчера — Пауэлла

С помощью метода Дэвидона — Флетчера — Пауэлла найти точку минимума функции

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

если х⁽⁰⁾ = [0, 0] .

Решение

Шаг 1.Положим s⁽⁰⁾ = – f(х⁽⁰⁾) = – [1, 0] .

Шаг 2.Поиск вдоль прямой приводит к результату, полученному в примере 3.9, x⁽¹⁾=[ –⅛. 0] .

Шаг 3.k = l, А ⁽¹⁾ = A ⁽⁰⁾ + A ,

A = – ,

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

∆ g = [0, ½ ] – [1, 0] = [–1, ½ ] ,

s⁽¹⁾ = – А ⁽¹⁾ f(х⁽¹⁾) = [– , ] .

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

x⁽²⁾ = x⁽¹⁾ + α ⁽¹⁾s⁽¹⁾ → α ⁽¹⁾ = ,

x⁽²⁾ = [– , 0] – [ , ] = [– , – ]

что совпадает с полученным ранее решением.

Интересно отметить, что в примерах 3.9 и 3.10 методы Флетчера — Ривса и Дэвидона — Флетчера — Пауэлла порождают одни и те же направления поиска, которые оказываются H -сопряженными:

Заметим также, что матрица A стремится к Н ^-1:

Таким образом, А ⁽²⁾ = Н ^-1(х*). После опубликования работы Дэвидона [43] были разработаны другие методы переменной метрики, отличающиеся выбором β, у и z в (3.83). Общая трудность реализации методов такого типа связана с тем, что матрица A в ряде случаев становится плохо обусловленной (определение плохо обусловленной матрицы см. в приложении А) и возникает необходимость возврата к начальной итерации с пересмотренной метрикой.

Другой метод, предложенный Бройденом [45], Флетчером [46] и Шэнно [47], получил широкую известность благодаря рекомендациям Пауэлла [48]. Метод Бройдена — Флетчера — Шэнно (БФШ) реализуется в соответствии с рекуррентной формулой

A = A + . (3.89)

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

Улучшение методов переменной метрики и методов сопряжённых градиентов в настоящее время осуществляется весьма близкими путями. Следовательно, все замечания, сделанные выше по поводу методов сопряженных градиентов, в некоторой степей справедливы для методов переменной метрики. Отметим, что Дэвидон [49] предложил ряд модифицированных процедур, в которых не требуются точные вычисления при проведении поисков вдоль прямой. Позже Пауэлл [50] установил свойство квадратичной сходимости этих методов при отсутствии одномерных поисков. По-видимому, метод переменной метрики в условиях квадратичной сходимости и отсутствия трудоемких операций одномерного поиска может отличаться как устойчивостью, так и быстродействием при решении задач с целевыми функциями общего вида. Эти вопросы были также рассмотрены Голдфарбом [51]. Вообще, возврат к начальной итерации метода Дэвидона — Флетчера — Пауэлла (при А = I) обычно осуществляется после реализации N шагов алгоритма. Как правило, такие действия носят профилактический характер, поскольку в ряде случаев можно сделать большее число шагов до возврата. Необходимость возврата к начальной итерации можно обосновать путем анализа обусловленности получаемых матриц. Однако следует иметь в виду, что наряду с повышением степени надежности (или устойчивости) алгоритмов переменной метрики возвраты чаще всего замедляют процесс приближения к точке оптимума, так как не позволяют использовать имеющиеся оценки производных второго порядка.

В работах [40, 52, 53] проведены обширные исследования связи между методами сопряженных градиентов и методами переменной метрики. Шэнно рассматривает методы сопряженных градиентов как методы переменной метрики с отсутствием «памяти». Большинство авторов придерживается той точки зрения, что эти два класса методов обладают гораздо более существенным сходством, чем это представлялось ранее. Кроме того, ясно, что многие варианты метода переменной метрики отличаются рядом общих особенностей при решении практических задач [54, 55], наличие которых заставляет проводить оценку трудоемкости дополнительных вычислений, связанных с реализацией более сложных методов. Шэнио и Фуа [56, 57] представили обширные числовые результаты, которые свидетельствуют в пользу относительно простой рекуррентной формулы Бройдена — Флетчера — Шэнно.

Описание программной реализации на Фортране некоторых наиболее полезных методов дано в работах [53, 58]. Следует отметить, что методы переменной метрики широко используются при разработке методов решения задач условной оптимизации. В работе [59] предложен алгоритм, объединяющий метод обобщенного приведенного градиента¹⁾ и метод Дэвидона — Флетчера — Пауэлла, тогда как Рут [60] применил метод Дэвидона — Флетчера Пауэлла при расчетах по методу множителей Лагранжа. В работах Хена [61] и Пауэлла [62] исследуются вопросы эффективности методов переменной метрики при решении задач с ограничениями.

Наконец, значительное количество работ посвящено вопросам применения методов переменной метрики к решению задач большой размерности. Как было отмечено выше, в настоящее время наилучшим средством решения таких задач являются методы сопряженных градиентов. Достигнуты определенные успехи при решении задач, в которых матрица Гессе разрежена [63—66]. Одна из трудностей использования методов переменной метрики связана с тем обстоятельством, что часто известна лишь степень разреженности некоторой оценки матрицы Н ^-1, а не матрицы Н.

⇐ Предыдущая 1 2 3 4 567 Следующая ⇒