Лекция: КВАЗИНЬЮТОНОВСКИЕ МЕТОДЫ
Стремление уменьшить объем вычислений привело к созданию класса методов, близких по скорости сходимости к обобщенному методу Ньютона, но не использующих вторых производных целевой функции f(х) и процедуры обращения матрицы f"(х). В методах этого типа используется итерационный процесс
X k+1 = x k — a k H (k) f¢(хk), (3.71)
где H(k) — некоторая квадратичная матрица размера п´ п, а величина шага ak> 0 выбирается из условия исчерпывающего спуска вдоль направления
рk = -H(k) f¢(хk).
В частности, если H(k) = -[f¢¢(хk)]-1, то процесс (3.71) представляет собой обобщенный метод Ньютона.
В квазиньютоновских методах матрица H(k) строится с помощью рекуррентных формул на каждом шаге процесса (3.71). Вид этих формул определяет метод. Рассмотрим в качестве примера метод Давидона — Флетчера — Пауэла (ДФП — метод). Рекуррентная формула для H(k) имеет вид
H(k+1) =H(k) + А(k) +В(k), H(0) = Е, А(0) = В(0) = 0. (3.72)
| Матрицы А(k) и В(k) выражаются на каждом шаге через матрицу H(k) и векторы-столбцы vk = xk+1 — xk, uk = f ¢(xk+1) – f ¢(xk) следующим образом (см. (3.4)):
, (3.73)
.
Пусть в итерационном процессе (3.71)—(3.73) при минимизации выпуклой дифференцируемой функции f(х) в очередной точке хi градиент f'(хi) ¹ 0, т.е. точка минимума f(х) еще не достигнута. Тогда все направления рk= -H(k)f'(хk), £iявляются направлениями убывания функции f(х).
Для доказательства этого утверждения запишем условие убывания (3.36) для направления рk :
<р k, f ' (х k)> = -< H (k) f ' (х k ), f ' (х k)> < 0.
Докажем по индукции, что для всех k £ i,H(k)— симметрическая положительно определенная матрица- Очевидно, H(0)=Е обладает этими свойствами. Отметим, что из соотношений (3.72) и (3.73) следует, что матрица H(k) является симметрической как линейная комбинация симметрических матриц. Предположим, что H(k) положительно определена и докажем, что это справедливо и для матрицы H(k+1). Рассмотрим квадратичную форму <H(k+1)х, х> при х ¹ 0:
<H(k+1)х, х> = <H(k) х, х> + — .
(3.74)
Представим симметрическую матрицу H(k) в виде H(k) = С× СТ= СТ×С, где С — некоторая квадратная матрица размера n´n Обозначим векторы Cx = q, а Cuk = r, тогда равенство (3.74) можно записать в виде
<H(k+1)х, х> = <q2 — + .
(3.75)
Из неравенства Коши — Буняковского (3.2) следует, что q2r2 ³ <q, r>2 поэтому из (3.75) получим неравенство:
<H(k+1)х, х> ³ .
Оценим скалярное произведение в знаменателе правой части неравенства (3.76) с учетом свойства исчерпывающего спуска:
<vk, uk> = < xk+1 – x, f ¢(xk+1) – f ¢(xk)> = ak< pk, f ¢(xk+1) – f ¢(xk) > = ak< pk, f ¢(xk) > = ak< H(k)f ¢(xk), f ¢(xk) > > 0
Из неравенства (3.76) видно, что <H(k+1)х, х > > 0, т.е. матрица H(k+1)также положительно определена.
Можно показать, что для квадратичной функции с положительно определенной матрицей A направления рk в методе ДФП оказываются A-ортогональными. Отсюда следует, что точка минимума такой квадратичной функции этим методом будет найдена не более чем за п итераций.
Приведем описание алгоритма метода ДФП.
Шаг 0. Задать параметр точности e > 0, выбрать х Î Еn, вычислить f ¢(x), положить Н=Е.
Шаг 1. Найти направление р = — Н× f '(х).
Шаг 2. Решить задачу одномерной минимизации f(х + aр) ® min, a >0,
т.е. найти a*.
Шаг 3. Положить =х+a*р и найти f '(x). Проверить условие достижения точности: ||f '( )|[< e. Если оно выполнено, то положить x* = f* = f( ) и прекратить поиск, иначе — перейти к шагу 4.
Шаг 4. Найти векторы v = -x, u = f '( ) – f '(х), матрицы. Положить H=H+ A+ B, х =, f ¢(х)= f ¢( ) и перейти к шагу 1.
Пример 3.14. Методом ДФП решить задачу f(x)=4x21+ 3x22– 4x1x2+ x1®min.
Итерация 1.
Шаг 0. Положим e = 10-4, х =(0,0), найдем f'(x)=(l,0), положим Н = Е = = .
Шаг 1. Найдем направление р =-Н f ¢(х)=(- 1,0).
Шаг 2. Решим задачу f(х + aр) ® min, получим a* = 1/8.
Шаг 3. Находим = х+a*р = (-1/8, 0), f '( ) = (0, 1/2). Так как ||f '( )||= 1/2>e, переходим к шагу 4.
Шаг 4. Находим векторы v = — x=(-1/8, 0), u = f '( ) – f '(x) = (-1, 1/2) и матрицы
,
,
.
Полагаем х=, f '(x)=f'( ) и переходим к следующей итерации, начиная с шага 1.