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

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

X ^{k +1} = x ^k - a _k H ^(k) f¢(х ^k), (3.71)

где H ^(k) — некоторая квадратичная матрица размера п´ п, а величина шага a _k > 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. (3.72)

| Матрицы А ^(k) и В ^(k) выражаются на каждом шаге через матрицу H ^(k) и векторы-столбцы v ^k = x ^{k +1} - x ^k, u ^k = f ¢(x ^{k +1}) – f ¢(x ^k) следую­щим образом (см. (3.4)):

, (3.73)

.

Пусть в итерационном процессе (3.71)—(3.73) при минимизации выпуклой дифференцируемой функции f(х) в очередной точке х ⁱ градиент f' (х ⁱ) ¹ 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 ⁽⁰⁾= Е обладает этими свойствами. Отметим, что из соотношений (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 Обозначим векторы C x = q, а Cu ^k = r, тогда равенство (3.74) можно записать в виде

< H ^(k+1) х,х> = <q² - + .

(3.75)

Из неравенства Коши — Буняковского (3.2) следует, что q²r² ³ <q, r>² поэтому из (3.75) получим неравенство:

< H ^(k+1) х, х> ³ .

Оценим скалярное произведение в знаменателе правой части неравенства (3.76) с учетом свойства исчерпывающего спуска:

<v ^k, u ^k > = < x ^{k +1} – x, f ¢(x ^{k +1}) – f ¢(x ^k)> = a _k < p ^k, f ¢(x ^{k +1}) – f ¢(x ^k) > = a _k < p ^k, f ¢(x ^k) > = a _k < H ^(k) f ¢(x ^k), f ¢(x ^k) > > 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)=4x²₁+ 3x²₂– 4x₁x₂+ x₁®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.