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

Этот класс методов основан на аппроксимации Гессиана некоторой положительно определенной симметрической матрицей H. Можно сказать, что если в методе Ньютона и его модификациях кривизна оптимизируемой функции учитывается Гессианом, то в квазиньютоновских информацию о кривизне накапливает матрица Н. Квазиньютоновские методы относятся к методам первого порядка, поскольку для пересчета Н на каждой итерации используется значение градиента в точках и , что принципиально отличает квазиньютоновские методы от методов второго порядка.

Матрицу Н называют метрикой. Поскольку метрика изменяется на каждой итерации, квазиньютоновские методы часто называют методами с переменной метрикой.

Расчетной формулой квазиньютоновского метода будет следующая формула:

Рассмотрим нахождение .

Разложим в ряд Тейлора градиент g(x) в окрестностях следующего к-ого приближения . Отбросив производные выше первого порядка и подставив будем иметь:

или

или

Заметим, что для квадратичных функций эта формула точная.

Для матрицы , которая будет аппроксимировать должно выполняться условие:

Такое условие называется квазиньютоновским. Методы оптимизации, для которых на каждой итерации выполняется квазиньютоновское условие, называются квазиньютоновскими.

Матрицу находят как:

Перепишем квазиньютоновское условие в виде:

Такому условию удовлетворяет большое число матриц.

Прямой подстановкой можно показать, что для уравнение имеет следующее решение:

,

где z и y – произвольные векторы размерности n.

Например, если , то получим метод Бройдена:

, где

.

, BFGS