37. Модификация метода БФГШ

Недостатком метода Бройдена – Флетчера – Гольдфарба – Шанно по сравнению с методом Девидона – Флетчера – Пауэлла является необходимость решения системы линейных алгебраических уравнений (4.30) для определения вектора направления одномерного поиска . Если коррекция некоторой квадратной матрицы проводится поправкой ранга один, то обратную матрицу можно найти по формуле Шермана – Моррисона

.

Дважды применяя эту формулу к формуле БФГШ (4.29), получим модификацию этой формулы

. (4.35)

Эта формула называется Модифицированной формулой Бройдена – Флетчера – Гольдфарба – Шанно, а использующий ее квазиньютоновский метод называется Модифицированным методом БФГШ. Вывод формулы (4.35) приведен в подразделе 5.4.

На первой итерации из заданной начальной точки выполняется одномерный поиск в направлении антиградиента:

, , , . (4.36)

Последующие итерации выполняются с учетом формулы (4.35):

, , , (4.37)

, (4.38)

, , . (4.39)

Итерации продолжаются до тех пор, пока выполняется условие

.

По формулам (4.36)–(4.39) составим алгоритм модифицированного метода Бройдена – Флетчера – Гольдфарба – Шанно.

Алгоритм модифицированного метода БФГШ.

Входные параметры: – начальная точка поиска, – процедура вычисления функции, – допустимая погрешность.

Выходной параметр – конечная точка поиска.

1. Вычислить и положить , .

2. Вычислить , .

3. Положить , .

4. Вычислить , , , .

5. Положить .

6. Вычислить .

7. Если , то перейти к шагу 2.

8. Остановиться.

Этот алгоритм не требует решения системы линейных алгебраических уравнений в отличие от предыдущего алгоритма.

Пример 4.7. Для вычисления точки минимума квадратичной функции (1.3) с допустимой погрешностью модифицированный метод БФГШ затратил 3 итерации и 19 вычислений функции. Траектория поиска такая же, как и траектория метода Бройдена из примера 4.1, представленная на рис. 4.1.

Пример 4.8. Минимизация функции Розенброка модифицированным методом БФГШ с погрешностью и допустимой погрешностью одномерного поиска потребовала 17 итераций и 265 вычислений функции, как и в примере 4.6, но время вычислений уменьшилось благодаря исключению решения СЛАУ. Траектория поиска такая же, как и на рис. 4.4. На рис. 4.5 представлена траектория минимизации функции Розенброка модифицированным методом БФГШ при и , что потребовало 26 итераций и 166 вычислений функции. При снижении точности одномерного поиска число итераций возросло, но количество вычислений функции уменьшилось. Этот пример подтверждает слабую чувствительность метода БФГШ к точности одномерного поиска.

Рис. 4.5. Минимизация функции Розенброка модифицированным методом БФГШ

< Предыдущая		Следующая >