Далее будет изложен метод сопряженных градиентов, относящейся к группе методов сопряженных направлений. Этот метод как и метод градиентного спуска, является методом первого порядка т. е. Использует информацию только первой производной минимизируемой функции.
Однако метод сопряженных градиентов отличается от градиентных методов более высокой скоростью сходимости, которая при определенных предположениях относительно целевой функции, приближается к скорости сходимости метода Ньютона.
Два вектора 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. Воспользуйтесь формой поиска:
Еще по теме Метод сопряженных градиентов:
- 26. Отыскание экстремумов функций многих переменных. метод сопряженных градиентов, метод переменных направлений, метод переменной метрики.
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 − задача решена |
||||||||||
Рассмотренные выше градиентные методы отыскивают точку минимума функции в общем случае лишь за бесконечное число итераций. Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Это существенно увеличивает скорость их сходимости и позволяет, например, минимизировать квадратичную функцию
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. Понятие о методах сопряженных направлений.
Рассмотрим задачу минимизации квадратичной функции
с симметричной положительно определенной матрицей А Напомним, что для ее решения требуется один шаг метода Ньютона и не более чем шагов квазиньютоновского метода Методы сопряженных направлений также позволяют найти точку минимума функции (10.33) не более чем за шагов. Добиться этого удается благодаря специальному выбору направлений поиска.
Будем говорить, что ненулевые векторы являются взаимно сопряженными (относительно матрицы А), если для всех
Под методом сопряженных направлений для минимизации квадратичной функции (10.33) будем понимать метод
в котором направления взаимно сопряжены, а шаги
получаются как решение задач одномерной минимизации:
Теорема 10.4. Метод сопряженных направлений позволяет найти точку минимума квадратичной функции (10 33) не более чем за шагов.
Методы сопряженных направлений отличаются один от другого способом построения сопряженных направлений. Наиболее известным среди них является метод сопряженных градиентов
2. Метод сопряженных градиентов.
В этом методе направления строят правилу
Так как то первый шаг этого метода совпадает с шагом метода наискорейшего спуска. Можно показать (мы этого делать не будем), что направления (10.34) действительно являются
сопряженными относительно матрицы А. Более того, градиенты оказываются взаимно ортогональными.
Пример 10.5. Применим метод сопряженных градиентов для минимизации квадратичной функции - из примера 10.1. Запишем виде где
Возьмем начальное приближение
1-й шаг метода совпадает с первым шагом метода наискорейшего спуска. Поэтому (см. пример 10.1)
2-й шаг. Вычислим
Так как то и решение оказалось найденным за два шага.
3. Метод сопряженных градиентов для минимизации неквадратичных функций.
Для того чтобы указанный метод можно было применить для минимизации произвольной гладкой функции формулу (10.35) для вычисления коэффициента преобразуют к виду
или к виду
Преимущество формул (10 36), (10.37) в том, что они не содержат явным образом матрицу А.
Минимизацию функции методом сопряженных градиентов производят в соответствии с формулами
Коэффициенты вычисляют по одной из формул (10.36), (10.37).
Итерационный процесс здесь уже не оканчивается после конечного числа шагов, а направления не являются, вообще говоря, сопряженными относительно некоторой матрицы.
Решение задач одномерной минимизации (10.40) приходится осуществлять численно. Отметим также то, что часто в методе сопряженных градиентов при коэффициент не вычисляют по формулам (10.36), (10.37), а полагают равным нулю. При этом очередной шаг производят фактически методом наискорейшего спуска. Такое "обновление" метода позволяет уменьшить влияние вычислительной погрешности.
Для сильно выпуклой гладкой функции при некоторых дополнительных условиях метод сопряженных градиентов обладает высокой сверхлинейной скоростью сходимости. В то же время его трудоемкость невысока и сравнима с трудоемкостью метода наискорейшего спуска. Как показывает вычислительная практика, он незначительно уступает по эффективности квазиньютоновским методам, но предъявляет значительно меньшие требования к используемой памяти ЭВМ. В случае, когда решается задача минимизации функции с очень большим числом переменных, метод сопряженных градиентов, по-видимому, является единственным подходящим универсальным методом.
Метод сопряженных градиентов (в англ. литературе «conjugate gradient method») - это итерационный численный метод (первого порядка) решения оптимизационных задач, который позволяет определить экстремум (минимум или максимум) целевой функции:
- это значения аргумента функции (управляемые параметры) на вещественной области.
В соответствии с рассматриваемым методом экстремум (максимум или минимум) целевой функции определяют в направлении наиболее быстрого возрастания (убывания) функции, т.е. в направлении градиента (антиградиента) функции. Градиентом функции в точке называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам:
где i, j,…, n - единичные векторы, параллельные координатным осям.
Градиент в базовой точке 
строго ортогонален к поверхности, а его направление показывает направление наискорейшего возрастания функции, а противоположное направление (антиградиент), соответственно, показывает направление наискорейшего убывания функции.
Метод сопряженных градиентов является дальнейшим развитием метода наискорейшего спуска, который сочетает в себе два понятия: градиент целевой функции и сопряженное направление векторов. В общем случае процесс нахождения минимума функции является итерационной процедурой, которая записывается в векторной форме следующим образом:
где знак «+» используется для поиска максимума функции, а знак «-» используется для поиска минимума функции.
Единичный вектор сопряженных направлений, который определяется по формуле:
Существует несколько способов определения значений весовых коэффициентов (переменная ), которые используются для определения сопряженного направления.
В качестве первого способа рассматривают определение весового коэффициента по формуле Флетчера-Ривса (Fletcher–Reeves):
- модуль градиента определяет скорость возрастания или убывания функции в направлении градиента или антиградиента соответственно.
В качестве второго способа рассматривают определение весового коэффициента по формуле Полака–Райбера (Polak-Ribiere):
В соответствии с представленными выражениями новое сопряженное направление получается сложением градиента (антиградиента) в точке поворота и предыдущего направления движения, умноженного на коэффициент. Таким образом, метод сопряженных градиентов формирует направление поиска к оптимальному значению используя информацию о поиске полученную на предыдущих этапах спуска. Следует отметить, что сопряженные направления P, P, ..., P вычисляют с помощью формулы Флетчера-Ривса, которая позволяет построить сопряженные векторы относительно некоторой симметрической матрицы для произвольно заданной функции.
Траектория спуска в методе сопряженных градиентов (поиск минимума)
Геометрический смысл метода сопряженных градиентов состоит в следующем: из заданной начальной точки х осуществляется спуск в направлении р (градиента или антиградиента) в новую точку х, в которой определяется вектор-градиент функции. Поскольку х является точкой минимума функции в направлении р, то вектор-градиент функции в точке х ортогонален вектору р. Затем определяется вектор р который ортогонален относительно некоторой симметрической матрицы вектору р. В результате осуществляется спуск вдоль найденного направления в новую точку х.
Траектория движения к точке экстремума при использовании метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная).
Следует отметить, что через каждые n + 1 шагов необходимо выполнять рестарт алгоритмической процедуры (n – размерность пространства поиска). Рестарт алгоритмической процедуры необходим, чтобы забыть последнее направление поиска и стартовать алгоритм заново в направлении скорейшего спуска.
Величина шага выбирается из условия минимума целевой функции f(х) в направлении движения, т. е. в результате решения задачи одномерной оптимизации в направлении градиента или антиградиента:
Другими словами, величину шага определяют при решении данного уравнения:
Поиск оптимального решения завершается в случае, когда на итерационном шаге расчета (несколько критериев):
Траектория поиска остается в малой окрестности текущей точки поиска:
Приращение целевой функции не меняется:
Градиент целевой функции в точке локального минимума обращается в нуль:
Метод сопряженных градиентов является методом первого порядка, но при этом обладает квадратичной скоростью сходимости, как Ньютоновские методы расчета. Метод градиента вместе с его многочисленными модификациями является распространенным и эффективным методом поиска оптимума исследуемых объектов. Недостатком градиентного поиска (так же и рассмотренных выше методов) является то, что при его использовании можно обнаружить только локальный экстремум функции. Для отыскания других локальных экстремумов необходимо производить поиск из других начальных точек.
Методика расчета
1 шаг: Определение аналитические выражения (в символьном виде) для вычисления градиента функции
2 шаг : Задаем начальное приближение
3 шаг: Определяется необходимость рестарта алгоритмической процедуры для обнуления последнего направления поиска. В результате рестарта поиск осуществляется заново в направлении скорейшего спуска.
4 шаг : Вычисление координат единичного вектора по формуле, полученной на шаге 1, и определение координат новой точки при движении по направлению единичного вектора как функция от шага расчета.
Вычисление весового коэффициента и единичного вектора сопряженных направлений на текущем шаге расчета (формула Флетчера-Ривса):
Для первого шага расчета весовой коэффициент не вычисляется (или в случае рестарта алгоритма), а единичный вектор сопряженных направлений определяется следующим образом.