Лекция: МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ

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

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

хk+1= хk+ akрk, k = 0, 1, …; x0 ÎEn, p0= -f ¢(х0), (3.55)

в котором величина шага находится из условия исчерпывающего спуска по направлению рk. После вычисления очередной точки хk+1, k = 0, 1,… новое направление поиска рk+1 находится по формуле

рk+1=-f ¢( хk+1) + bkpk, k = 0, 1, …, (3.56)

где коэффициенты bk выбираются так, чтобы при минимизации квад­ратичной функции f(х) с положительно определенной матрицей A получалась последовательность А-ортогональных векторов р0, р1,… Из условия <Aрk+1, рk+1>=0 имеем:

. (3.57)

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

. (3.58)

Можно показать, что процесс (3.55)-(3.58) минимизации квадра­тичной функции с положительно определенной симметрической мат­рицей A дает точки х0, .., хk и векторы р0, …, рk такие, что если f ¢(xi) при 0 £ i < k £ n-1, то векторы р0, …, рk A-ортогональны, а градиенты f '(x0), .., f '(xi) взаимно ортогональны.

Обращение градиента в нуль в очередной точке хk итерационного процесса свидетельствует о достижении точки глобального минимума. Так как направления рk в (3.55) являются A-ортогональными, рассмат­риваемый метод гарантирует нахождение точки минимума сильно выпуклой квадратичной функции не более чем за п шагов (см. теорему 3.9).

С учетом взаимной ортогональности градиентов f'(xi) и условий исчерпывающего спуска по направлениям рk можно упростить выра­жения (3.57) и (3.58). Выразим числитель дроби (3.58):

<f¢(xk),pk>= <f ¢(xk), -f ¢(xk) + bk-1pk-1> = -||f ¢(xk)||2 +bk-1<f ¢(xk), pk-1> =-||f¢(xk)||2.

(3.59)

Умножив обе части равенства (3.55) слева на матрицу Aи приба­вив к ним по вектору b, получим

f ¢(xk+1)= f ¢(xk)+ ak Aрk. (3.60)

С учетом формулы (3.60) упростим числитель в выражении (3.57) для bk следующим образом:

<Af ¢(xk+1), рk > = <f ¢(xk+1), Aрk > = <f ¢(xk+1), > =. (3.61)

В результате выражения для ak и bk примут вид

; (3.62)

. (3.63)

Выражение (3.63) для коэффициента bk не содержит в явном виде матрицу A квадратичной функции. Поэтому метод сопряженных гра­диентов может применяться и для минимизации неквадратичных фун­кций. В этом случае итерационный процесс метода описывается соот­ношениями:

xk+1 =xk + akpk, x0 Î En, p0= -f ¢(x0), k= 0, 1, …; (3.64)

f(xk + akpk) =, k= 0, 1, …; (3.65)

pk+1= -f ¢(xk+1) + bkpk, k= 0, 1, …; (3.66)

, k= 0, 1, …; (3.67)

Разумеется, процесс (3.64)—(3.65) может не приводить к точке минимума функции f(х), отличной от квадратичной, за конечное число итераций. Далее, точное определение ak из условия (3.65) возможно лишь в редких случаях. Поэтому реализация каждой итерации метода будет сопровождаться неизбежными погрешностями. Эти погрешно­с­ти, накапливаясь, могут привести к тому, что векторы рk перестанут указывать направление убывания функции и сходимость метода может нарушиться. Поэтому на практике в методе сопряженных градиентов через N шагов производят обновление метода, полагая bmN = 0, m = 1, 2,… Номера mN называются моментами обновления метода (реcтарта). Часто полагают N=n — размерности пространства En. Если N=1, то получается частный случай метода сопряженных градиентов — метод наискорейшего спуска.

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

Шаг 0. Задать параметр точности e > 0, выбрать x0 Î En, найти f ¢(х0).

Шаг 1. Положить k= 0, р0=-f ¢(х0).

Шаг 2. Решить задачу одномерной минимизации f(хk + aрk)®min, a > 0, т.е. найти a = ak .

Шаг 3. Положить хk+1= хk + aрk и вычислить f '(хk+1). Проверить условие достижения точности: ||f '(хk+1)|| < e. Если оно выполняется, то положить х0=хk+1, f '(x0)=f '(хk+1) и закончить поиск, иначе — перейти к шагу 4.

Шаг 4. Проверить условие k+ 1 = n. Если оно выполняется, то положить х0=хk+1, f '(x0)=f '(хk+1) и перейти к шагу 1 (рестарт), иначе — перейти к шагу 5.

Шаг 5. Вычислить коэффициент bk = ||f '(хk+1)||2/ ||f '(хk)||2 и найти новое направление поиска рk+1 =-f '(хk+1)+ bkрk. Положить k=k+1 и перейти к шагу 2.

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

Пример 3.12. Методом сопряженных градиентов найти точку минимума функции f(x)=4x21 + 3x22 – 4 x1x2 + x1 из начальной точки x0= (0, 0).