Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
До сих пор в итерационной процедуре (3.48) в качестве направления убывания функции f(х) мы использовали направление антиградиента: ¢(х k) . Однако такой выбор направления убывания не всегда бывает удачным. В частности, для плохо обусловленных задач минимизации направление антиградиента в точке х k может значительно отличаться от направления к точке минимума х*. В результате траектория приближения к точке минимума имеет зигзагообразный характер (см. пример 3.10).
В разд. 3.5.6 был описан метод сопряженных направлений, позволяющий найти точку минимума квадратичной функции за конечное число шагов. Опишем метод, позволяющий получить сопряженные направления для квадратичной функции f(х) с использованием ее производных. В этом методе используется итерационный процесс
х k +1= х k + a k р k, k = 0, 1, …; x0 Î E n, p0 = -f ¢(х0), (3.55)
в котором величина шага находится из условия исчерпывающего спуска по направлению р k. После вычисления очередной точки х k +1, k = 0, 1,… новое направление поиска р k +1 находится по формуле
р k +1=-f ¢(х k +1) + b k p k, k = 0, 1, …, (3.56)
где коэффициенты b k выбираются так, чтобы при минимизации квадратичной функции 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 ¢(x i) при 0 £ i < k £ n- 1, то векторы р0, …, р k A -ортогональны, а градиенты f '(x0),.., f '(x i) взаимно ортогональны.
Обращение градиента в нуль в очередной точке х k итерационного процесса свидетельствует о достижении точки глобального минимума. Так как направления р k в (3.55) являются A -ортогональными, рассматриваемый метод гарантирует нахождение точки минимума сильно выпуклой квадратичной функции не более чем за п шагов (см. теорему 3.9).
С учетом взаимной ортогональности градиентов f' (x i) и условий исчерпывающего спуска по направлениям р k можно упростить выражения (3.57) и (3.58). Выразим числитель дроби (3.58):
<f¢(x k),p k >= <f ¢(x k), -f ¢(x k) + b k -1p k -1> = -||f ¢(x k)||2 +b k -1<f ¢(x k), p k -1> =-||f¢(x k)||2.
(3.59)
Умножив обе части равенства (3.55) слева на матрицу A и прибавив к ним по вектору b, получим
f ¢(x k +1)= f ¢(x k)+ a k A р k. (3.60)
С учетом формулы (3.60) упростим числитель в выражении (3.57) для b k следующим образом:
< A f ¢(x k +1), р k > = <f ¢(x k +1), A р k > = <f ¢(x k +1), > = . (3.61)
В результате выражения для a k и b k примут вид
; (3.62)
. (3.63)
Выражение (3.63) для коэффициента b k не содержит в явном виде матрицу A квадратичной функции. Поэтому метод сопряженных градиентов может применяться и для минимизации неквадратичных функций. В этом случае итерационный процесс метода описывается соотношениями:
x k +1 =x k + a k p k, x0 Î E n, p0 = -f ¢(x0), k= 0, 1, …; (3.64)
f(x k + a k p k) = , k= 0, 1, …; (3.65)
p k +1= -f ¢(x k +1) + b k p k, k= 0, 1, …; (3.66)
, k= 0, 1, …; (3.67)
Разумеется, процесс (3.64)—(3.65) может не приводить к точке минимума функции f(х), отличной от квадратичной, за конечное число итераций. Далее, точное определение a k из условия (3.65) возможно лишь в редких случаях. Поэтому реализация каждой итерации метода будет сопровождаться неизбежными погрешностями. Эти погрешности, накапливаясь, могут привести к тому, что векторы р k перестанут указывать направление убывания функции и сходимость метода может нарушиться. Поэтому на практике в методе сопряженных градиентов через N шагов производят обновление метода, полагая b mN = 0, m = 1, 2,.. Номера mN называются моментами обновления метода (реcтарта). Часто полагают N=n — размерности пространства E n. Если N = 1, то получается частный случай метода сопряженных градиентов — метод наискорейшего спуска.
Опишем алгоритм метода сопряженных градиентов.
Шаг 0. Задать параметр точности e > 0, выбрать x0 Î E n, найти f ¢(х0).
Шаг 1. Положить k= 0, р0 =-f ¢(х0).
Шаг 2. Решить задачу одномерной минимизации f(х k + aр k)®min, a > 0, т.е. найти a = a k.
Шаг 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. Вычислить коэффициент b k = || f '(х k +1)||2/ || f '(х k)||2 и найти новое направление поиска р k +1 =- f '(х k +1)+ b k р k. Положить k=k+ 1 и перейти к шагу 2.
Замечание. Вблизи точки минимума дважды дифференцируемая функция с положительно определенной матрицей Гессе f ''(х*), как правило, достаточно хорошо аппроксимируется квадратичной функцией. Поэтому можно надеяться на хороший результат применения этого метода для таких функций.
Пример 3.12. Методом сопряженных градиентов найти точку минимума функции f(x)=4x21 + 3x22 – 4 x1x2 + x1 из начальной точки x0 = (0, 0).
Дата публикования: 2015-04-07; Прочитано: 550 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!