Лекция: КВАЗИНЬЮТОНОВСКИЕ МЕТОДЫ

Стремление уменьшить объем вычислений привело к созданию класса методов, близких по скорости сходимости к обобщенному ме­тоду Ньютона, но не использующих вторых производных целевой фун­кции 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.

еще рефераты
Еще работы по информатике